Finding Dominating Induced Matchings in P8 -Free Graphs in Polynomial Time

Let G= (V, E) be a finite undirected graph. An edge set E′⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G; this problem is also known as the Efficient Edge Domination problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three and is solvable in linear time for P7-free graphs. However, its complexity was open for Pk-free graphs for any k≥ 8 ; Pk denotes the chordless path with k vertices and k- 1 edges. We show in this paper that the weighted DIM problem is solvable in polynomial time for P8-free graphs. © 2016, Springer Science+Business Media New York.