Dominating induced matchings for \(P_7\)-free graphs in linear time (Q476446): Difference between revisions

A dominating induced matching (d.i.m.) is an induced matching that is at the same time a dominating edge set. The dominating induced matching problem (DIM) asks whether a given graph has a d.i.m. The DIM is NP-complete for very restricted graph classes, say for planar bipartite graph with maximum degree three. In this paper, an algorithm is designed that solves the weighted DIM problem (to find a minimum weight d.i.m.) for \(P_7\)-free graphs in linear time. The algorithm is robust in the sense that it either finds a minimum d.i.m. or finds out that the input graph has no d.i.m. or is not \(P_7\)-free. Along the way, a simple direct linear algorithm is given that recognizes \(P_4\)-free graphs (alias cographs) with d.i.m. It remains open whether for some \(k\) the DIM problem is NP-complete for \(P_k\)-free graphs.