Upper Domination : Towards a Dichotomy Through Boundary Properties
- AbouEisha, Hassan King Abdullah University of Science and Technology
- Shahid, Hussain Habib University
- Lozin, Vadim University of Warwick
- Monnot, Jérôme Université Paris-Dauphine, PSL Research University
- Ries, Bernard University of Fribourg
- Zamaraev, Viktor University of Warwick
-
2018
Published in:
- Algorithmica. - 2018, vol. 80, no. 10, p. 2799-2817
English
Anupper 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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324394
- DOI 10.1007/s00453-017-0346-9
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307805
Statistics
Document views: 49
File downloads:
- domination_rero.pdf: 85