On Two Variants of Induced Matchings

Abstract

A matching M in a graph G is an induced matching if the subgraph of G induced by M is the same as the subgraph of G induced by $S = \{v \in V(G)\mid v$ is incident on an edge of $M\}$. Given a graph G and a positive integer k, Induced Matching asks whether G has an induced matching of cardinality at least k. An induced matching M is maximal if it is not properly contained in any other induced matching of G. Given a graph G, Min-Max-Ind-Matching is the problem of finding a maximal induced matching M in G of minimum cardinality. Given a bipartite graph $G=(X\uplus Y,E(G))$, Saturated Induced Matching asks whether there exists an induced matching in G that saturates every vertex in Y. In this paper, we study Min-Max-Ind-Matching and Saturated Induced Matching. First, we strengthen the hardness result of Min-Max-Ind-Matching by showing that its decision version remains ${\textsf{NP}}$-complete for perfect elimination bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. Then, we show the hardness difference between Induced Matching and Min-Max-Ind-Matching. Finally, we propose a linear-time algorithm to solve Saturated Induced Matching.

1 Introduction

All graphs considered in this paper are simple, finite, connected, and undirected. For a graph G, let V(G) denote its vertex set, and E(G) denote its edge set. A matching M in a graph G is 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(G)\mid v$ is incident on an edge of $M\}$. An induced matching M is maximal if M is not properly contained in any other induced matching of G. Given a graph G, Min-Max-Ind-Matching asks to find a maximal induced matching M of minimum cardinality in G. Formally, the decision version of Min-Max-Ind-Matching is defined as follows:

The induced matching number of G is the maximum cardinality of an induced matching among all induced matchings in G, and we denote it by $\mu _{\textsf{in}}(G)$. The minimum maximal induced matching number of G is the minimum cardinality of a maximal induced matching among all maximal induced matchings in G, and we denote it by $\mu '_{\textsf{in}}(G)$. It is also known as the lower induced matching number of G [8]. For an example, consider the graph G with vertex set $V(G)=\{a,b,c,d,e\}$ and edge set $E(G)=\{ab,bc,cd,de\}$. $M_{1}=\{bc\}$ and $M_{2}=\{ab,de\}$ are two maximal induced matchings of G and $M_{1}$ is a minimum maximal induced matching of G. Therefore, $\mu '_{\textsf{in}}(G)=1$.

When we restrict Induced Matching by applying a constraint, which is to saturate one of the partitions of the bipartite graph, then we obtain Saturated Induced Matching. The motivation for Saturated Induced Matching comes directly from the applications of Induced Matching, which are secure communication networks, VLSI design, risk-free marriages, etc. One possible application of Saturated Induced Matching in the secure communication channel is as follows: Suppose we have a bipartite graph $G=(X\uplus Y,E(G))$ where the partitions X and Y represent broadcasters and receivers, respectively, and the edges represent the communication capabilities between broadcasters and receivers. Now, we want to select |Y| edges such that all receivers should get the information, and that too from a unique broadcaster. Moreover, there should be no edge between any two active channels (i.e., edges) to avoid any interception or leakage.

Related Work. Min-Max-Ind-Matching is known to be polynomial-time solvable for graph classes like chordal graphs, circular-arc graphs, and AT-free graphs [15]. The weighted version of Min-Max-Ind-Matching is known to be linear-time solvable for trees [11]. Min-Max-Ind-Matching for random graphs has been studied in [6]. A graph G is bi-size matched if there exists $k\ge 1$ such that $|M| \in \{k, k + 1\}$ for every maximal induced matching M in G. For bi-size matched graphs, Decide-Min-Max-Ind-Matching is shown to be ${\textsf{NP}}$-complete in [16]. From the approximation point of view, Min-Max-Ind-Matching cannot be approximated within a ratio of $n^{1-\epsilon }$ for any $\epsilon >0$ unless ${\textsf{P}}={\textsf{NP}}$ [15]. The Min-Max version of other variants of matchings, like acyclic matching and uniquely restricted matching, have also been considered in the literature [4, 5, 12].

Our Contribution. In Sect. 3, we discuss Min-Max-Ind-Matching. In particular, in Subsect. 3.1, we strengthen the hardness result of Min-Max-Ind-Matching by showing that Decide-Min-Max-Ind-Matching remains $\textsf{NP}$-complete for perfect elimination bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. In Subsect. 3.2, we show the hardness difference between Induced Matching and Min-Max-Ind-Matching by giving a graph class where one problem is polynomial-time solvable while the other problem is $\textsf{APX}$-hard, and vice-versa. In Sect. 4, we introduce Saturated Induced Matching and propose a linear-time algorithm for the same.

2 Preliminaries

For a positive integer k, let [k] denote the set $\{1, \ldots , k\}$. Given a graph G and a matching M, we use the notation $V_{M}$ to denote the set of M-saturated vertices and $G[V_{M}]$ to denote the subgraph induced by $V_{M}$. In a graph G, the open and closed neighborhood of a vertex $v \in V(G)$ are denoted by N(v) and N[v], respectively, and defined by $N(v)=\{w\mid wv \in E(G)\}$ and $N[v]=N(v)\cup \{v\}$. The degree of a vertex v is |N(v)| and is denoted by $d_{G}(v)$. When there is no ambiguity, we do not use the subscript G. If $d(v)=1$, then v is a pendant vertex. For a graph G, the subgraph of G induced by $S\subseteq V(G)$ is denoted by G[S], where $G[S]=(S,E_{S})$ and $E_{S}=\{xy\in E(G)\mid x,y \in S\}.$ A graph G is a k-regular graph if $d(v)=k$ for every vertex v of G. Let $K_{n}$ and $P_{n}$ denote a complete graph and a path graph, respectively. A graph G is a bipartite graph if its vertex set V(G) can be partitioned into two sets, X and Y, such that every edge of G joins a vertex in X to a vertex in Y. We use the notation $G=(X\uplus Y,E(G))$ to represent the bipartite graph with vertex partitions X and Y. An edge xy of G is a bisimplicial edge if $N(x)\cup N(y)$ induces a complete bipartite subgraph of G. Let $\sigma =(x_1y_1,x_2y_2,\dots , x_ky_k)$ be a sequence of pairwise nonadjacent edges of G. Let $S_j=\{x_1,x_2,\ldots ,x_j\}\cup \{y_1,y_2,\ldots ,y_j\}$ and $S_0=\emptyset$. Then, $\sigma$ is a perfect edge elimination ordering for G if each edge $x_{j+1}y_{j+1}$ is bisimplicial in $G_{j+1}=G[(X \uplus Y)\setminus S_j]$ for $j=0,1,\ldots ,k-1$ and $G_{k+1}=G[(X\uplus Y)\setminus S_k]$ has no edge. A bipartite graph for which there exists a perfect edge elimination ordering is a perfect elimination bipartite graph. Introduced by Golumbic and Goss, the class of perfect elimination bipartite graphs is considered to be a bipartite counterpart of chordal graphs and can be recognized in polynomial time [9].

A bipartite graph G is a tree-convex bipartite graph, if a tree $T=(X,E^{X})$ can be defined on the vertices of X, 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 an associated tree T can also be constructed in linear time [2]. A tree with at most one non-pendant vertex is called a star. If the tree T in a tree-convex bipartite graph G is a star, then G is a star-convex bipartite graph. The following proposition is a characterization of star-convex bipartite graphs.

Proposition 1

(Pandey and Panda [14]). A bipartite graph $G=(X\uplus Y,$ E(G)) 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.

A vertex $u\in N_{G}[v]$ in a graph G is a maximum neighbor of v if for all $w\in N_{G}[v]$, $N_{G}[w] \subseteq N_{G}[u]$. An ordering $\alpha =(v_{1},\ldots ,v_{n})$ of V(G) is a maximum neighborhood ordering, if $v_{i}$ has a maximum neighbor in $G_{i}=G[\{v_{i},\ldots ,v_{n}\}]$ for all $i\in [n]$. A graph G is a dually chordal graph if it has a maximum neighborhood ordering. These graphs are a generalization of strongly chordal graphs and a superclass of interval graphs. Furthermore, note that dually chordal graphs can be recognized in linear time [1].

3 Minimum Maximal Induced Matching

3.1 $\textsf{NP}$-completeness Results

In this subsection, we first show that Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for perfect elimination bipartite graphs.

Theorem 2

Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for perfect elimination bipartite graphs.

Proof

Given a perfect elimination bipartite graph G and a matching M, it is easy to observe that Decide-Min-Max-Ind-Matching is in NP. Next, we prove that Decide-Min-Max-Ind-Matching is $\textsf{NP}$-hard for perfect elimination bipartite graphs by establishing a polynomial-time reduction from Decide-Min-Max-Ind-Matching for bipartite graphs, which is known to be $\textsf{NP}$-hard [15].

Given a bipartite graph $G=(X\uplus Y,E(G))$, where $X=\{x_{1},\ldots ,x_{p}\}$ and $Y=\{y_{1},\ldots ,y_{l}\}$, an instance of Decide-Min-Max-Ind-Matching, construct a graph $G'=(X'\uplus Y',E(G'))$, an instance of Decide-Min-Max-Ind-Matching for perfect elimination bipartite graphs in the following way: For each $y_{i}\in Y$, introduce a path $P_{i}=y_{i},a_{i},b_{i},c_{i},d_{i},e_{i}$ of length 5. Formally, $X'=X \cup \bigcup _{i \in [l]}\{a_{i},c_{i},e_{i} \}$, $Y'=Y \cup \bigcup _{i \in [l]} \{b_{i},d_{i} \}$ and $E(G')=E(G) \cup \bigcup _{i \in [l]} \{y_{i}a_{i},a_{i}b_{i},b_{i}c_{i},$ $c_{i}d_{i},d_{i}e_{i} \}$. See Fig. 1 for an illustration of the construction of $G'$ from G. Note that $G'$ is a perfect elimination bipartite graph as $(e_{1}d_{1},\ldots ,e_{l}d_{l}, c_{1}b_{1},\ldots ,c_{l}b_{l},$ $a_{1}y_{1},\ldots ,a_{l}y_{l})$ is a perfect edge elimination ordering of $G'$. Now, the following claim is sufficient to complete the proof of the theorem.

Fig. 1.

An illustration of the construction of $G'$ from G.

Claim 3

G has a maximal induced matching of cardinality at most k if and only if $G'$ has a maximal induced matching of cardinality at most $k+l$.

Proof

Let M be a maximal induced matching in G of cardinality at most k. Define a matching $M'=M\cup \bigcup _{i \in [l]}\{b_{i}c_{i} \}$ in $G'$. By the definition of an induced matching, note that $M'$ is a maximal induced matching in $G'$ and $|M'|\le k+l$.

Conversely, let M be a minimum maximal induced matching in $G'$ of cardinality at most $k+l$. Since M is maximal, $|M\cap \{b_{i}c_{i},c_{i}d_{i},d_{i}e_{i} \}|\ge 1$ for each $i \in [l]$. Furthermore, since M is an induced matching, $|M\cap \{b_{i}c_{i},c_{i}d_{i},d_{i}e_{i} \}|\le 1$ for each $i \in [l]$. Thus, for each $i \in [l]$, $|M\cap \{b_{i}c_{i},c_{i}d_{i},d_{i}e_{i} \}|= 1$.

Now, we label each $y_{i}\in Y$ as either Type-I vertex, Type-II vertex or Type-III vertex depending on whether $b_{i}c_{i},c_{i}d_{i}$ or $d_{i}e_{i}$ belongs to M. For every $i \in [l]$, if $y_{i}$ is a Type-I vertex, remove the vertices $a_{i},b_{i},c_{i},d_{i},e_{i}$ from $G'$, if $y_{i}$ is a Type-II vertex, remove the vertices $b_{i},c_{i},d_{i},e_{i}$ from $G'$, and if $y_{i}$ is a Type-III vertex, remove the vertices $c_{i},d_{i},e_{i}$ from $G'$. After removing all the desired vertices, let us call the graph so obtained as $\widehat{G}$. See Fig. 2 for an illustration of the construction of $\widehat{G}$ from $G'$. Let $\widehat{M}$ be the restriction of M to $\widehat{G}$. Clearly, $\widehat{M}$ is a maximal induced matching in $\widehat{G}$ and $|\widehat{M}|= (k+l)-l=k$. Now, we claim that there exists a maximal induced matching in G of cardinality at most k. If $\widehat{M}\subset E(G)$, then we are done, as $\widehat{M}$ will be a desired maximal induced matching in G of cardinality at most k. So, let us assume that $\widehat{M}$ contains an edge from the path $P_{j}$ for some fixed $j\in [l]$.

Fig. 2.

An illustration of the construction of $\widehat{G}$ from $G'$. Here, the dashed edges show a minimum maximal induced matching in $G'$.

If $y_{j}a_{j}\in \widehat{M}$ and $y_{j}$ is a Type-II (or Type-III) vertex, then we claim that one of the following conditions will hold:

• i) $(\widehat{M}\setminus \{y_{j}a_{j}\}) \cup \{y_{j}x_{k}\}$ is a maximal induced matching in $\widehat{G}$ for some $x_{k}\in N(y_{j})$.

• ii) $\widehat{M} \setminus \{y_{j}a_{j}\}$ is a maximal induced matching in $\widehat{G}\setminus \{a_{j}\}$ or $\widehat{G}\setminus \{a_{j},b_{j}\}$ depending on whether $y_{j}$ is a Type-II vertex or a Type-III vertex, respectively.

If Condition i) holds, then we are done. So, let us assume that $(\widehat{M}\setminus \{y_{j}a_{j}\}) \cup \{y_{j}x_{k}\}$ is not a maximal induced matching in $\widehat{G}$ for any $x_{k}\in N(y_{j})$. This implies that the edges incident on $y_{j}$ (except $y_{j}a_{j}$) are dominated by edges from the edge set $E(G)\cap \widehat{M}$. So, in other words, if we remove the edge $y_{j}a_{j}$ from $\widehat{M}$, then all edges except $y_{j}a_{j}$ will be dominated by the rest of $\widehat{M}$. This further implies that $\widehat{M} \setminus \{y_{j}a_{j}\}$ is a maximal induced matching in $\widehat{G}\setminus \{a_{j}\}$ or $\widehat{G}\setminus \{a_{j},b_{j}\}$ depending on whether $y_{j}$ is a Type-II or a Type-III vertex. Similarly, if $a_{j}b_{j}\in \widehat{M}$, then we claim that either $(\widehat{M}\setminus \{a_{j}b_{j}\})\cup \{y_{j}a_{j}\}$ is a maximal induced matching in $\widehat{G}$ or $\widehat{M}\setminus \{a_{j}b_{j}\}$ is a maximal induced matching in $\widehat{G}\setminus \{a_{j},b_{j}\}$. So, we have proved that every edge $e\in \widehat{M}\cap P_{j}$ can either be replaced by an edge in E(G) or can be removed without disturbing the maximality of the matching restricted to E(G). Therefore, G has a maximal induced matching of cardinality at most k.    $\square$

Hence, Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for perfect elimination bipartite graphs.    $\square$

Next, we show that Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for star-convex bipartite graphs.

Theorem 4

Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for star-convex bipartite graphs.

Proof

Given a star-convex bipartite graph G and a matching M, it is easy to observe that Decide-Min-Max-Ind-Matching is in NP. Next, we prove that Decide-Min-Max-Ind-Matching is $\textsf{NP}$-hard for star-convex bipartite graphs by establishing a polynomial-time reduction from Decide-Min-Max-Ind-Matching for bipartite graphs, which is known to be $\textsf{NP}$-hard [15].

Given a bipartite graph $G=(X \uplus Y,E(G))$, where $X=\{x_{1},\ldots ,x_{p}\}$ and $Y=\{y_{1},\ldots ,y_{q}\}$ for $q\ge 3$, an instance of Decide-Min-Max-Ind-Matching, we construct a star-convex bipartite graph $G'=(X'\uplus Y',E(G'))$, an instance of Decide-Min-Max-Ind-Matching in the following way:

• Introduce a vertex $x_{0}$ and make $x_{0}$ adjacent to $y_{i}$ for each $i \in [q]$.

• Introduce the vertex set $\{\overline{y}_{1},\ldots ,\overline{y}_{q}\}$ and make $x_{0}$ adjacent to $\overline{y}_{i}$ for each $i \in [q]$.

• Introduce the edge set $\bigcup _{i,j \in [q]}\{x_{ij}y_{ij}\}$. For each $i\in [q]$, make $\overline{y}_{i}$ adjacent to $x_{ij}$ for every $j\in [q]$.

Formally, $X'=X\cup \{x_{0}\}\cup \bigcup _{i,j \in [q]} \{x_{ij}\}$ and $Y'=Y\cup \bigcup _{i \in [q]}\{\overline{y}_{i}\} \bigcup _{i,j \in [q]}\{ y_{ij} \}$. See Fig. 3 for an illustration of the construction of $G'$ from G. Note that every vertex in $Y'$ is either adjacent to $x_{0}$ or is a pendant vertex. So, by Proposition 1, it is clear that the graph $G'$ is a star-convex bipartite graph. Now, the following claim is sufficient to complete the proof of the theorem.

Claim 5

G has a maximal induced matching of cardinality at most k if and only if $G'$ has a maximal induced matching of cardinality at most $k+q$.

Proof

Let M be a maximal induced matching in G of cardinality at most k. Define a matching $M'$ in $G'$ as follows: $M'=M\cup \bigcup _{i \in [q]}\{\overline{y}_{i}x_{ii} \}$. Clearly, $M'$ is a maximal induced matching in $G'$ and $|M'|\le k+q$.

Conversely, let M be a minimum maximal induced matching in $G'$ of cardinality at most $k+q$. Let $M_{G}$ denote a maximum induced matching in G. Note that $|M_{G}|\le q$. Now consider the following matching: $M'=\bigcup _{i \in [q]}\{\overline{y}_{i}x_{ii}\}\cup M_{G}$. Note that $M'$ is a maximal induced matching in $G'$ of cardinality at most 2q. Thus, $|M|\le 2q$. Now, we will show that there exists a maximal induced matching in G of cardinality at most k.

If $x_{0}\overline{y}_{i}\in M$ for some fixed $i\in [q]$, then $\overline{y}_{k}x_{kj}\notin M$ for any $k,j \in [q]$. Also, $x_{0}\overline{y}_{k}\notin M$ for any $k\in [q]\setminus \{i\}$. So, edges of the form $x_{kj}y_{kj}$ must belong to M for every $k \in [q]\setminus \{i\}$ and $j \in [q]$. Thus, $|M|\ge q(q-1)+1$, which is a contradiction to the fact that $|M|\le 2q$. Therefore, $x_{0}\overline{y}_{i}\notin M$ for any $i \in [q]$. Now, there are two possibilities. If $x_{ij}y_{ij}\in M$ for some $i \in [q]$, then $x_{ij}y_{ij}\in M$ for every $j\in [q]$. On the other hand, if for each $i \in [q]$ there exists some $j \in [q]$ such that $\overline{y}_{i}x_{ij}\in M$, then only q edges will suffice to make M maximal. So, in any minimum maximal induced matching M, it is always better to choose edges of the form $\overline{y}_{i}x_{ij}$ in M for all $i,j \in [q]$. Thus, M restricted to E(G) is a desired maximal induced matching in G of cardinality at most k.    $\square$

Hence, by Claim 5, Decide-Min-Max-Ind-Matching is ${\textsf{NP}}$-complete for star-convex bipartite graphs.    $\square$

Fig. 3.

An illustration of the construction of $G'$ from G.

As the class of tree-convex bipartite graphs is a superclass of star-convex bipartite graphs, the following corollary is a consequence of Theorem 4.

Corollary 6

Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for tree-convex bipartite graphs.

Next, we show that Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for dually chordal graphs. Note that the reduction is similar to the reduction given for star-convex bipartite graphs.

Theorem 7

Decide-Min-Max-Ind-Matching is $\textsf{NP}$-complete for dually chordal graphs.

Proof

Given a dually chordal graph G and a subset $M\subseteq E(G)$, it can be checked in polynomial time whether M is a maximal induced matching in G or not. So, Decide-Min-Max-Ind-Matching belongs to the class $\textsf{NP}$ for dually chordal graphs. To show the ${\textsf{NP}}$-hardness, we give a polynomial-time reduction from Decide-Min-Max-Ind-Matching for general graphs, which is already known to be $\textsf{NP}$-complete [15].

Given a graph G, where $V(G)=\{v_{1}\ldots ,v_{n}\}$ and $n\ge 3$, an instance of Decide-Min-Max-Ind-Matching, we construct a dually chordal graph $G'$, an instance of Decide-Min-Max-Ind-Matching in the following way:

• Introduce a vertex $v_{0}$ and make $v_{0}$ adjacent to $v_{i}$ for each $i \in [n]$.

• Introduce the vertex set $\{w_{1},\ldots ,w_{n}\}$ and make $v_{0}$ adjacent to $w_{i}$ for each $i \in [n]$.

• Introduce the edge set $\bigcup _{i,j \in [n]}\{p_{ij}q_{ij}\}$. For each $i\in [n]$, make $w_{i}$ adjacent to $p_{ij}$ for every $j\in [n]$.

Clearly, $G'$ is a dually chordal graph as $(q_{11},\ldots q_{1n},q_{21},\ldots q_{2n},\ldots ,q_{n1},\ldots$ $q_{nn},$ $p_{11},\ldots p_{1n},p_{21},$ $\ldots p_{2n},\ldots ,p_{n1},\ldots p_{nn},w_{1},w_{2},\ldots ,w_{n},v_{1},v_{2},\ldots ,v_{n},v_{0})$ is a maximum neighborhood ordering of $G'$. Now, the following claim is sufficient to complete the proof.

Claim 8

G has a maximal induced matching of cardinality at most k if and only if $G'$ has a maximal induced matching of cardinality at most $k+n$.

Proof

Let M be a maximal induced matching in G of cardinality at most k. Define a matching $M'$ in $G'$ as follows: $M'=M\cup \bigcup _{i \in [n]}\{w_{i}p_{ii}\}$. Clearly, $M'$ is a maximal induced matching in $G'$ and $|M'|\le k+n$.

Conversely, let M be a minimum maximal induced matching in $G'$ of cardinality at most $k+n$. Now, we will show that there exists a maximal induced matching in G of cardinality at most k. Let $M_{G}$ denote a maximum induced matching in G. Note that $|M_{G}|\le \frac{n}{2}$.

If $v_{0}w_{i}\in M$ for some fixed $i\in [n]$, then $w_{k}p_{kj}\notin M$ for any $k,j\in [n]$. Also, $v_{0}w_{k}\notin M$ for any $k\in [n]\setminus \{i\}$. So, edges of the form $p_{kj}q_{kj}$ must belong to M for each $k \in [n]\setminus \{i\}$ and $j \in [n]$. Thus, $|M|\ge n(n-1)+1$, which is a contradiction as $M'=\bigcup _{i \in [n]}\{w_{i}p_{ii}\}\cup M_{G}$ is a maximal induced matching in $G'$ of cardinality at most $\frac{n}{2}+n$ and cardinality of M cannot be greater than the cardinality of $M'$. Therefore, $v_{0}w_{i}\notin M$ for any $i \in [n]$. Now, there are two possibilities. If $p_{ij}q_{ij}\in M$ for some $i,j \in [n]$, then $p_{ik}q_{ik}\in M$ for every $k \in [n]$. On the other hand, if for each $i \in [n]$ there exists some $j\in [n]$ such that $w_{i}p_{ij}\in M$, then only n edges will suffice to make M maximal. So, in any minimum maximal induced matching M, it is always better to choose edges of the form $w_{i}p_{ij}$ in M for all $i,j \in [n]$. Thus, M restricted to E(G) is a desired maximal induced matching in G of cardinality at most k.    $\square$

Hence, Decide-Min-Max-Ind-Matching is ${\textsf{NP}}$-complete for dually chordal graphs.    $\square$

3.2 Hardness Difference Between Induced Matching and Minimum Maximal Induced Matching

In this subsection, we show that Min-Max-Ind-Matching and Induced Matching differ in hardness; that is, there are graph classes in which one problem is polynomial-time solvable while the other is $\textsf{APX}$-hard, and vice versa. For this purpose, consider the following definition.

Definition 9

($\boldsymbol{GC_{3}}$ graph). A graph H is a $GC_{3}$ graph if it can be constructed from some graph G, where $V(G)=\{v_{1},\ldots , v_{n}\}$ in the following way: For each vertex $v_{i}$ of G, introduce a cycle $v_{i},a_{i},b_{i},v_{i}$ of length 3 in H. Formally, $V(H)=V(G)\cup \bigcup _{i \in [n]}\{a_{i},b_{i}\}$ and $E(H)=E(G) \cup \bigcup _{i \in [n]} \{v_{i}a_{i},a_{i}b_{i},v_{i}b_{i} \}$.

Now, consider the following straightforward observation that follows from the definition of maximal induced matching.

Observation 10

Let M be an induced matching in a $GC_{3}$ graph H. Then, M is maximal in H iff for each $i\in [n]$, either $v_{i}$ is saturated by M or $a_{i}b_{i}\in M$.

Now, we will show that Induced Matching is polynomial-time solvable for $GC_{3}$ graphs, and Min-Max-Ind-Matching is $\textsf{APX}$-hard for $GC_{3}$ graphs.

Theorem 11

Let H be a $GC_{3}$ graph constructed from a graph G, where $V(G)=\{v_{1}, \ldots , v_{n}\}$, as in Definition 9. Then, $\mu _{\textsf{in}}(H)=n$.

Proof

Let $M=\bigcup _{i \in [n]} \{a_{i}b_{i} \}$. It is easy to see that $|M|=n$ and $G[V_{M}]$ is a disjoint union of $K_{2}'s$. So, M is an induced matching in H. Hence, $\mu _{\textsf{in}}(H)\ge n$.

Next, consider a maximum induced matching, say $M_{in}$ in H. If $|M_{in}|>n$, then $M_{in}$ must contain at least one edge from the edge set E(G), i.e., $v_{i}v_{j}\in M_{in}$ for some $i,j\in [n]$. Define $M=(M_{in}\setminus \{v_{i}v_{j}\})\cup \{a_{i}b_{i},a_{j}b_{j}\}$. By Observation 10, M is an induced matching in H and $|M|>|M_{in}|$, which is a contradiction as $M_{in}$ is a maximum induced matching in H. Thus, $\mu _{\textsf{in}}(H)\le n$.    $\square$

Proposition 12

(Gotthilf and Lewenstein [10]). Let G be a graph with maximum degree $\varDelta$. Then, $\mu _{\textsf{in}}(G)\ge \frac{|E(G)|}{1.5\varDelta ^2-0.5\varDelta }$.

Proposition 13

(Duckworth et al. [7]).Induced Matching is $\textsf{APX}$-complete for r-regular graphs for every fixed integer $r\ge 3$.

Theorem 14

Min-Max-Ind-Matching is $\textsf{APX}$-hard for $GC_{3}$ graphs.

Proof

Given a 3-regular graph G, an instance of Induced Matching, we construct a $GC_{3}$ graph H, an instance of Min-Max-Ind-Matching by attaching a cycle $v_{i},a_{i},b_{i},v_{i}$ of length 3 to each $v_{i}, i\in [n]$. Next, let Type-A edges $=\bigcup _{i \in [n]} \{a_{i}b_{i} \}$ and Type-B edges $=E(G)$. Now, consider the following claim whose proof follows from Observation 10 and the fact that every edge of the form $v_{i}a_{i}$ or $v_{i}b_{i}$ (where $i\in [n]$) can be replaced with $a_{i}b_{i}$.

Claim 15

For every maximal induced matching M in a $GC_3$ graph H, there exists a maximal induced matching $M'$ such that $|M'| = |M|$ and $M'$ contains edges of Type-A and Type-B only.

Claim 16

Let $M_{B}^{*}$ be a minimum maximal induced matching in H and $M_{A}^{*}$ be a maximum induced matching in G. Then, $|M_{B}^{*}|=n-|M_{A}^{*}|$.

Proof

Since $M_{A}^{*}$ is a maximum induced matching in G, this implies that $2|M_{A}^{*}|$ vertices are saturated, and $n-2|M_{A}^{*}|$ vertices are unsaturated by $M_{A}^{*}$ in G. Define a matching $M_{B}=M_{A}^{*}\cup \{a_{i}b_{i} \mid v_{i}$ is unsaturated by $M_{A}^{*}\}$ in H. By Observation 10, $M_{B}$ is a maximal induced matching in H. Since $|M_{B}|=(|M_{A}^{*}|+n-2|M_{A}^{*}|)=n-|M_{A}^{*}|$, $|M_{B}^{*}|\le n-|M_{A}^{*}|.$

By Claim 15, there exists a minimum maximal induced matching $M_{B}^{*}$ in H such that $M_{B}^{*}$ contains edges of Type-A and Type-B only. Let $T^*\cup S^*$ be a partition of $M_{B}^{*}$ such that $T^*$ contains Type-A edges and $S^*$ contains Type-B edges. Since $M_{B}^{*}$ is maximal, $|T^*|=n-2|S^*|$. This implies that $|M_{B}^{*}|=|S^*|+(n-2|S^*|)=n-|S^*|$. Since $S^{*}\subset M_{B}^{*}$, $S^*$ is an induced matching in G and $|S^{*}|\le |M_{A}^{*}|$. As $|S^*|=n-|M_{B}^{*}|$, $n-|M_{B}^{*}|\le |M_{A}^{*}|$. This completes the proof of Claim 16.    $\square$

We now return to the proof of Theorem 14. By Proposition 12, we know that any 3-regular graph G satisfies the inequality $|M_{A}^{*}|\ge \frac{n}{8}.$ Therefore, we have $|M_{B}^{*}|=n-|M_{A}^{*}|\le 8|M_{A}^{*}|-|M_{A}^{*}|=7|M_{A}^{*}|$. Further, let M be a maximal induced matching in H. By Claim 15, there exists a maximal induced matching in H such that $|M_{B}|=|M|$ and $M_{B}$ contains edges of Type-A and Type-B only. Let $T_{B}\cup S_{B}$ be a partition of $M_{B}$ such that $T_{B}$ contains Type-A edges and $S_{B}$ contains Type-B edges. Since $M_{B}$ is maximal, $|T_{B}|=(n-2|S_{B}|)$. Hence, $|M_{B}|=n-|S_{B}|$. Here, $S_{B}$ is a desired induced matching in G. Let $S_{B}=M_{A}$. Now, $|M_{A}^{*}|- |M_{A}|=|M_{A}^{*}|-|M_{A}|+n-n=(n-|M_{A}|)-(n-|M_{A}^{*}|)\le |(|M_{B}^{*}|-M_{B})|$. From these two inequalities and Proposition 13, it follows that it is an $\textsf{L}$-reduction with $\alpha =7$ and $\beta =1$. Thus, Min-Max-Ind-Matching is $\textsf{APX}$-hard for $GC_{3}$ graphs.    $\square$

Next, consider the following definition.

Definition 17

($\boldsymbol{Gx_{0}}$ graph). A bipartite graph $G'=(X' \uplus Y',E(G'))$ is a $Gx_{0}$ graph if it can be constructed from a bipartite graph $G=(X \uplus Y,E(G))$, where $Y=\{y_{1}, \ldots , y_{l}\}$ in the following way: Introduce a new vertex $x_{0}$ and make $x_{0}$ adjacent to each $y_{i}\in Y$. Formally, $X'=X\cup \{x_{0}\}, Y'=Y,$ and $E(G')=E(G)\cup \{x_{0}y_{i} \mid y_{i}\in Y\}$.

Now, we show that Min-Max-Ind-Matching is polynomial-time solvable for $Gx_{0}$ graphs, and Induced Matching is $\textsf{APX}$-hard for $Gx_{0}$ graphs.

Theorem 18

Let $G'=(X' \uplus Y',E(G'))$ be a $Gx_{0}$ graph constructed from a bipartite graph $G=(X \uplus Y,E(G))$, where $Y=\{y_1,\ldots ,y_l\}$, as in Definition 17. Then, $\mu '_{\textsf{in}}(G')=1$.

Proposition 19

(Panda et al. [13]). Let $G'$ be a $Gx_{0}$ graph constructed from an r-regular $(r\ge 3)$ bipartite graph G by introducing a vertex $x_{0}$ and making $x_{0}$ adjacent to every vertex in one of the partitions of G. Then, G has an induced matching of cardinality at least k if and only if $G'$ has an induced matching of cardinality at least k.

Now, we are ready to prove the following theorem by giving a polynomial-time reduction from Induced Matching.

Theorem 20

Induced Matching is $\textsf{APX}$-hard for $Gx_{0}$ graphs.

Proof

Given an r-regular graph G, an instance of Induced Matching, we construct a $Gx_{0}$ graph H, an instance of Induced Matching by introducing a vertex $x_{0}$ and making it adjacent to every vertex of G (see Definition 17). Now, we have the following claim from Proposition 19.

Claim 21

If $M_{B}^{*}$ is a maximum induced matching in $G'$ and $M_{A}^{*}$ is a maximum induced matching in G, then $|M_{B}^{*}|=|M_{A}^{*}|$.

We now return to the proof of Theorem 20. By Claim 21, it is clear that $|M_{B}^{*}|=|M_{A}^{*}|$. Further, let $M_{B}$ be an induced matching in $G'$. By Proposition 19, there exists an induced matching $M_{A}$ in G such that $|M_{A}|\ge |M_{B}|$. By Claim 21, it follows that $|M_{A}^{*}|- |M_{A}|\le |M_{B}^{*}|-M_{B}|$. From these two inequalities, it follows that it is an $\textsf{L}$-reduction with $\alpha =1$ and $\beta =1$. Therefore, Min-Max-Ind-Matching is $\textsf{APX}$-hard for $Gx_{0}$ graphs.    $\square$

4 Saturated Induced Matching

In this section, we will first introduce Saturated Induced Matching and then propose a linear-time algorithm to solve it.

It is well-known that Induced Matching is $\textsf{NP}$-complete for bipartite graphs [3]. However, when we restrict Induced Matching to Saturated Induced Matching, then the problem becomes linear-time solvable. To prove this, consider the following lemma.

Lemma 22

Let $M_{S}$ be an induced matching in a bipartite graph $G=(X\uplus Y,E(G))$ that saturates all vertices of Y. Then, an edge $x_{i}y_{j}\in M_{S}$ only if $d(x_{i})=1$.

Proof

Targeting a contradiction, let us suppose that there exists an edge $x_{i}y_{j}\in M_{S}$ such that $d(x_{i})>1$. Let $y_{k}\in Y\setminus \{y_{j}\}$ be such that $x_{i}y_{k}\in E(G)$. Now, since $x_{i}y_{j}\in M_{S}$, therefore $x_{i}y_{k}\notin M_{S}$ (as $x_{i}y_{k}$ and $x_{i}y_{j}$ are adjacent). However, since $M_{S}$ is a saturated induced matching, this implies that there is an edge incident on $y_{k}$ that belongs to $M_{S}$. This, in turn, implies that the edge $x_{i}y_{k}$ is dominated twice, a contradiction to the fact that $M_{S}$ is an induced matching.    $\square$

Based on Lemma 22, we have Algorithm 1 that finds a saturated induced matching $M_{S}$ in a given bipartite graph, if one exists. Since we are just traversing the adjacency list of every vertex in the X partition of the bipartite graph G, we have the following theorem.

Theorem 23

Given a bipartite graph G, the Saturated Induced Matching problem can be solved in $\mathcal {O}(|V(G)|+|E(G)|)$ time.

5 Open Problems

Exploring the parameterized complexity of Min-Max-Ind-Matching is an interesting future direction.