Upper Domination: Complexity and Approximation

Cristina Bazgan; Ljiljana Brankovic; Katrin Casel; Henning Fernau; Klaus Jansen; Kim-Manuel Klein; Michael Lampis; Mathieu Liedloff; Jérôme Monnot; Vangelis Th Paschos

doi:10.1007/978-3-319-44543-4_19

Upper Domination: Complexity and Approximation

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th Paschos

Computer Science

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

9 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms
Editors	Veli Mäkinen, Simon J Puglisi, Leena Salmela
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	241-252
ISBN (Print)	9783319445434, 9783319445427, 331944543X
DOIs	https://doi.org/10.1007/978-3-319-44543-4_19
Publication status	Published - 2016
Event	IWOCA 2016: 27th International Workshop on Combinatorial Algorithms - University of Helsinki, Helsinki, Finland Duration: 17 Aug 2016 → 19 Aug 2016

Publication series

Name	Lecture Notes in Computer Science
Number	9843
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	IWOCA 2016: 27th International Workshop on Combinatorial Algorithms
City	Helsinki, Finland
Period	17/08/16 → 19/08/16

Access to Document

10.1007/978-3-319-44543-4_19

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

Handle.net

Persistent link

Cite this

Bazgan, C., Brankovic, L., Casel, K., Fernau, H., Jansen, K., Klein, K.-M., Lampis, M., Liedloff, M., Monnot, J., & Paschos, V. T. (2016). Upper Domination: Complexity and Approximation. In V. Mäkinen, S. J Puglisi, & L. Salmela (Eds.), Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms (pp. 241-252). (Lecture Notes in Computer Science; No. 9843). Springer. https://doi.org/10.1007/978-3-319-44543-4_19

@inproceedings{d1e6be4657b14b4ebaf8cfc045742efc,

title = "Upper Domination: Complexity and Approximation",

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

author = "Cristina Bazgan and Ljiljana Brankovic and Katrin Casel and Henning Fernau and Klaus Jansen and Kim-Manuel Klein and Michael Lampis and Mathieu Liedloff and J{\'e}r{\^o}me Monnot and Paschos, \{Vangelis Th\}",

year = "2016",

doi = "10.1007/978-3-319-44543-4\_19",

language = "English",

isbn = "9783319445434",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "9843",

pages = "241--252",

editor = "Veli M{\"a}kinen and \{J Puglisi\}, Simon and Leena Salmela",

booktitle = "Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms",

note = "IWOCA 2016: 27th International Workshop on Combinatorial Algorithms ; Conference date: 17-08-2016 Through 19-08-2016",

}

Bazgan, C, Brankovic, L, Casel, K, Fernau, H, Jansen, K, Klein, K-M, Lampis, M, Liedloff, M, Monnot, J & Paschos, VT 2016, Upper Domination: Complexity and Approximation. in V Mäkinen, S J Puglisi & L Salmela (eds), Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms. Lecture Notes in Computer Science, no. 9843, Springer, Cham, Switzerland, pp. 241-252, IWOCA 2016: 27th International Workshop on Combinatorial Algorithms, Helsinki, Finland, 17/08/16. https://doi.org/10.1007/978-3-319-44543-4_19

Upper Domination: Complexity and Approximation. / Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin et al.
Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms. ed. / Veli Mäkinen; Simon J Puglisi; Leena Salmela. Cham, Switzerland: Springer, 2016. p. 241-252 (Lecture Notes in Computer Science; No. 9843).

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

TY - GEN

T1 - Upper Domination

T2 - IWOCA 2016: 27th International Workshop on Combinatorial Algorithms

AU - Bazgan, Cristina

AU - Brankovic, Ljiljana

AU - Casel, Katrin

AU - Fernau, Henning

AU - Jansen, Klaus

AU - Klein, Kim-Manuel

AU - Lampis, Michael

AU - Liedloff, Mathieu

AU - Monnot, Jérôme

AU - Paschos, Vangelis Th

PY - 2016

Y1 - 2016

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

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

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

U2 - 10.1007/978-3-319-44543-4_19

DO - 10.1007/978-3-319-44543-4_19

M3 - Conference contribution

SN - 9783319445434

SN - 9783319445427

SN - 331944543X

T3 - Lecture Notes in Computer Science

SP - 241

EP - 252

BT - Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms

A2 - Mäkinen, Veli

A2 - J Puglisi, Simon

A2 - Salmela, Leena

PB - Springer

CY - Cham, Switzerland

Y2 - 17 August 2016 through 19 August 2016

ER -

Bazgan C, Brankovic L, Casel K, Fernau H, Jansen K, Klein KM et al. Upper Domination: Complexity and Approximation. In Mäkinen V, J Puglisi S, Salmela L, editors, Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms. Cham, Switzerland: Springer. 2016. p. 241-252. (Lecture Notes in Computer Science; 9843). Epub 2016 Aug 9. doi: 10.1007/978-3-319-44543-4_19

Upper Domination: Complexity and Approximation

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Cite this