2015/07/23 by Andreas Brandstädt, Brandstadt, Andreas, Raffaele Mosca +1
Computer Science · #Advanced Graph Theory Research #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1507.06541
openalex publication_date 2015/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.