Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity

Abstract

The so called (σ,ρ)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (σ,ρ)-dominating if for every vertex v ∈ S, |S ∩ N(v)| ∈ σ, and for every v ∉ S, |S ∩ N(v)| ∈ ρ, where σ and ρ are sets of nonnegative integers and N(v) denotes the open neighborhood of the vertex v in G.) It is known that for any two nonempty finite sets σ and ρ (such that 0 ∉ ρ), the decision problem whether an input graph contains a (σ,ρ)-dominating set is NP-complete, but that when restricted to some graph classes, polynomial time solvable instances occur. We show that for every k, the problem performs a complete dichotomy when restricted to k-degenerate graphs, and we fully characterize the polynomial and NP-complete instances. It is further shown that the problem is polynomial time solvable if σ, ρ are such that every k-degenerate graph contains at most one (σ,ρ)-dominating set, and NP-complete otherwise. This relates to the concept of ambivalent graphs previously introduced for chordal graphs.