Weighted Efficient Domination for -Free Graphs in Polynomial Time
Let be a finite undirected graph. A vertex {\em dominates} itself and all its neighbors in . A vertex set is an {\em efficient dominating set} (\emph{e.d.}\ for short) of if every vertex of is dominated by exactly one vertex of . The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.\ in , is known to be \NP-complete even for very restricted graph classes such as for claw-free graphs, for chordal graphs and for -free graphs (and thus, for -free graphs). We call a graph a {\em linear forest} if is cycle- and claw-free, i.e., its components are paths. Thus, the ED problem remains \NP-complete for -free graphs, whenever is not a linear forest. Let WED denote the vertex-weighted version of the ED problem asking for an e.d. of minimum weight if one exists. In this paper, we show that WED is solvable in polynomial time for -free graphs for every fixed , which solves an open problem, and, using modular decomposition, we improve known time bounds for WED on -free graphs, -free graphs, and on -free graphs and simplify proofs. For -free graphs, the only remaining open case is WED on -free graphs.