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 (Q1762983)

From MaRDI portal
scientific article
Language Label Description Also known as
English
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
scientific article

    Statements

    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 (English)
    0 references
    0 references
    0 references
    0 references
    11 February 2005
    0 references
    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 \geq 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.
    0 references
    Induced matching
    0 references
    Line-graphs
    0 references
    Claw-free graphs
    0 references
    Bull
    0 references
    Regular graphs
    0 references
    Polynomial algorithms
    0 references

    Identifiers