- Title
- Upper domination: complexity and approximation
- Creator
- Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.
- Relation
- 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). Combinatorial Algorithms: 27th International Workshop, IWOCA 2016: Proceedings (presented in Lecture Notes in Computer Science, Vol. 2843) (Helsinki, Finland 17-19 August, 2016) p. 241-253
- Publisher Link
- http://dx.doi.org/10.1007/978-3-319-44543-4_19
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2016
- Description
- We consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an n1−ϵ approximation for any ϵ>0, making it significantly harder than Dominating Set, while it remains hard even on severely restricted special cases, such as cubic graphs (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an O(Δ) approximation on graphs of maximum degree Δ, as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight n1−1d upper and lower bounds on the approximability of the related problem Maximum Minimal Hitting Set on d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.
- Subject
- upper domination; graphs; approximation; complexity
- Identifier
- http://hdl.handle.net/1959.13/1322889
- Identifier
- uon:24680
- Identifier
- ISBN:9783319445427
- Language
- eng
- Reviewed
- Hits: 5511
- Visitors: 2702
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|