Let $G=(V,E)$ be a finite undirected graph without loops and multiple edges. A subset $M \subseteq E$ of edges is a { \em dominating induced matching} ({ \em d.i.m.}) in $G$ if every edge in $E$ is intersected by exactly one edge of $M$. In particular, this means that $M$ is an induced matching, and every edge not in $M$ shares exactly one vertex with an edge in $M$. Clearly, not every graph has a d.i.m. The \emph{ Dominating Induced Matching} (\emph{ DIM}) problem asks for the existence of a d.i.m.\ in $G$; this problem is also known as the \emph{ Efficient Edge Domination} problem; it is the { \em Efficient Domination} problem for line graphs. The DIM problem is \NP-complete in general, and even for very restricted graph classes such as planar bipartite graphs with maximum degree 3. However, DIM is solvable in polynomial time for claw-free (i.e., $S_{ 1,1,1}$-free) graphs, for $S_{ 1,2,3}$-free graphs as well as for $S_{ 2,2,2}$-free graphs, in linear time for $P_7$-free graphs, and in polynomial time for $P_8$-free graphs ($P_k$ is a special case of $S_{ i,j,\ell}$). In a paper by Hertz, Lozin, Ries, Zamaraev and de Werra, it was conjectured that DIM is solvable in polynomial time for $S_{ i,j,k}$-free graphs for every fixed $i,j,k$. In this paper, combining two distinct approaches, we solve it in polynomial time for $S_{ 1,2,4}$-free graphs which generalizes the $S_{ 1,2,3}$-free as well as the $P_7$-free case.
Categories: cs.DM