Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/54504
Title: Upper Domination: Complexity and Approximation
Contributor(s): Bazgan, Cristina (author); Brankovic, Ljiljana  (author)orcid ; Casel, Katrin (author); Fernau, Henning (author); Jansen, Klaus (author); Klein, Kim-Manuel (author); Lampis, Michael (author); Liedloff, Mathieu (author); Monnot, Jérôme (author); Paschos, Vangelis Th (author)
Publication Date: 2016
DOI: 10.1007/978-3-319-44543-4_19
Handle Link: https://hdl.handle.net/1959.11/54504
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.

Publication Type: Conference Publication
Conference Details: IWOCA 2016: 27th International Workshop on Combinatorial Algorithms, Helsinki, Finland, 17th - 19th August, 2016
Source of Publication: Combinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms, p. 241-252
Publisher: Springer
Place of Publication: Cham, Switzerland
Fields of Research (FoR) 2020: 461305 Data structures and algorithms
Socio-Economic Objective (SEO) 2020: 229999 Other information and communication services not elsewhere classified
Peer Reviewed: Yes
HERDC Category Description: E1 Refereed Scholarly Conference Publication
WorldCat record: https://www.worldcat.org/title/957123354
Series Name: Lecture Notes in Computer Science
Series Number : 9843
Appears in Collections:Conference Publication
School of Science and Technology

Files in This Item:
2 files
File Description SizeFormat 
Show full item record

SCOPUSTM   
Citations

9
checked on Dec 14, 2024

Page view(s)

300
checked on Jun 18, 2023

Download(s)

4
checked on Jun 18, 2023
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.