Thumbnail

A Dichotomy for Upper Domination in Monogenic Classes

AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2014), A Dichotomy for Upper Domination in Monogenic Classes, in Zhang, Zhao; Wu, Lidong; Xu, Wen; Du, Ding-Zhu, Combinatorial Optimization and Applications, Springer International Publishing : Cham, p. 258-267. 10.1007/978-3-319-12691-3_20

View/Open
Type
Communication / Conférence
Date
2014
Conference title
8th International Conference, COCOA 2014
Conference date
2014-12
Conference city
Wailea, Maui, HI
Conference country
United States
Book title
Combinatorial Optimization and Applications
Book author
Zhang, Zhao; Wu, Lidong; Xu, Wen; Du, Ding-Zhu
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-12690-6
Number of pages
774
Pages
258-267
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
Center for Numerical Porous Media (NumPor) - King Abdullah University of Science and Technology
Lozin, Vadim
Centre for Discrete Mathematics and its Applications [Warwick] [DIMAP]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.
Subjects / Keywords
graphs
JEL
C44 - Operations Research; Statistical Decision Theory