Thumbnail

Upper Domination: Towards a Dichotomy Through Boundary Properties

AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor (2018), Upper Domination: Towards a Dichotomy Through Boundary Properties, Algorithmica, 80, 10, p. 2799-2817. 10.1007/s00453-017-0346-9

View/Open
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Algorithmica
Volume
80
Number
10
Publisher
Springer
Pages
2799-2817
Publication identifier
Metadata
Show full item record
Author(s)
AbouEisha, Hassan
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Hussain, Shahid
autre
Lozin, Vadim
Warwick Mathematics Institute [WMI]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard

Zamaraev, Viktor
Warwick Mathematics Institute [WMI]
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.
Subjects / Keywords
Upper dominating set; Boundary class; Complexity dichotomy; NP-hard