2017/01/12 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #cs.DM #msc:05C69 #msc:05C70 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1701.03414
arxiv created 2019/04/30 · arxiv updated 2019/05/01
A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be \NP-complete even for very restricted graph classes such as for 2P3-free chordal graphs while it is solvable in polynomial time for P6-free chordal graphs (and even for P6-free graphs). A standard reduction from the \NP-complete Exact Cover problem shows that ED is \NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is \NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is \NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P2-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S1,2,3.