On the Complexity Landscape of the Domination Chain

Cristina Bazgan; Ljiljana Brankovic; Katrin Casel; Henning Fernau

doi:10.1007/978-3-319-29221-2_6

On the Complexity Landscape of the Domination Chain

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Citations (Scopus)

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(n^{log 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.

Original language	English
Title of host publication	Algorithms and Discrete Applied Mathematics
Editors	Sathish Govindarajan, Anil Maheshwari
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	61-72
ISBN (Print)	9783319292212, 9783319292205
DOIs	https://doi.org/10.1007/978-3-319-29221-2_6
Publication status	Published - 2016
Event	CALDAM 2016: 2nd International Conference on Algorithms and Discrete Applied Mathematics - University of Kerala, Thiruvananthapuram, India Duration: 18 Feb 2016 → 20 Feb 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer International Publishing
Number	9602
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	CALDAM 2016: 2nd International Conference on Algorithms and Discrete Applied Mathematics
City	Thiruvananthapuram, India
Period	18/02/16 → 20/02/16

Access to Document

10.1007/978-3-319-29221-2_6

https://hdl.handle.net/1959.11/43430

Handle.net

Persistent link

Cite this

@inproceedings{3316c44a57b641239e7630a0f79a78ae,

title = "On the Complexity Landscape of the Domination Chain",

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.",

author = "Cristina Bazgan and Ljiljana Brankovic and Katrin Casel and Henning Fernau",

note = "Paper presented by Henning Fernau; CALDAM 2016: 2nd International Conference on Algorithms and Discrete Applied Mathematics ; Conference date: 18-02-2016 Through 20-02-2016",

year = "2016",

doi = "10.1007/978-3-319-29221-2\_6",

language = "English",

isbn = "9783319292212",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "9602",

pages = "61--72",

editor = "Sathish Govindarajan and Anil Maheshwari",

booktitle = "Algorithms and Discrete Applied Mathematics",

}

Bazgan, C, Brankovic, L, Casel, K & Fernau, H 2016, On the Complexity Landscape of the Domination Chain. in S Govindarajan & A Maheshwari (eds), Algorithms and Discrete Applied Mathematics. Lecture Notes in Computer Science, no. 9602, Springer, Cham, Switzerland, pp. 61-72, CALDAM 2016: 2nd International Conference on Algorithms and Discrete Applied Mathematics, Thiruvananthapuram, India, 18/02/16. https://doi.org/10.1007/978-3-319-29221-2_6

On the Complexity Landscape of the Domination Chain. / Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin et al.
Algorithms and Discrete Applied Mathematics. ed. / Sathish Govindarajan; Anil Maheshwari. Cham, Switzerland: Springer, 2016. p. 61-72 (Lecture Notes in Computer Science; No. 9602).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the Complexity Landscape of the Domination Chain

AU - Bazgan, Cristina

AU - Brankovic, Ljiljana

AU - Casel, Katrin

AU - Fernau, Henning

N1 - Paper presented by Henning Fernau

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://caldam2016.keralauniversity.ac.in/day1.html

UR - https://www.scopus.com/pages/publications/84959137914

U2 - 10.1007/978-3-319-29221-2_6

DO - 10.1007/978-3-319-29221-2_6

M3 - Conference contribution

SN - 9783319292212

SN - 9783319292205

T3 - Lecture Notes in Computer Science

SP - 61

EP - 72

BT - Algorithms and Discrete Applied Mathematics

A2 - Govindarajan, Sathish

A2 - Maheshwari, Anil

PB - Springer

CY - Cham, Switzerland

T2 - CALDAM 2016: 2nd International Conference on Algorithms and Discrete Applied Mathematics

Y2 - 18 February 2016 through 20 February 2016

ER -

On the Complexity Landscape of the Domination Chain

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Cite this