In a finite undirected graph G = (V, E), a vertex υ ∈V dominates itself and its neighbors in G. A vertex set D is contained in V is an efficient dominating set (e.d.s. for short) of G if every υ ∈V is dominated in G 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 for P_7-free graphs and solvable in polynomial time for P_5-free graphs. The P_6-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 P_6-free graphs, based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for P_6-free graphs. Independently, by a direct approach which is simpler and faster, we found an O(n~5m) time solution for weighted ED on P6-free graphs. Moreover, we showed that weighted ED is solvable in linear time for P_5-free graphs which solves another open question for the complexity of (weighted) ED.
展开▼
