On the Complexity Landscape of the Domination Chain

Author(s)
Bazgan, Cristina
Brankovic, Ljiljana
Casel, Katrin
Fernau, Henning
Publication Date
2016
Abstract
Paper presented by Henning Fernau
Abstract
<p>In this paper, we survey and supplement the complexity landscape of the domination chain parameters as a whole, including classifications according to approximability and parameterised complexity. Moreover, we provide clear pointers to yet open questions. As this posed the majority of hitherto unsettled problems, we focus on Upper Irredundance and Lower Irredundance that correspond to finding the largest irredundant set and resp. the smallest maximal irredundant set. The problems are proved NP-hard even for planar cubic graphs. While Lower Irredundance is proved not <i>c</i> log(<i>n</i>)-approximable in polynomial time unless <i>NP</i> ⊆ DTIME(n<sup>log log <i>n</i></sup>), no such result is known for Upper Irredundance. Their complementary versions are constant-factor approximable in polynomial time. All these four versions are APX-hard even on cubic graphs.</p>
Citation
Algorithms and Discrete Applied Mathematics, p. 61-72
ISBN
9783319292212
9783319292205
Link
Publisher
Springer
Series
Lecture Notes in Computer Science
Title
On the Complexity Landscape of the Domination Chain
Type of document
Conference Publication
Entity Type
Publication

Files:

NameSizeformatDescriptionLink