Maximum weight induced matching in some subclasses of bipartite graphs

B. S. Panda (), Arti Pandey (), Juhi Chaudhary (), Piyush Dane and Manav Kashyap
Additional contact information
B. S. Panda: Indian Institute of Technology Delhi
Arti Pandey: Indian Institute of Technology Ropar
Juhi Chaudhary: Indian Institute of Technology Delhi
Piyush Dane: Indian Institute of Technology Delhi
Manav Kashyap: Indian Institute of Technology Delhi

Journal of Combinatorial Optimization, No 0, 20 pages

Abstract: Abstract A subset $$M\subseteq E$$ M ⊆ E of edges of a graph $$G=(V,E)$$ G = ( V , 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 if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced by $$S=\{v \in V |$$ S = { v ∈ V | v is incident on an edge of $$M\}$$ 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 Maximum Weight Induced Matching problem in a weighted graph $$G=(V,E)$$ G = ( V , E ) in which the weight of each edge is a positive real number, is to find an induced matching such that the sum of the weights of its edges is maximum. It is known that the Induced Matching Decision problem and hence the Maximum Weight Induced Matching problem is known to be NP-complete for general graphs and bipartite graphs. In this paper, we strengthened this result by showing that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs, the subclasses of the class of bipartite graphs. On the positive side, we propose polynomial time algorithms for the Maximum Weight Induced Matching problem for circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial time reductions from the Maximum Weight Induced Matching problem in these graph classes to the Maximum Weight Induced Matching problem in convex bipartite graphs.

Keywords: Matching; Induced matching; Bipartite graphs; Graph algorithm; NP-complete (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00611-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00611-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00611-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().