Finding Maximum Induced Matchings in Subclasses of Claw-Free and P_5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size

摘要

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph G. This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph G either finds a maximum induced matching in G, or claims that the size of a maximum induced matching in G is strictly less than the size of a maximum matching in G. We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and r-regular graphs for r ≥ 5. On the other hand, we present polynomial time algorithms for the MIM problem on (P_5, D_m)-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.