Portal de Periódicos da CAPES

Upper Domination: Complexity and Approximation

2016; Springer Science+Business Media; Linguagem: Inglês

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

1611-3349

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

Optimization and Search Problems

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 $$n^{1-\epsilon }$$ approximation for any $$\epsilon >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(\varDelta )$$ approximation on graphs of maximum degree $$\varDelta $$ , as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight $$n^{1-\frac{1}{d}}$$ 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.