Maximum weight induced matching in some subclasses of bipartite graphs

Abstract

A subset $M\subseteq 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 \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 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, 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.

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\subseteq 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 \in 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 $M_{1}=\{ab,gh\}$ and $M_{2}=\{ab,cd,gh\}$. Note that $M_1$ is a matching as well as an induced matching in G, but $M_2$ is a matching but not an induced matching in G.

Fig. 1

Graph G

For a graph G, the Maximum Induced Matching problem is to find an induced matching of maximum cardinality in G. The maximum induced matching problem and its decision version are defined as follows:

Maximum Induced Matching problem (MIMP)

• Instance A graph $G=(V,E)$.

• Solution An induced matching M in G.

• Measure Cardinality of the set M.

Induced Matching Decision problem (IMDP)

• Instance A graph $G=(V,E)$ and a positive integer $k\le |V|$.

• Question Does there exist an induced matching M in G such that $|M|\ge k$?

The Maximum Induced Matching problem was introduced by Stockmeyer and Vazirani as “Risk-free Marriage problem” in 1982 (Stockmeyer and Vazirani 1982). The Induced Matching Decision problem is NP-complete for general graphs (Stockmeyer and Vazirani 1982), and remains so even for bipartite graphs (Cameron 1989) and k-regular graphs for $k\ge 4$ (Kobler and Rotics 2003; Zito 1999) (see Duckworth et al. 2005 for a survey). The Induced Matching Decision problem also remains NP-complete for bipartite graphs with maximum degree 3, and $C_{4}$-free bipartite graphs, which are two special subclasses of bipartite graphs (Lozin 2002). On the other hand, the Maximum Induced Matching problem is polynomial time solvable for many graph classes, for example, chordal graphs (Cameron 1989), chordal bipartite graphs (Cameron et al. 2003), trapezoid graphs, interval-dimension graphs and cocomparability graphs (Golumbic and Lewenstein 2000) etc.

Recently, Klemz and Rote studied the weighted version of the Maximum Induced Matching problem (Klemz and Rote 2017). The Maximum Weight Induced Matching problem is defined as follows:

Maximum Weight Induced Matching problem (MWIMP)

• Instance A graph $G=(V,E)$ with positive real weights w(e) for each $e\in E$.

• Solution An induced matching M in G.

• Measure Weight of M, that is $\displaystyle \sum _{e\in M}w(e)$.

In this paper, we study the Maximum weight Induced Matching problem for some subclasses of bipartite graphs: perfect elimination bipartite graphs, comb-convex bipartite graphs, star-convex bipartite graphs, circular-convex bipartite graphs, and triad-convex bipartite graphs. The class of circular-convex bipartite graphs was introduced by Liang and Blum (1995) and has been studied recently by researchers (see Liu 2014; Liu et al. 2015, 2014; Pandey and Panda 2019). The triad-convex bipartite graphs, star-convex bipartite graphs, and comb-convex bipartite graphs are studied in Chen et al. (2016), Jiang et al. (2013), Liu et al. (2015), Song et al. (2012), Wang et al. (2014). The main contributions of the paper are summarized below.

• 1. We show that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs.

• 2. We propose an $O(m^{2})$ time algorithm to solve the Maximum Weight Induced Matching problem in circular-convex bipartite graphs.

• 3. We propose an $O(mn^{6})$ time algorithm to solve the Maximum Weight Induced Matching problem in triad-convex bipartite graphs.

Our algorithms for the Maximum Weight Induced Matching problem in circular-convex bipartite graphs and triad-convex bipartite graphs are based on a polynomial time reduction for the Maximum Weight Induced Matching problem from these graph classes to convex bipartite graphs. The following result is already known for the Maximum Weight Induced Matching problem in convex bipartite graphs.

Theorem 1

(Klemz and Rote 2017) The Maximum Weight Induced Matching problem can be solved in $O(n+m)$ time in convex bipartite graphs.

A preliminary version of this paper for unweighted graphs appeared in Pandey et al. (2017).

2 Preliminaries

We consider only simple, connected and undirected graphs. In a graph $G=(V,E)$, the sets $N_{G}(v)=\{u\in V(G) \mid uv\in E\}$ and $N_{G}[v]=N_{G}(v)\cup \{v\}$ denote the open neighborhood and closed neighborhood of a vertex v, respectively. For a vertex v, the degree of v is the cardinality of open neighborhood of v, and is denoted by $d_{G}(v)$. A vertex v is called a pendant vertex if $d_{G}(v)=1$. For a set $S \subseteq V$ of the graph $G=(V,E)$, the subgraph of G induced by S is defined as $G[S]=(S,E_{S})$, where $E_{S}=\{xy \in E | x, y \in S\}$. For a set $E' \subseteq E$ of the graph $G=(V,E)$, the subgraph of G induced by $E'$ is defined as $G[E']=(V_{E'},E')$, where $V_{E'}=\{x \in V | x$ is incident on an edge of $E' \}$. A graph G is said to be chordal if every cycle in G of length at least four has a chord, that is, an edge joining two non-consecutive vertices of the cycle. A graph $G = (V,E)$ is said to be bipartite if V can be partitioned into two disjoint sets X and Y such that every edge of G joins a vertex in X to a vertex in Y, and such a partition (X, Y) of V is called a bipartition. A bipartite graph with bipartition (X, Y) of V is denoted by $G=(X,Y,E)$. A bipartite graph G is said to be chordal bipartite if every cycle of length at least 6 has a chord. A weighted graph is a graph $G=(V,E)$ together with a weight function $w:E \rightarrow R^{+}$ from the edge set to the set of positive real numbers.

Let $G=(X,Y,E)$ be a bipartite graph with $|X|=n_{1}$ and $|Y|=n_{2}$. G is called a convex bipartite graph if there exists a linear ordering < on X, say $x_{1}<x_{2}< \cdots < x_{n_{1}}$, such that for every vertex y in Y, $N_{G}(y)=\{x_{i},x_{i+1},\ldots ,x_{j}\}$ for $1\le i \le j \le n_{1}$, that is, vertices in $N_{G}(y)$ are consecutive in the linear ordering < on X. A set of consecutive vertices in the linear ordering < on X is called an interval. G is called a circular-convex bipartite graph if there exists a circular ordering $\prec$ on X, say $x_{1} \prec x_{2} \prec \cdots \prec x_{n_{1}} \prec x_{(n_{1}+1)}=x_{1}$, such that for every vertex y in Y, either $N_{G}(y)=\{x_{i},x_{i+1},\ldots ,x_{j}\}$ or $N_{G}(y)=\{x_{j},x_{j+1},\ldots ,x_{n_{1}},x_{1},\ldots ,x_{i}\}$ for $1 \le i \le j \le n_{1}$, that is, vertices in $N_{G}(y)$ are consecutive in the circular ordering $\prec$ on X. A set of consecutive vertices in the clock-wise direction in the circular ordering $\prec$ on X is called a circular arc and the first vertex and the last vertex in the circular arc are called the left end point and the right end point of the circular arc, respectively.

A tree with exactly one non-pendant vertex is a star. A comb is a graph obtained by attaching a pendant vertex (tooth) to every vertex of a path (backbone). A bipartite graph $G=(X,Y,E)$ is called a tree-convex bipartite graph, if a tree $T=(X,E^{X})$ can be defined such that for every vertex y in Y, the neighborhood of y induces a subtree of T. Tree-convex bipartite graphs are recognizable in linear time, and the associated tree T can also be constructed in linear-time (Bao and Zhang 2012). A tree-convex bipartite graph with a corresponding tree is shown in Fig. 2. For T a star, G is called a star-convex bipartite graph. For T a triad, that is, three paths with a common end-vertex, G is called a triad-convex bipartite graph. For T a comb, G is called a comb-convex bipartite graph. If T is a path, then G is called a convex bipartite graph. Note that both the definitions of convex bipartite graphs are equivalent.

Fig. 2

A tree-convex bipartite graph G with a corresponding tree T

For a bipartite graph $G=(X,Y,E)$, an edge $uv \in E$ is a bisimplicial edge if $N_{G}(u)\cup N_{G}(v)$ induces a complete bipartite subgraph in G. Let $(e_{1},e_{2},\ldots ,e_{k})$ be an ordering of pairwise non-adjacent edges (no two edges have a common end vertex) of G (not necessarily all edges of E). Let $S_{i}$ be the set of endpoints of edges $e_{1},e_{2},\ldots ,e_{i}$ and let $S_{0}=\emptyset$. Ordering $(e_{1},e_{2},\ldots ,e_{k})$ is a perfect edge elimination ordering for G if $G[(X\cup Y){\setminus } S_{k}]$ has no edge and each edge $e_{i}$ is bisimplicial in the remaining induced subgraph $G[(X\cup Y){\setminus } S_{i-1}]$. A graph G is called a perfect elimination bipartite graph if G admits a perfect edge elimination ordering. The class of perfect elimination bipartite graphs was introduced by Golumbic and Gauss (1978). The hierarchial relationship between subclasses of bipartite graphs is shown in Fig. 3.

Fig. 3

The hierarchical relationship between subclasses of bipartite graphs

3 NP-completeness results

In this section, we study the NP-completeness of the Induced Matching Decision problem. The Induced Matching Decision problem is NP-complete for bipartite graphs. We strengthen the complexity result of the Induced Matching Decision problem, by showing that it remains NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs, three important subclasses of the class of bipartite graphs.

3.1 Star-convex bipartite graphs

In this subsection, we prove the hardness result for the Induced Matching Decision problem in star-convex bipartite graphs. Recall that a bipartite graph $G=(X,Y,E)$ is called a star-convex bipartite graph, if a star $T=(X,E^{X})$ can be defined on partition X such that for every vertex y in Y, the neighborhood of y induces a connected subgraph of T. A star-convex bipartite graph with a corresponding star is shown in Fig. 4.

Fig. 4

A star-convex bipartite graph G with a corresponding star T

The following necessary and sufficient condition for a bipartite graph to be a star-convex bipartite graph will be useful in the polynomial time reduction.

Lemma 1

(Pandey and Panda 2019) A bipartite graph $G=(X,Y,E)$ is a star-convex bipartite graph if and only if there exists a vertex x in X such that every vertex y in Y is either a pendant vertex or is adjacent to x.

Theorem 2

The Induced Matching Decision problem is NP-complete for star-convex bipartite graphs.

Proof

Clearly, the Induced Matching Decision problem is in NP for star-convex bipartite graphs. To show the NP-completeness, we give a polynomial time reduction from the Induced Matching Decision problem for bipartite graphs, which is already known to be NP-complete (Cameron 1989).

Given a bipartite graph $G=(X,Y,E)$, we construct a star-convex bipartite graph $H=(X_{H},Y_{H},E_{H})$ in the following way: $X_{H}=X\cup \{u\}$, $Y_{H}=Y$, and $E_{H}=E\cup \{uy\mid y\in Y_{H}\}$. The construction of H from G is shown in Fig. 5. By Lemma 1, it is clear that the constructed graph H is a star-convex bipartite graph (as every vertex in $Y_{H}$ is adjacent to the vertex $u\in X_{H}$). Now, the following claim is sufficient to complete the proof of the theorem. $\square$

Fig. 5

An illustration of the construction of H from G

Claim

G has an induced matching of size at least k if and only if H has an induced matching of size at least k.

Proof

Let M be an induced matching in G and $|M|\ge k$. Then M is also an induced matching in H (As, in the construction of H from G, we have not added any edge whose both endpoints are the vertices of G). Hence H contains an induced matching of size at least k.

Conversely, let $M'$ be an induced matching in H, and $|M'|\ge k$. If $M'$ saturates u, that is, $M'$ contains an edge, say $e=uy_{i}$, whose one endpoint is u, then $|M'|=1$. If any other edge $x_{r}y_{s}\in M'$, then $M'$ will not be an induced matching in H (as $uy_{s}\in E(H)$). In this case, G contains an induced matching with at least one edge. Otherwise, if $M'$ does not contain any edge whose one of the endpoints is u, then $M'\subseteq E(G)$. Also, since $M'$ is an induced matching in H and G is a subgraph of H, $M'$ is also an induced matching in G. Hence G contains an induced matching of size at least k. $\square$

Hence, the theorem is proved. $\square$

3.2 Comb-convex bipartite graphs

In this subsection, we show that the Induced Matching Decision problem remains NP-complete for comb-convex bipartite graphs, which is a subclass of tree-convex bipartite graphs. Recall that a bipartite graph $G=(X,Y,E)$ is called a comb-convex bipartite graph, if a comb $T=(X,E^{X})$ can be defined on partition X such that for every vertex y in Y, the neighborhood of y induces a connected subgraph of T. A comb-convex bipartite graph with a corresponding comb is shown in Fig. 6.

Fig. 6

A comb-convex bipartite graph G with a corresponding comb T

Theorem 3

The Induced Matching Decision problem is NP-complete for comb-convex bipartite graphs.

Proof

Clearly, the Induced Matching Decision problem is in NP for comb-convex bipartite graphs. To show the NP-completeness, we give a polynomial time reduction from the Induced Matching Decision problem for bipartite graphs, which is already known to be NP-complete (Cameron 1989).

Given a bipartite graph $G=(X,Y,E)$, we construct a comb-convex bipartite graph $H=(X_{H},Y_{H},E_{H})$ in the following way: $X_{H}=X\cup X'$, where $X'$ contains a copy of x for each $x \in X$, $Y_{H}=Y$ and $E_{H}=E\cup \{x'y \mid x' \in X'$ and $y \in Y\}$. Note that H can be constructed from G in polynomial time. The construction of H from G is shown in Fig. 7. It is easy to see that H is a comb convex bipartite graph if $X'$ is taken as the backbone and X is taken as the teeth of the comb. $\square$

Fig. 7

An illustration of the construction of H from G

Claim

G has an induced matching of size at least k if and only if H has an induced matching of size at least k, where $k>1$.

Proof

Let M be an induced matching in G of size at least k. Then, M is also an induced matching in H. Hence, H has an induced matching of size at least k.

Conversely, assume that M is an induced matching in H of size at least k, $k>1$. Observe that if a vertex $x'\in X'$ is saturated by M, that is $x'y\in M$ for some $y\in Y$, then M does not contain any other edge of H. Since $x'$ is adjacent to every vertex $y \in Y$, for any edge $x_{i}y_{i}$, where $x_{i}\in X_{H}$ and $y_{i}\in Y$, $x'y_{i}$ is also an edge in H. Hence, the edge $x_{i}y_{i}$ can not be present in M and |M| should be 1.

As $|M|\ge k>1$, any vertex $x'\in X'$ is not saturated by M, that is, M does not have any edge from $E'$. In this case, M is also an induced matching in G, and $|M|\ge k$. $\square$

Hence, the theorem is proved. $\square$

3.3 Perfect elimination bipartite graphs

In this subsection, we prove the hardness result for the Induced Matching Decision problem in perfect elimination bipartite graphs. Since the class of perfect elimination bipartite graphs is a subclass of bipartite graphs, and a superclass of chordal bipartite graphs, our result reduces the complexity gap between bipartite graphs and chordal bipartite graphs.

A perfect elimination bipartite graph with a perfect edge elimination ordering $\sigma =(x_4y_2,x_{2}y_{1})$ is shown in Fig. 8.

Fig. 8

A perfect elimination bipartite graph

Theorem 4

The Induced Matching Decision problem is NP-complete for perfect elimination bipartite graphs.

Proof

Clearly, the Induced Matching Decision problem is in NP for perfect elimination bipartite graphs. To show the NP-completeness, we give a polynomial time reduction from the Induced Matching Decision problem for bipartite graphs, which is already known to be NP-complete (Cameron 1989).

Given a bipartite graph $G=(X,Y,E)$ where $X=\{x_{1},x_{2},\ldots ,x_{n_{1}}\}$ and $Y=\{y_{1},y_{2},\ldots ,y_{n_{2}}\}$, we construct a bipartite graph $H=(X_{H},Y_{H},E_{H})$ in the following way: For each $x_{i}\in X$, add a path $P_{i}=x_{i},w_{i},z_{i},t_{i}$ of length 3. Formally $X_{H}=X\cup \{z_{i} \mid 1\le i \le n_{1}\}$, $Y_{H}=Y\cup \{w_{i},t_{i}\mid 1\le i \le n_{1}\}$, and $E_{H}=E\cup \{x_{i}w_{i},w_{i}z_{i},z_{i}t_{i}\mid 1\le i \le n_{1}\}$. $\square$

Fig. 9

An illustration of the construction of H from G

Figure 9 illustrates the construction of H from G. Clearly H is a perfect elimination bipartite graph and $(z_{1}t_{1},z_{2}t_{2},\ldots ,z_{n_{1}}t_{n_{1}}, x_{1}w_{1},x_{2}w_{2},\ldots ,x_{n_{1}}w_{n_{1}})$ is a perfect edge elimination ordering for H. Now, the following claim is sufficient to complete the proof of the theorem.

Claim

G has an induced matching of size at least k if and only if H has an induced matching of size at least $k+n_{1}$.

Proof

Let M be an induced matching in G, and $|M|\ge k$. Then $M'=M\cup \{z_{i}t_{i}\mid 1\le i \le n_{1}\}$ is an induced matching in H, and $|M'|\ge k+n_{1}$. Hence H has an induced matching of size at least $k+n_{1}$.

Conversely, let $M'$ be an induced matching in H, and $|M'|\ge k+n_{1}$. Then for each i, $1\le i \le n_{1}$, $|M'\cap \{x_{i}w_{i},w_{i}z_{i},z_{i}t_{i}\mid 1\le i \le n_{1}\}|\le 1$, that is, at most one edge from the set $\{x_{i}w_{i},w_{i}z_{i},z_{i}t_{i}\}$ belongs to $M'$. Define $S=\{x_{i}w_{i},w_{i}z_{i},z_{i}t_{i}\mid 1\le i \le n_{1}\}$. Also define $M=M'{\setminus } S$. Then $|M|\ge k$. Since $M \subseteq M'$, M is also an induced matching in H. Also, G is a subgraph of H, and $M\subseteq E_{G}$. Hence M is also an induced matching in G. Hence G contains an induced matching of size at least k. $\square$

Hence, the theorem is proved. $\square$

4 Circular-convex bipartite graph

In this section, we propose a polynomial time algorithm to compute a maximum weight induced matching in a weighted circular-convex bipartite graph. Recall that a circular-convex bipartite graph is a bipartite graph that exhibits a circular ordering $\prec$ on X, say $x_{1} \prec x_{2} \prec \cdots \prec x_{n_{1}} \prec x_{(n_{1}+1)}=x_{1}$, such that for every vertex y in Y, either $N_{G}(y)=\{x_{i},x_{i+1},\ldots ,x_{j}\}$ or $N_{G}(y)=\{x_{j},x_{j+1},\ldots ,x_{n_{1}},x_{1},\ldots ,x_{i}\}$ for $1 \le i \le j \le n_{1}$, that is, vertices in $N_{G}(y)$ are consecutive in the circular ordering $\prec$ on X. A circular-convex bipartite graph with a corresponding circular ordering $x_{1} \prec x_{2} \prec \cdots \prec x_{8} \prec x_{1}$ is shown in Fig. 10.

Fig. 10

A circular-convex bipartite graph

Our algorithm is based on the reduction from circular-convex bipartite graphs to convex bipartite graphs. Below we first give a construction of a convex bipartite graph from a given circular-convex bipartite graph.

Construction 1 Let $G=(X,Y,E)$ be a weighted circular-convex bipartite graph with positive edge weights w(e) for each $e\in E$. Let $|X|=n_{1}$ and $|Y|=n_{2}$. Let $e=x_{i}y_{j}\in E$. Without loss of generality, we can always assume a circular ordering $\prec$ on X, say $x_{1} \prec x_{2} \prec \cdots \prec x_{n_{1}} \prec x_{(n_{1}+1)}=x_{1}$, such that for every vertex y in Y, $N_{G}(y)$ is a circular arc. Now, construct the graph $G_{e}=(X_{e},Y_{e},E_{e})$ as follows: $X_{e}=X {\setminus } N_{G}(y_{j})$, $Y_{e}=Y {\setminus } N_{G}(x_{i})$, and $E_{e}=\{xy\in E \mid x\in X_{e}, y\in Y_{e}\}$.

Lemma 2

$G_{e}$ is a convex bipartite graph.

Proof

Let $G'=(X',Y',E')$ be the graph constructed from G by removing $x_{i}$ and all its neighbors. Now, we define a linear ordering < on the vertices of $X'$ as follows, $x_{i+1}<x_{i+2}<\cdots<x_{n_{1}}<x_{1}<\cdots <x_{i-1}$. Since we have removed all the neighbors of $x_{i}$, none of the vertex in $Y'$ is adjacent to both $x_{i-1}$ and $x_{i+1}$. Therefore for every vertex $y\in Y'$, $N_{G'}(y)$ is an interval on $X'$. Hence $G'$ is a convex bipartite graph. Also, observe that $G_{e}$ is a subgraph of $G'$. Since, $G'$ is a convex bipartite graph, $G_{e}$ is also a convex bipartite graph. $\square$

Lemma 3

Let M be a maximum weight induced matching in G and $e\in M$. Let $M_{e}$ be a maximum weight induced matching in $G_{e}$. Then $M'=M_{e}\cup \{e\}$ is also a weighted induced matching in G and $w(M)=w(M')$. In other words, $M'$ is a maximum weight induced matching in G.

Proof

Note that $G_{e}$ is constructed from G by removing some of its vertices. Hence every weighted induced matching in $G_{e}$ is also a weighted induced matching in G. Therefore $M_{e}$ is also a weighted induced matching in G. Also, there is no edge in G, which joins an endpoint of e and an endpoint of some edge of $G_{e}$, which implies that there is no edge in G which joins an endpoint of e and an endpoint of some edge in $M_{e}$. Hence $M'=M_{e}\cup \{e\}$ is also a weighted induced matching in G. Since M is a maximum weight induced matching in G, $w(M)\ge w(M')$. To complete the proof, we need to show that $w(M)\le w(M')$.

Let $x_{i},y_{j}$ are the end points of the edge e, and $S=N_{G}(x_{i})\cup N_{G}(y_{j})$. Then $M{\setminus } \{e\}$ does not contain any edge incident on any vertex in S, otherwise M is not a weighted induced matching in G. Hence $M{\setminus } \{e\}$ is a weighted induced matching in $G[(X\cup Y){\setminus } (N_{G}(x_{i})\cup N_{G}(y_{j}))]$, which is exactly the graph $G_{e}$. Since $M_{e}$ is a maximum weight induce matching in $G_{e}$, $w(M_{e})\ge w(M)-w(e)$. Therefore $w(M)\le w(M_{e})+w(e)=w(M')$.

Hence $w(M)=w(M')$, and $M'$ is also a maximum weight induced matching in G. $\square$

The detailed algorithm for finding a maximum weight induced matching in a weighted circular-convex bipartite graph G is given in Fig. 11.

Fig. 11

Algorithm to compute a maximum weight induced matching in a circular-convex bipartite graph

The following theorem directly follows from the Lemma 3 and the algorithm Weighted-Induced-M-Circular-Convex.

Theorem 5

A maximum weight induced matching in a weighted circular-convex bipartite graph can be computed in $O(m^{2})$ time.

Proof

Since for each edge $e\in E$, we are computing a maximum weight induced matching in graph $G_{e}$. The time taken by algorithm is atmost $O(m \times g(n))$, where g(n) is the time complexity of computing a maximum weight induced matching in a convex bipartite graph. By Theorem 1, it is clear that $g(n)=O(m)$. So, the overall time complexity of Weighted-Induced-M-Circular-Convex is at most $O(m^{2})$. $\square$

5 Triad-convex bipartite graph

In this section, we propose a polynomial time algorithm to compute a maximum weight induced matching in a weighted triad-convex bipartite graph.

Let $G=(X,Y,E)$ be a weighted triad-convex bipartite graph with positive edge weights w(e) for each $e\in E$ and $T=(X,E^{X})$ be a triad defined on X, such that for every vertex $y\in Y$, $T[N_{G}(y)]$ is a connected subgraph of T. Let $X=\{x_{0}\}\cup X_{1}\cup X_{2}\cup X_{3}$ be such that for each i, $1\le i \le 3$, $X_{i}=\{x_{i,1},x_{i,2},\ldots ,x_{i,n_{i}}\}$. Also suppose that $x_{i,0}=x_{0}$ for all i, $1\le i \le 3$. For each i, $1\le i \le 3$, let $P_{i}=x_{0},x_{i,1},x_{i,2},\ldots ,x_{i,n_{i}}$ be a path in $T=(X,E^{X})$. Note that $x_{0}$ is a common vertex in all the three paths $P_{1}$, $P_{2}$, and $P_{3}$. A triad-convex bipartite graph with a corresponding triad is shown in Fig. 12.

Fig. 12

A triad-convex bipartite graph G with a corresponding triad T

Let $G=(X,Y,E)$ be a weighted triad-convex bipartite graph with $x_0$ as the common vertex of the three paths of a triad. Note that a maximum weight induced matching of G may saturate $x_0$ or may not saturate $x_0$. Among all the weighted induced matchings of G not saturating $x_0$, let $M_1$ be a maximum weight induced matching. Similarly, among all the weighted induced matchings of G saturating $x_0$, let $M_2$ be a maximum weight induced matching. If weight of $M_1$ is at least the weight of $M_2$, then $M_1$ is a maximum weight induced matching of G. Otherwise, $M_2$ is a maximum weight induced matching of G. So, it is enough to find a maximum weight induced matching of G saturating $x_0$ and a maximum weight induced matching of G not saturating $x_0$. We first find a maximum weight induced matching M of G not saturating $x_0$. We first show that in this case, M can saturate at most 3 neighbors of $x_0$. This allows us to consider only four cases: M does not saturate any neighbor of $x_0$, M saturates exactly one neighbor of $x_0$, M saturates exactly two neighbors of $x_0$ and M saturates exactly three neighbors of $x_0$. In each of these cases, we construct a convex bipartite graph $G'$ from G and we compute a maximum weight induced matching of $G'$ using the known algorithm given in Klemz and Rote (2017). We then use this matching to find a maximum weight induced matching of G. Similarly, we solve the case when M saturates $x_0$. So, in each of these cases, we first construct a convex bipartite graph $G'$ from G and we find a maximum weight induced matching $M'$ of $G'$ using the known algorithm given in Klemz and Rote (2017). We then construct a maximum weight induced matching of G by suitably adding some edges which depends on the corresponding case. The details are given below through a series of lemmas.

Lemma 4

Let M be a maximum weight induced matching in G. Let M does not saturate $x_{0}$, but M saturates some of the neighbors of $x_{0}$. Then M saturates at most 3 neighbors of $x_{0}$.

Proof

We prove it by contradiction. Suppose M saturates 4 neighbors of $x_{0}$, say $y_{j_{1}}$, $y_{j_{2}}$, $y_{j_{3}}$, and $y_{j_{4}}$. Also suppose that $\{x_{j_{1}}y_{j_{1}},x_{j_{2}}y_{j_{2}}, x_{j_{3}}y_{j_{3}}, x_{j_{4}}y_{j_{4}}\} \subseteq M$. Then at least two vertices of the set $\{x_{j_{1}},x_{j_{2}},x_{j_{3}},x_{j_{4}}\}$ belong to the same path $P_{i}$ for some i, $1\le i \le 3$ (see Fig. 13). Without loss of generality, we may assume that $x_{j_{1}},x_{j_{2}} \in P_{1}$. Also assume that the distance between $x_{0}$ and $x_{j_{1}}$ is less than the distance between $x_{0}$ and $x_{j_{2}}$ in path $P_{1}$. Notice that $y_{j_{2}}$ is adjacent to $x_{0}$ as well as $x_{j_{2}}$. Also, by the definition of triad-convex bipartite graph, $T[N_{G}(y_{j_{2}})]$ is a subtree of T. Hence $y_{j_{2}}$ must be adjacent to $x_{j_{1}}$. But by the definition of induced matching, if $x_{j_{1}}y_{j_{1}}$ and $x_{j_{2}}y_{j_{2}}$ are edges in an induced matching, then $x_{j_{1}}y_{j_{2}}\notin E$. So, we arrive at a contradiction. $\square$

Fig. 13

A triad-convex bipartite graph

Now let M be a maximum weight induced matching in G, then one of the following possibilities must occur:

(a):

M does not saturate any vertex in $N_{G}[x_{0}]$.

(b):

$x_{0}$ is saturated by M.

(c):

M does not saturate $x_{0}$ but M saturates at most 3 neighbors of $x_{0}$. In this case, again three possibilities arise.

• M saturates exactly one neighbor of $x_{0}$.

• M saturates exactly two neighbors of $x_{0}$.

• M saturates exactly three neighbors of $x_{0}$.

Now we discuss in detail that how to find a maximum weight induced matching M in G in each of the above cases:

Case 1 M does not saturate any vertex in $N_{G}[x_{0}]$.

We construct a weighted convex bipartite graph $G_{0}=(X_{0},Y_{0},E_{0})$ in the following way:

Construction 2 $G_{0}=G[V{\setminus } N_{G}[x_{0}]]$.

Lemma 5

$G_{0}$ is a convex bipartite graph.

Proof

$G_{0}$ is constructed by removing the vertex $x_{0}$ and all its neighbors from G. Now, we define a linear ordering < on the vertices of $X_{0}$ as follows, $x_{1,1}<x_{1,2}<\cdots<x_{1,n_{1}}<x_{2,1}<x_{2,2}<\cdots<x_{2,n_{2}}< x_{3,1}<x_{3,2}<\cdots <x_{3,n_{3}}$. Then for every vertex $y \in Y_{0}$, $N_{G_{0}}(y)$ is an interval on $X_{0}$. Hence $G_{0}$ is a convex bipartite graph. $\square$

Lemma 6

Let $M_{0}$ be a maximum weight induced matching in $G_{0}$. Then $M_{0}$ is a weighted induced matching in G. Moreover, if there exists a maximum weight induced matching M in G which does not saturate any vertex in $N_{G}[x_{0}]$ then $w(M)=w(M_{0})$. In other words, $M_{0}$ is a maximum weight induced matching in G.

Proof

Note that $G_{0}$ is a subgraph of G, and there does not exist any edge $e\in E(G){\setminus } E(G_{0})$ such that both the end points of e are in $G_{0}$. Hence every induced matching in $G_{0}$ is also an induced matching in G. So, $M_{0}$ is an induced matching in G.

Now, if M is a maximum weight induced matching in G and M does not saturate any vertex in $N_{G}[x_{0}]$, then M is also a maximum weight induced matching in the graph obtained from G by removing $x_{0}$ and all its neighbors, which is exactly $G_{0}$. Hence $w(M)=w(M_{0})$, and $M_{0}$ is also a maximum weight induced matching in G. $\square$

Case 2 $x_{0}$ is saturated by M, that is $x_{0}y\in M$ for some $y\in N_{G}(x_{0})$.

We construct a weighted convex bipartite graph $G_{0}^{y}$ in the following way:

Construction 3 $G_{0}^{y}=G[V{\setminus } (N_{G}(x_{0})\cup N_{G}(y))]$.

Lemma 7

$G_{0}^{y}$ is a weighted convex bipartite graph.

Proof

Since $G_{0}^{y}$ is a subgraph of $G_{0}$, and $G_{0}$ is a convex bipartite graph (by Lemma 5), $G_{0}^{y}$ is also a convex bipartite graph. $\square$

Lemma 8

Let $M_{0}$ be a maximum weight induced matching in $G_{0}^{y}$. Then $M_{0}\cup \{x_{0}y\}$ is a weighted induced matching in G. Moreover, if there exists a maximum weight induced matching M in G containing the edge $x_{0}y$ then $w(M)=w(M_{0})+w(x_{0}y)$.

Proof

Clearly $M_{0}$ is a induced matching in G, as $G_{0}^{y}$ is a subgraph of G, and no edge $e \in E(G){\setminus } E(G_{0}^{y})$ contains both end points in $G_{0}^{y}$. Also, notice that the distance of any vertex, say v saturated by $M_{0}$ is at least 2 from $x_{0}$ as well as y in G. Hence $M_{0}\cup \{x_{0}y\}$ is also a weighted induced matching in G.

Next, if M is a maximum weight induced matching in G and $x_{0}y\in M$. Then $M{\setminus } \{x_{0}y\}$ must be maximum weight induced matching in $G[V{\setminus } (N_{G}(x_{0})\cup N_{G}(y))]$, which is exactly $G_{0}^{y}$. Hence $w(M_{0})=w(M)-w(x_{0}y)$, that is, $w(M)=w(M_{0})+w(x_{0}y)$. Hence $M_{0}\cup \{x_{0}y\}$ is also a maximum weight induced matching in G. $\square$

Case 3 M does not saturate $x_{0}$ but M saturates at most 3 neighbors of $x_{0}$.

Again the following three cases arise:

Subcase 3.1 M saturates exactly one neighbor $y_{i}$ of $x_{0}$, that is, $xy_{i}\in M$ for some $x\in N_{G}(y_{i}){\setminus } \{x_{0}\}$.

We construct a weighted convex bipartite graph $G_{x}^{y_{i}}$ in the following way:

Construction 4 First remove all the neighbors of $x_{0}$ other than $y_{i}$ from G. Let us call the resultant graph $G'$. Now define $G_{x}^{y_{i}}=G'[V(G'){\setminus } (N_{G'}(x)\cup N_{G'}(y_{i}))]$.

Lemma 9

$G_{x}^{y_{i}}$ is a weighted convex bipartite graph.

Proof

Since $G_{x}^{y_{i}}$ is a subgraph of $G_{0}$, and $G_{0}$ is a convex bipartite graph (by Lemma 5), $G_{x}^{y_{i}}$ is also a convex bipartite graph. $\square$

Lemma 10

Let $M_{i}$ be a maximum weight induced matching in $G_{x}^{y_{i}}$. Then $M_{i}\cup \{xy_{i}\}$ is a weighted induced matching in G. Moreover, if there exists a maximum weight induced matching M in G such that M does not saturate $x_{0}$, and M saturates exactly one neighbor $y_{i}$ of $x_{0}$, and $xy_{i}\in M$, then $w(M)=w(M_{i})+w(xy_{i})$. In otherwords, $M_{i}\cup \{xy_{i}\}$ is a maximum weight induced matching in G.

Proof

Clearly, $M_{i}$ is also a weighted induced matching in G. Also every vertex of $G_{x}^{y_{i}}$ is at distance at least two from x as well as $y_{i}$. Hence every vertex which is saturated by $M_{i}$ is at distance at least two from both x and $y_{i}$. Hence $M_{i}\cup \{xy_{i}\}$ is a weighted induced matching in G.

Now, if M is a maximum weight induced matching in G, and M does not saturate $x_{0}$, and M saturates exactly one neighbor $y_{i}$ of $x_{0}$, and $xy_{i}\in M$, then M is also a maximum weight induced matching in $G'=G[V{\setminus } (N_{G}(x_{0}){\setminus }\{y_{i}\})]$. Also, $M{\setminus } \{xy_{i}\}$ is a maximum weight induced matching in $G'[V(G'){\setminus } (N_{G'}(x)\cup N_{G'}(y_{i}))]$, which is exactly $G_{x}^{y_{i}}$. Hence $w(M_{i})=w(M)-w(xy_{i})$, that is, $w(M)=w(M_{i})+w(xy_{i})$. Therefore, $M_{i}\cup \{xy_{i}\}$ is a maximum weight induced matching in G. $\square$

Subcase 3.2 M saturates exactly two neighbors $y_{i},y_{j}$ of $x_{0}$, that is, $x_{r}y_{i},x_{s}y_{j}\in M$ where $x_{r}\in N_{G}(y_{i}){\setminus } N_{G}(y_{j})$, and $x_{s}\in N_{G}(y_{j}){\setminus } N_{G}(y_{i})$.

We construct a weighted convex bipartite graph $G_{x_{r}x_{s}}^{y_{i}y_{j}}$ in the following way:

Construction 5 First remove all the neighbors of $x_{0}$ other than $y_{i},y_{j}$ from G. Let us call the resultant graph $G'$. Now define $G_{x_{r}x_{s}}^{y_{i}y_{j}}=G'[V(G'){\setminus } (N_{G'}(x_{r})\cup N_{G'}(x_{s})\cup N_{G'}(y_{i})\cup N_{G'}(y_{j}))]$.

Lemma 11

$G_{x_{r}x_{s}}^{y_{i}y_{j}}$ is a weighted convex bipartite graph.

Proof

Since $G_{x_{r}x_{s}}^{y_{i}y_{j}}$ is a subgraph of $G_{0}$, and $G_{0}$ is a convex bipartite graph (by Lemma 5), $G_{x_{r}x_{s}}^{y_{i}y_{j}}$ is also a convex bipartite graph. $\square$

Lemma 12

Let $M_{ij}$ be a maximum weight induced matching in $G_{x_{r}x_{s}}^{y_{i}y_{j}}$. Then $M_{ij}\cup \{x_{r}y_{i},x_{s}y_{j}\}$ is a weighted induced matching in G. Moreover, if there exists a maximum weight induced matching M in G such that M does not saturate $x_{0}$, and M saturates exactly two neighbors $y_{i},y_{j}$ of $x_{0}$, and $x_{r}y_{i},x_{s}y_{j}\in M$, then $w(M)=w(M_{ij})+w(x_{r}y_{i})+w(x_{s}y_{j})$. In other words, $M_{ij}\cup \{x_{r}y_{i},x_{s}y_{j}\}$ is a maximum weight induced matching in G.

Proof

Since $G_{x_{r}x_{s}}^{y_{i}y_{j}}$ is constructed from G by removing some of its vertices, $M_{ij}$ is also a weighted induced matching in G. Observe that there is no edge in G joining the two edges $x_{r}y_{i}$ and $x_{s}y_{j}$. Also, in graph G every vertex saturated by $M_{ij}$ is at distance at least 2 from every vertex in $\{x_{r},x_{s},y_{i},y_{j}\}$. Hence $M_{ij}\cup \{x_{r}y_{i},x_{s}y_{j}\}$ is a weighted induced matching in G.

Now, if M is a maximum weight induced matching in G, and M does not saturate $x_{0}$, and M saturates exactly two neighbors $y_{i},y_{j}$ of $x_{0}$, and $x_{r}y_{i},x_{s}y_{j}\in M$, then M is also a maximum weight induced matching in $G'=G[V{\setminus } (N_{G}(x_{0}){\setminus }\{y_{i},y_{j}\})]$. Also, $M{\setminus } \{x_{r}y_{i},x_{s}y_{j}\}$ is a maximum weight induced matching in $G'[V(G'){\setminus } (N_{G'}(x_{r})\cup N_{G'}(x_{s}) \cup N_{G'}(y_{i})\cup N_{G'}(y_{j}))]$, which is exactly $G_{x_{r}x_{s}}^{y_{i}y_{j}}$. Hence $w(M_{ij})=w(M)-w(x_{r}y_{i})-w(x_{s}y_{j})$, that is, $w(M)=w(M_{ij})+w(x_{r}y_{i})+w(x_{s}y_{j})$. Therefore, $M_{ij}\cup \{x_{r}y_{i},x_{s}y_{j}\}$ is a maximum weight induced matching in G. $\square$

Subcase 3.3 M saturates exactly three neighbors $y_{i},y_{j},y_{k}$ of $x_{0}$, that is, $x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\in M$ where $x_{r}\in N_{G}(y_{i}){\setminus } (N_{G}(y_{j})\cup N_{G}(y_{k}))$, and $x_{s}\in N_{G}(y_{j}){\setminus } (N_{G}(y_{i})\cup N_{G}(y_{k}))$, and and $x_{t}\in N_{G}(y_{k}){\setminus } (N_{G}(y_{i})\cup N_{G}(y_{j}))$.

We construct a weighted convex bipartite graph $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$ in the following way:

Construction 6 First remove all the neighbors of $x_{0}$ other than $y_{i},y_{j},y_{k}$ from G. Let us call the resultant graph $G'$. Now define $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}=G'[V(G'){\setminus } (N_{G'}(x_{r})\cup N_{G'}(x_{s})\cup N_{G'}(x_{t})\cup N_{G'}(y_{i})\cup N_{G'}(y_{j})\cup N_{G'}(y_{k}))]$.

Fig. 14

Algorithm to compute a maximum weight induced matching in a triad-convex bipartite graph

Lemma 13

$G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$ is a weighted convex bipartite graph.

Proof

Since $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$ is a subgraph of $G_{0}$, and $G_{0}$ is a convex bipartite graph (by Lemma 5), $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$ is also a convex bipartite graph. $\square$

Lemma 14

Let $M_{ijk}$ be a maximum weight induced matching in $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$. Then $M_{ijk}\cup \{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$ is a weighted induced matching in G. Moreover, if there exists a maximum weight induced matching M in G such that M does not saturate $x_{0}$, and M saturates exactly three neighbors $y_{i},y_{j},y_{k}$ of $x_{0}$, and $\{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}\subseteq M$, then $w(M)=w(M_{ijk})+w(x_{r}y_{i})+w(x_{s}y_{j})+w(x_{t}y_{k})$. In other words, $M_{ijk}\cup \{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$ is a maximum weight induced matching in G.

Proof

Since $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$ is constructed from G by removing some of its vertices, $M_{ijk}$ is also a weighted induced matching in G. Observe that there is no edge in G joining any two edges in the set $\{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$. Also, in graph G every vertex saturated by $M_{ijk}$ is at distance at least 2 from every vertex in $\{x_{r},x_{s},x_{t},y_{i},y_{j},y_{k}\}$. Hence $M_{ijk}\cup \{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$ is a weighted induced matching in G.

Now, if M is a maximum weight induced matching in G, and M does not saturate $x_{0}$, and M saturates exactly three neighbors $y_{i},y_{j},y_{k}$ of $x_{0}$, and $x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\in M$, then M is also a maximum weight induced matching in $G'=G[V{\setminus } (N_{G}(x_{0}){\setminus }\{y_{i},y_{j},y_{k}\})]$. Also, $M{\setminus } \{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$ is a maximum weight induced matching in $G'[V(G'){\setminus } (N_{G'}(x_{r})\cup N_{G'}(x_{s})\cup N_{G'}(x_{t}) \cup N_{G'}(y_{i})\cup N_{G'}(y_{j}) \cup N_{G'}(y_{k}))]$, which is exactly $G_{x_{r}x_{s}x_{t}}^{y_{i}y_{j}y_{k}}$. Hence $w(M_{ijk})=w(M)-w(x_{r}y_{i})-w(x_{s}y_{j})-w(x_{t}y_{k})$, that is, $w(M)=w(M_{ijk})+w(x_{r}y_{i})+w(x_{s}y_{j})+w(x_{t}y_{k})$. Therefore, $M_{ijk}\cup \{x_{r}y_{i},x_{s}y_{j},x_{t}y_{k}\}$ is a maximum weight induced matching in G. $\square$

Based on the above discussion, the detailed algorithm for finding a maximum weight induced matching in a weighted triad-convex bipartite graph G is given in Fig. 14.

The following theorem directly follows from Lemmas 6, 8, 10, 12, 14 and the algorithm Weighted-Induced-M-Triad-Convex.

Theorem 6

A maximum weight induced matching in a weighted triad-convex bipartite graph can be computed in $O(mn^{6})$ time.

Proof

The time taken by algorithm is atmost $O(\varDelta ^{6} \times g(n))$, where g(n) is the time complexity of computing a maximum weight induced matching in a convex bipartite graph. By Theorem 1, it is clear that $g(n)=O(m)$. So, the overall time complexity of Weighted-Induced-M-Triad-Convex is at most $O(mn^{6})$. $\square$

6 Conclusion

In this paper, we prove the NP-completeness result for the Induced Matching Decision problem in the following subclasses of bipartite graphs: star-convex bipartite graphs, comb-convex bipartite graphs and perfect elimination bipartite graphs. On the positive side, we propose an $O(m^{2})$-time algorithm for the Maximum Weight Induced Matching problem in circular-convex bipartite graphs. We also propose an $O(mn^{6})$-time algorithm for the Maximum Weight Induced Matching problem in triad-convex bipartite graphs. Further, it will be interesting to study algorithms with better time complexity for the Maximum Weight Induced Matching problem in these graph classes.