2015/08/31 by Andreas Brandstadt, Brandstadt, Andreas, Raffaele Mosca +1
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1508.07733
arxiv created 2015/09/14 · arxiv updated 2015/09/15
In a finite undirected graph G=(V,E), a vertex v ∈ V \em dominates itself and its neighbors in G. A vertex set D ⊆ V is an \em efficient dominating set (\em e.d. for short) of G if every v ∈ V is dominated in G by exactly one vertex of D. The \em Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete for P7-free graphs but solvable in polynomial time for P5-free graphs. The P6-free case was the last open question for the complexity of ED on F-free graphs. Recently, Lokshtanov, Pilipczuk and van Leeuwen showed that weighted ED is solvable in polynomial time for P6-free graphs, based on their sub-exponential algorithm for the Maximum Weight Independent Set problem for P6-free graphs. Independently, at the same time, Mosca found a polynomial time algorithm for weighted ED on P6-free graphs using a direct approach. In this paper, we describe the details of this approach which is simpler and much faster, namely its time bound is \cal O(n6 m).