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 -