A dichotomy for upper domination in monogenic classes

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

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is NP-hard for general graphs and in many restricted graph families. In the present paper, we study the computational complexity of this problem in monogenic classes of graphs (i.e. classes defined by a single forbidden induced subgraph) and show that the problem admits a dichotomy in this family. In particular, we prove that if the only forbidden induced subgraph is a P4 or a 2K2 (or any induced subgraph of these graphs), then the problem can be solved in polynomial time. Otherwise, it is NP-hard.
Original languageEnglish (US)
Pages (from-to)258-267
Number of pages10
JournalCombinatorial Optimization and Applications
Volume8881
DOIs
StatePublished - Nov 14 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A dichotomy for upper domination in monogenic classes'. Together they form a unique fingerprint.

Cite this