Finding Dominating Induced Matchings in S_1,1,5-Free Graphs in Polynomial Time

2019/05/14 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.1905.05582

Abstract

Let G=(V,E) be a finite undirected graph. An edge set 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; this problem is also known as the Efficient Edge Domination problem; it is the Efficient Domination problem for line graphs. The DIM problem is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in linear time for P₇-free graphs, and in polynomial time for S_1,2,4-free graphs as well as for S_2,2,2-free graphs and for S_2,2,3-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for S_1,1,5-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_2,2,3)-Free Graphs in Polynomial Time
• Dominating Induced Matchings in S_1,2,4-Free Graphs
• Finding Dominating Induced Matchings in P₉-Free Graphs in Polynomial Time
• Dominating Induced Matchings for P₈-free Graphs in Polynomial Time
• Dominating Induced Matchings for P7-Free Graphs in Linear Time