Upper Domination: Towards a Dichotomy Through Boundary Properties

Thumbnail
View/Open
Date
2018
Notes
The results of this paper previously appeared as extended abstracts in proceedings of the 8th International Conference on Combinatorial Optimization and Applications, COCOA 2014, and the 27th International Workshop on Combinatorial Algorithms, IWOCA 2016.
Dewey
Programmation, logiciels, organisation des données
Sujet
Upper dominating set; Boundary class; Complexity dichotomy; NP-hard
Journal issue
Algorithmica
Volume
80
Number
10
Publication date
10-2018
Article pages
2799-2817
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00453-017-0346-9
URI
https://basepub.dauphine.fr/handle/123456789/19239
Collections
Metadata
Show full item record
Author
AbouEisha, Hassan
230273 Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
115536 autre
Lozin, Vadim
41505 Warwick Mathematics Institute [WMI]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
207238 University of Fribourg
Zamaraev, Viktor
41505 Warwick Mathematics Institute [WMI]
Type
Article accepté pour publication ou publié
Abstract (EN)
An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.