- Title
- On the complexity landscape of the domination chain
- Creator
- Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning
- Relation
- Second International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2016). Proceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics [presented in Algortihms and Discrete Mathematics: Lecture Notes in Computer Science, Vol. 9602 No. 2016] (Thiruvananthapuram, India 18-20 February, 2016) p. 61-72
- Publisher Link
- http://dx.doi.org/10.1007/978-3-319-29221-2_6
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2016
- Description
- 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 constantfactor approximable in polynomial time. All these four versions are APXhard even on cubic graphs.
- Subject
- domination chain parameters; complexity landscape; upper irredundance; lower irredundance
- Identifier
- http://hdl.handle.net/1959.13/1322921
- Identifier
- uon:24690
- Identifier
- ISBN:9783319292205
- Language
- eng
- Reviewed
- Hits: 842
- Visitors: 836
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|