Thumbnail - Request a copy

On the Complexity Landscape of the Domination Chain

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning (2016), On the Complexity Landscape of the Domination Chain, in Govindarajan, Sathish; Maheshwari, Anil, Algorithms and Discrete Applied Mathematics, Springer : Cham, p. 61-72. 10.1007/978-3-319-29221-2_6

Type
Communication / Conférence
Date
2016
Conference title
Second International Conference, CALDAM 2016
Conference date
2016-02
Conference city
Thiruvananthapuram
Conference country
India
Book title
Algorithms and Discrete Applied Mathematics
Book author
Govindarajan, Sathish; Maheshwari, Anil
Publisher
Springer
Published in
Cham
ISBN
978-3-319-29220-5
Number of pages
369
Pages
61-72
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Brankovic, Ljiljana
University of Newcastle
Casel, Katrin

Fernau, Henning
Abstract (EN)
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 clog(n)-approximable in polynomial time unless NP⊆DTIME(nloglogn), 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.
Subjects / Keywords
domination; complexity
JEL
C44 - Operations Research; Statistical Decision Theory