Paper Info
Title
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 NPcomplete 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.
Year
DOI
Venue
2008
10.1007/978-3-540-79228-4_16
TAMC
Keywords
Field
DocType
decision problem,chordal graph,computational complexity,polynomial time,dominating set
Integer,Discrete mathematics,Combinatorics,Finite set,Vertex (geometry),Polynomial,Chordal graph,Independent set,Time complexity,Mathematics,Computational complexity theory
Conference
Volume
ISSN
ISBN
4978
0302-9743
3-540-79227-9
Citations 
PageRank 
References 
2
0.37
6
Authors
2
Name
Order
Citations
PageRank
Petr A. Golovach176683.25
Jan Kratochvíl21751151.84