Induced Matching in Some Subclasses of Bipartite Graphs

摘要

For a graph G = (V,E), a set M ⊆ E is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching in G if G[M], the subgraph of G induced by M, is same as G[S], the subgraph of G induced by S = {v ∈V| v is incident on an edge of M}. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. Given a graph G and a positive integer k, the Induced Matching Decision problem is to decide whether G has an induced matching of cardinality at least k. The Induced Matching Decision problem is NP-complete on bipartite graphs, but polynomial time solvable for convex bipartite graphs. In this paper, we show that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs and perfect elimination bipartite graphs. On the positive side, we propose polynomial time algorithms to solve the Maximum Induced Matching problem in circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial reductions from the Maximum Induced Matching problem in these graph classes to the Maximum Induced Matching problem in convex bipartite graphs.