Upper Domination: Towards a Dichotomy Through Boundary Properties

Hassan M. AbouEisha, Shahid Hussain, Vadim Lozin, Jérôme Monnot, Bernard Ries, Viktor Zamaraev

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.
Original languageEnglish (US)
Pages (from-to)2799-2817
Number of pages19
Issue number10
StatePublished - Jul 14 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Vadim Lozin and Viktor Zamaraev gratefully acknowledge support from EPSRC, Grant EP/L020408/1. Part of this research was carried out when Vadim Lozin was visiting the King Abdullah University of Science and Technology (KAUST). This author thanks the University for hospitality and stimulating research environment.


Dive into the research topics of 'Upper Domination: Towards a Dichotomy Through Boundary Properties'. Together they form a unique fingerprint.

Cite this