TY - JOUR

T1 - A dichotomy for upper domination in monogenic classes

AU - AbouEisha, Hassan M.

AU - Hussain, Shahid

AU - Lozin, Vadim V.

AU - Monnot, Jérôme

AU - Ries, Bernard

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/11/14

Y1 - 2014/11/14

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/563271

UR - https://basepub.dauphine.fr//bitstream/123456789/16160/2/COCOA14_UDS.pdf

UR - http://www.scopus.com/inward/record.url?scp=84921515692&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-12691-3_20

DO - 10.1007/978-3-319-12691-3_20

M3 - Article

SN - 0302-9743

VL - 8881

SP - 258

EP - 267

JO - Combinatorial Optimization and Applications

JF - Combinatorial Optimization and Applications

ER -