Induced Matching in Some Subclasses of Bipartite Graphs

详细信息    查看全文

• 关键词：Matching ; Induced matching ; Bipartite graphs ; Graph algorithm ; NP ; complete
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10156
• 期：1
• 页码：308-319
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-53007-9
• 卷排序：10156

文摘

For a graph \(G=(V,E)\), a set \(M\subseteq 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 \in 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.