On the Complexity Landscape of the Domination Chain

Title
On the Complexity Landscape of the Domination Chain
Publication Date
2016
Author(s)
Bazgan, Cristina
Brankovic, Ljiljana
( author )
OrcID: https://orcid.org/0000-0002-5056-4627
Email: lbrankov@une.edu.au
UNE Id une-id:lbrankov
Casel, Katrin
Fernau, Henning
Editor
Editor(s): Sathish Govindarajan and Anil Maheshwari
Abstract
Paper presented by Henning Fernau
Type of document
Conference Publication
Language
en
Entity Type
Publication
Publisher
Springer
Place of publication
Cham, Switzerland
Series
Lecture Notes in Computer Science
DOI
10.1007/978-3-319-29221-2_6
UNE publication id
une:1959.11/43430
Abstract

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 c log(n)-approximable in polynomial time unless NP ⊆ DTIME(nlog log n), 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.
Link
link
Citation
Algorithms and Discrete Applied Mathematics, p. 61-72
ISBN
9783319292212
9783319292205
Start page
61
End page
72

Files:

NameSizeformatDescriptionLink