Finding Dominating Induced Matchings in P₉-Free Graphs in Polynomial Time

2019/08/02 by Brandstädt, Andreas, Mosca, Raffaele · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.00978

Abstract

Let G=(V,E) be a finite undirected graph. An edge subset E' ⊆ E is a \em dominating induced matching (\em 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. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P₇-free graphs and in polynomial time for P₈-free graphs. In this paper, we solve it in polynomial time for P₉-free graphs.

Cited by

• Perfect Edge Domination in P₆-free Graphs and in Graphs Without Efficient Edge Dominating Sets

Related

• Finding Dominating Induced Matchings in S_1,1,5-Free Graphs in Polynomial Time
• Dominating Induced Matchings for P₈-free Graphs in Polynomial Time
• Finding Dominating Induced Matchings in (S_2,2,3)-Free Graphs in Polynomial Time
• Dominating Induced Matchings in S_1,2,4-Free Graphs
• Dominating Induced Matchings for P7-Free Graphs in Linear Time