Maximum weight induced matching in some subclasses of bipartite graphs
- PDF / 1,097,077 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 56 Downloads / 241 Views
Maximum weight induced matching in some subclasses of bipartite graphs B. S. Panda1 · Arti Pandey2 · Juhi Chaudhary1 · Piyush Dane1 · Manav Kashyap1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A subset M ⊆ E of edges of a graph 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 ∈ 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 Maximum Weight Induced Matching problem in a weighted graph 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, combconvex 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
B
B. S. Panda [email protected]
Extended author information available on the last page of the article
123
Journal of Combinatorial Optimization
1 Introduction Let G = (V , E) be a graph. Let n and m denote the number of vertices and the number of edges of G, respectively. A set of edges M ⊆ E is called a matching if no two edges of M are incident on a common vertex. Vertices incident to the edges of a matching M are called saturated by M. The Maximum Matching problem is to find a matching of maximum cardinality in a given graph. The Maximum Matching problem and its variations are extensively studied in literature. In this paper, we study an important variant of matchings called induced matchings. 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 ∈ V | v is incident on an edge of M}. A graph G with vertex set V = {a, b, c, d, g, h} and edge set E = {ab, bc, cd, cg, gh, hd, ad, ac, bd, ch, gd} is shown in Fig. 1. Let M1 = {ab, gh} and M2 = {ab, cd, gh}. Note that M1 is a matching as well as an induced matching in G, but M2 is a matching but not an ind
Data Loading...
