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

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.