On the complexity of minimum maximal acyclic matchings

All graphs discussed in this paper are simple, connected, and undirected. In the context of a graph denoted as G, V(G) denotes its vertex set, and E(G) represents its edge set. For any subset \(X\subseteq V(G)\), we refer to the subgraph of G induced by X as G[X]. This subgraph is formally defined as \(G[X] = (X, E_X)\), where \(E_X\) comprises edges ab in E(G) with both vertices a and b belonging to X.

A matching M in a graph G is a subset of edges such that no two edges in M share a common vertex. Given a matching M within the graph G, we say that a vertex v in V(G) is M-saturated if there exists an edge e in M that is incident on v. To denote the set of vertices in G that are M-saturated, we use the notation \(V_M\).

In the Max-Matching problem, the aim is to find a matching of maximum cardinality in the given graph G. Note that Max-Matching can be solved in polynomial time (Edmonds 1965). In this paper, we shall denote by \(\mu (G)\) the matching number of G, which is defined as \(\mu (G)=\max \{|M|:M\) is a matching in \(G\}\).

In a graph G, a matching M is acyclic if the subgraph \(G[V_{M}]\) is a forest (acyclic). In Max-Acy-Matching, the aim is to find an acyclic matching of maximum cardinality in the input graph G. Note that the decision version of Max-Acy-Matching is \(\textsf{NP}\)-complete (Goddard et al. 2005). Furthermore, Max-Acy-Matching is hard to approximate within a factor of \(n^{1-\epsilon }\) for any \(\epsilon >0\) unless \(\mathsf {P=NP}\), and is \(\textsf{APX}\)-complete for \((2k+1)\)-regular graphs for every fixed integer \(k\ge 3\) (Panda and Chaudhary 2023). It is worth noting that acyclic matchings have found their applications in real-world problems such as tracing cells and electrons in chemical industries, cybersecurity, and so on Saffren and Angel (2022). The acyclic matching number of G represents the largest possible size of an acyclic matching within G, and we denote it by \(\mu _{ac}(G)\).

An acyclic matching M in a graph G is a maximal acyclic matching if M is not properly contained in any other acyclic matching of G. Given a graph G, the problem Low-Acy-Matching seeks to identify a maximal acyclic matching in G with the minimum possible cardinality. The minimum maximal acyclic matching number of G corresponds to the smallest cardinality among all the maximal acyclic matchings in G and is denoted as \(\mu '_{ac}(G)\). It is alternatively referred to as the lower acyclic matching number of graph G, as mentioned in Goddard’s work from 2005 (Goddard et al. 2005). Note that the lower acyclic matching number of a graph G serves as a lower bound for its acyclic matching number.

Formally, the decision problem version of Low-Acy-Matching is presented below.

Matching theory has received extensive attention in the literature due to its numerous applications and its connections with other graph-theoretic problems (Lovász and Plummer 2009). Over the years, the literature has investigated a range of matching variations, including connected matching (Gomes et al. 2022), disconnected matching (Chaudhary and Zehavi 2023a; Gomes et al. 2023), uniquely restricted matching (Francis et al. 2018; Golumbic et al. 2001; Mishra 2011), acyclic matching (Chaudhary and Zehavi 2023a, b; Goddard et al. 2005; Panda and Chaudhary 2023; Saffren and Angel 2022), and induced matching (Cameron 1989; Chaudhary and Zehavi 2023a; Stockmeyer and Vazirani 1982).

Recently, the Min–Max and Max–Min variations of several significant optimization problems, including Feedback Vertex Set (Dublois et al. 2020), Domination (Bazgan et al. 2018), Hitting Set (Damaschke 2011), and Vertex Cover (Boria et al. 2015) have gained substantial attention from the research community. These variations involve considering the minimization (in the case of Min–Max) or maximization (in the case of Max–Min) of the size of a maximal (for Min–Max) or minimal (for Max–Min) solution to the respective problem. Initially, these problems were studied to assess how naive heuristics perform compared to the conventional Max and Min versions. However, it has become evident that these Max–Min and Min–Max problems unveil intriguing combinatorial structures, rendering them as captivating as their conventional Max and Min counterparts.

Notably, in contrast to the classical Max-Matching problem, the decision problem associated with the Min–Max version of matching is well-established to be \(\textsf{NP}\)-complete, being equivalent to Independent Edge Domination (Yannakakis and Gavril 1980). Furthermore, the Min–Max versions of matchings, such as uniquely restricted matching and induced matching, have been subjects of investigation in previous studies (Chaudhary and Panda 2021; Lepin 2006; Orlovich et al. 2008; Orlovich and Zverovich 2004; Panda and Pandey 2016). In this paper, we will focus on minimum maximal acyclic matchings only.

The concept of a minimum maximal acyclic matching was first introduced by Goddard et al. Goddard et al. (2005). They proved that the decision version of Low-Acy-Matching is \({\textsf{NP}}\)-complete. In the same paper, they presented it as an open question, aiming to ascertain the computational complexity of Low-Acy-Matching across different graph classes. Recently, it has been shown that Low-Acy-Matching is linear-time solvable for proper interval graphs (Chaudhary et al. 2023) and Decide-Low-Acy-Matching is NP-complete for dually chordal graphs (Chaudhary et al. 2023). As far as we are aware, there are no other known algorithmic outcomes for Low-Acy-Matching.

Before moving forward, it is worth noting that the computation of \(\mu '_{ac}(G)\) is straightforward in some graph classes, as discussed below.

Let \(K_{n}\) represent a clique comprising of n vertices. Now, observe that, for \(n \ge 2\), \(\mu (K_n) = \big \lfloor \frac{n}{2} \big \rfloor \) and \(\mu _{ac}(K_n)=\mu '_{ac}(K_n) = 1\). Likewise, the maximum number of edges in an acyclic matching can be arbitrarily larger than the minimum number of edges in a maximal acyclic matching. For instance, consider creating a graph \(H_{n}\) by taking n copies of \(K_{2}\) and connecting their endpoints with a vertex u. In this case, \(\mu _{ac}(H_{n})=n\) and \(\mu '_{ac}(H_{n})=1\).

Now, note that it is relatively easy to find a minimum maximal acyclic matching in some graph classes. For instance, if G is a split graph and \(V_1 \uplus V_2\) is a partition of V(G) such that \(V_1\) is an independent set and \(V_2\) (with \(|V_2|\ge 2\)) is a clique, then M consisting of one edge in \(V_2\) is a minimum maximal acyclic matching in G.

Next, if \(G=(A \uplus B, E(G))\) is a chain graph and \(\sigma =(a_{1},\ldots ,a_{p},b_{1},\ldots ,b_{q})\) is a linear chain ordering of \(A \uplus B\) such that \(N(a_1) \subseteq \ldots \subseteq N(a_{p})\) and \(N(b_q) \subseteq \ldots \subseteq N(b_{1})\). Then, \(M=\{a'b'\mid a'\in N(b_{q}),b'\in N(a_{1})\}\) is a minimum maximal acyclic matching in G.

It is well-known that every cograph G is either disconnected or can be written as the join of two cographs \(G_{1}\) and \(G_{2}\) (Fürst and Rautenbach 2019). We assume that a connected cograph G is the join of two cographs \(G_{1}\) and \(G_{2}\). Let M be an acyclic matching of G. Then, by (Fürst and Rautenbach (2019), Theorem 2), it can be noted that either \(M\subseteq E(G_{1})\) or \(M\subseteq E(G_{2})\) or M consists of exactly one edge between a vertex of \(G_{1}\) and a vertex of \(G_{2}\). So \(M=\{x_{1}x_{2}\mid x_{1}\in V(G_{1})\) and \(x_{2} \in V(G_{2}) \}\) is a maximal acyclic matching in G, and hence \(\mu '_{ac}(G)=1\).

In this paper, we extend the study on the algorithmic aspects of Low-Acy-Matching. The contributions of this paper are organized as follows.

1. 1.

   In Sect. 3, we demonstrate the contrast in computational difficulty between Low-Acy-Matching and Max-Acy-Matching by identifying graph classes where one problem can be solved in polynomial time while the other is \(\textsf{APX}\)-hard, and vice versa.

2. 2.

   In Sect. 4, we establish the \({\textsf{NP}}\)-completeness of Decide-Low-Acy-Matching for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs.

3. 3.

   In Sect. 5, we prove that Low-Acy-Matching cannot be approximated within a ratio of \(n^{1-\epsilon }\) for any \(\epsilon >0\) unless \({\textsf{P}}={\textsf{NP}}\) even for bipartite graphs.

4. 4.

   In Sect. 6, we show that Low-Acy-Matching is \(\textsf{APX}\)-hard for 4-regular graphs.

5. 5.

   In Sect. 7, we conclude the paper with some open problems.

For \(\ell \in \mathbb {N}\), let \([\ell ]\) denote the set \(\{1, \ldots , \ell \}\). For a given graph G, we denote the open and closed neighborhoods of \(a \in V(G)\) by N(a) and N[a], respectively, which are defined by \(N(a)=\{b\mid ab \in E(G)\}\) and \(N[a]=N(a)\cup \{a\}\), respectively. The degree of a vertex a is |N(a)| and is denoted by d(a). A graph G is k-regular if \(d(a)=k\) for every \(a\in V(G)\). Given a matching M of a graph G, if the edge \(ab\in M\), then b is the M-mate of a and vice versa. A set \(D \subseteq V(G)\) is a dominating set of G if every vertex \(a \in V(G) {\setminus } D\) is adjacent to at least one vertex in D. An independent set of a graph G is a subset of V(G) such that no two vertices in the subset have an edge between them in G. A set \(D \subseteq V(G)\) is an independent dominating set of G if it is both a dominating set as well as an independent set. A graph G is a planar graph if it can be drawn on a plane in such a way that no two edges cross each other except at a vertex. An edge ab of a graph G is a bisimplicial edge if \(N(a)\cup N(b)\) induces a complete bipartite subgraph of G. Let \(\sigma =(a_1b_1,\dots , a_kb_k)\) be a sequence of pairwise nonadjacent edges of G. Let \(X_j=\{a_1,\ldots ,a_j\}\cup \{b_1,\ldots ,b_j\}\) and \(X_0=\emptyset \). Then \(\sigma \) is said to be a perfect edge elimination ordering for G if each edge \(a_{j+1}b_{j+1}\) is bisimplicial in \(G_{j+1}=G[(A \cup B)\setminus X_j]\) for \(j\in \{0\}\cup [k-1]\) and \(G_{k+1}=G[(A\cup B)\setminus X_k]\) has no edge. A bipartite graph for which there exists a perfect edge elimination ordering is a perfect elimination bipartite graph. Golumbic and Goss introduced the concept of perfect elimination bipartite graphs, which are regarded as the bipartite equivalent of chordal graphs and can be efficiently identified in polynomial time (Golumbic and Goss 1978). Given a graph G, a vertex set \(X \subseteq V(G)\) is an acyclic set if G[X] is an acyclic graph.

Next, consider the following definition, which is crucial to prove some of the results in this paper.

Definition 1

(\(\textsf{L}\)-reduction (Papadimitriou and Yannakakis 1991)) A pair of functions (f, g), both computable in polynomial time, constitutes an \(\textsf{L}\)-reduction from optimization problem \(\Pi _{1}\) to optimization problem \(\Pi _{2}\) if there exist positive constants \(\alpha \) and \(\beta \), such that for every instance x of \(\Pi _{1}\), the following conditions are satisfied:

(a):

The function f transforms instances of \(\Pi _{1}\) into instances of \(\Pi _{2}\) in a manner that ensures \(\textsf{opt}_{\Pi {2}}(f(x))\le \alpha \cdot \textsf{opt}_{\Pi {1}}(x)\). Here, \(\textsf{opt}_{\Pi _{1}}(x)\) denotes the optimal value of instance x of \(\Pi _{1}\) and \(\textsf{opt}_{\Pi _{2}}(f(x))\) denotes the optimal value of instance f(x) of \(\Pi _{2}\).

(b):

The function g translates feasible solutions y of f(x) into feasible solutions g(y) of x, ensuring that \(\vert \textsf{opt}_{\Pi _{1}}(x)-c_{x}(g(y))\vert \le \beta \cdot \vert \textsf{opt}_{\Pi _{2}}(f(x))-c_{f(x)}(y)\vert \), where \(c_x(\cdot )\) and \(c_{f(x)}(\cdot )\) are the cost functions^{Footnote 1} of the instances x and f(x), respectively.

We direct the reader to Ausiello et al. (2012) for most other approximate algorithm-related terms and concepts.

In this section, we will demonstrate the contrast in difficulty between Max-Acy-Matching and Low-Acy-Matching; specifically, we will identify graph classes where one problem can be solved in polynomial time while the other is \(\textsf{APX}\)-hard, and vice versa.

To this end, consider the following definition.

Definition 2

A graph G is a \(GC_{4}\) graph if it can be constructed from a graph H, where \(V(H)=\{v_{1}, \ldots , v_{n}\}\) in the following way: For each vertex \(v_{i}\) of H, introduce a cycle, namely, \(v_{i},c_{i},b_{i},a_{i},v_{i}\) of length four in G. More formally, \(V(G) = V(H)\cup \{c_{i},b_{i},a_{i} \mid i\in [n]\}\) and \(E(G)=E(H) \cup \{v_{i}a_{i},a_{i}b_{i},b_{i}c_{i},v_{i}c_{i} \mid i\in [n]\}\).

Theorem 1

Let G be a \(GC_{4}\) graph constructed from a graph H, where \(V(H)=\{v_{1},\ldots ,v_{n}\}\), as in Definition 2. Then, \(\mu '_{ac}(G)=n\).

Proof

Consider a maximal acyclic matching, say \(M_{ac}\), in G. Note that \(M_{ac}\) must contain exactly one edge from cycle \(v_{i},c_{i},b_{i},a_{i},v_{i}\) for each \(i \in [n]\). This implies that \(\mu '_{ac}(G)\ge n\).

Next, let A be a maximal acyclic set of H obtained by applying the algorithm Maximal-Acy-Set(H) to H. Now, define a matching M in G as: \(M=\{a_{i}v_{i}\mid v_{i}\in A\}\cup \{a_{j}b_{j}\mid v_{j}\notin A\}\). Note that \(|M|=n\). Since M saturates every vertex in A, and A is a maximal acyclic set of H, it is not possible to include any of the edges from the set E(H) in the matching M without creating a cycle. Also, for each \(i \in [n]\), note that exactly one edge from the cycle \(v_{i},c_{i},b_{i},a_{i},v_{i}\) belong to any maximal acyclic matching in G. Thus, M is maximal in G, and since \(|M|=n\), \(\mu '_{ac}(G)\le n\). With this, we conclude the proof of the theorem. \(\square \)

Maximal-Acy-Set(G)

Full size image

Proposition 1

(Fürst (2019)) If G is a graph of maximum degree at most \(\mathrm {\Delta }\), then \(\mu _{ac}(G)\ge \frac{|E(G)|}{{\Delta }^2}\).

Theorem 2

Max-Acy-Matching is \(\textsf{APX}\)-hard for \(GC_{4}\) graphs.

Proof

Given a 7-regular graph H, an instance of Max-Acy-Matching, we construct a \(GC_{4}\) graph G, an instance of Max-Acy-Matching, by attaching a cycle \(v_{i},c_{i},b_{i},a_{i},v_{i}\) of length four to each \(v_{i}, i\in [n]\) (see Definition 2). Furthermore, it is known that Max-Acy-Matching is \(\textsf{APX}\)-complete for \((2r+1)\)-regular graphs for every fixed integer \(r\ge 3\) (Panda and Chaudhary 2023).

Now, consider the following claims.

Claim 1

H has an acyclic matching of cardinality k if and only if G has an acyclic matching of cardinality \(n+k\).

Proof

Let M be an acyclic matching in H of cardinality k. Then \(M'=M\cup \{b_{i}c_{i} \mid i \in [n]\}\) is an acyclic matching in G of cardinality \(n+k\).

Conversely, let \(M_{ac}\) be a maximum acyclic matching in G of cardinality \(n+k\). Let \(M=M_{ac}\cap E(H)\). It is easy to observe that for each \(i \in [n]\), any maximum acyclic matching in G contains exactly one edge from the cycle \(v_{i},c_{i},b_{i},a_{i},v_{i}\). So, \(|M|=(n+k)-n=k\). Also, as \(M\subset M_{ac}\), M is an acyclic matching in H. This completes the proof of the claim. \(\square \)

By Claim 1, we have the following.

Claim 2

If \(M_{B}^{*}\) is a maximum acyclic matching in G and \(M_{A}^{*}\) is a maximum acyclic matching in H, then \(|M_{B}^{*}|=|M_{A}^{*}|+n\).

By Proposition 1, it is known that any 7-regular graph H satisfies \(|M_{A}^{*}|\ge \frac{n}{14}\) (as for a 7-regular graph \(|E(H)|=\frac{7n}{2}\)). Therefore, by Claim 2, we have \(|M_{B}^{*}|=n+|M_{A}^{*}|\le 14|M_{A}^{*}|+|M_{A}^{*}|=15|M_{A}^{*}|\). Furthermore, by Claim 1, from any acyclic matching \(M_{B}\) in G, we can obtain an acyclic matching \(M_{A}\) in H such that \(|M_{A}|= |M_{B}|-n\). Now, \(|M_{A}^{*}|- |M_{A}|=(|M_{A}^{*}|+n)- (|M_{A}|+n)=|M_{B}^{*}|-|M_{B}|\). From the above two inequalities (\(|M_{B}^{*}|\le 15|M_{A}^{*}|\) and \(|M_{A}^{*}|- |M_{A}|=|M_{B}^{*}|-|M_{B}|\)), it follows that we have an \(\textsf{L}\)-reduction, where \(\beta =1\) and \(\alpha =15\). \(\square \)

Next, we prove that Max-Acy-Matching is polynomial-time solvable for \(GC_{3}\) graphs (see Definition 3), whereas Low-Acy-Matching for \(GC_{3}\) graphs is \(\textsf{APX}\)-hard. To achieve this, let us see the following definition.

Definition 3

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

Theorem 3

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

Proof

Let \(M=\{a_{i}b_{i} \mid i\in [n]\}\). Notice that \(|M|=n\). Since \(G[V_M]\) is a disjoint union of \(K_{2}'s\), M is an acyclic matching in G. Hence, \(\mu _{ac}(G)\ge n\).

Next, consider a maximum acyclic matching, say \(M_{ac}\), in G. If \(|M_{ac}|>n\), then \(M_{ac}\) must contain at least one edge from the edge set E(H), i.e., \(v_{i}v_{j}\in M_{ac}\) for some distinct \( i,j \in [n]\). Note that if \(v_{i}\) is saturated by \(M_{ac}\) for some \(v_{i}\in V(H)\), then \(a_{i}b_{i}\notin M_{ac}\). Define \(M=(M_{ac}\setminus \{v_{i}v_{j}\})\cup \{a_{i}b_{i},a_{j}b_{j}\}\). Note that M is an acyclic matching in G. As \(|M|>|M_{ac}|\), it contradicts that \(M_{ac}\) is maximum in G. Hence, \(\mu _{ac}(G)\le n\). This completes the proof of the theorem. \(\square \)

Theorem 4

For \(GC_{3}\) graphs, Low-Acy-Matching is \(\textsf{APX}\)-hard.

Proof

Given a 7-regular graph H, an instance of Max-Acy-Matching, we construct a \(GC_{3}\) graph G, an instance of Low-Acy-Matching, by attaching a cycle \(v_{i},b_{i},a_{i},v_{i}\) of length three to each \(v_{i}, i\in [n]\) (see Definition 3). It is well-established that Max-Acy-Matching is \(\textsf{APX}\)-complete for \((2r+1)\)-regular graphs for every fixed integer \(r\ge 3\) (Panda and Chaudhary 2023).

Next, we will partition the edges in G as follows: Type-I \(=\{b_{i}a_{i} \mid i\in [n]\}\), Type-II \(=\{v_{i}v_{j} \mid i,j\in [n]\}\), and Type-III \(=\{v_{i}a_{i},v_{i}b_{i} \mid i\in [n]\}\).

Claim 3

For every maximal acyclic matching M in a \(GC_3\) graph G, there exists a maximal acyclic matching \(M'\) in G such that \(|M'|= |M|\) and \(M'\) contains edges from Type-I and Type-II only.

Proof

To prove the claim, we first show that M is a maximal acyclic matching in G if and only if M is an acyclic matching and for each \(i\in [n]\), either \(a_{i}b_{i}\in M\) or M saturates \(v_{i}\).

In one direction, let M be a maximal acyclic matching in G and let k be a fixed but arbitrary integer from [n]. If \(v_k\) is not matched by M and \(a_{k}b_{k}\) is not in M, we can conclude that because \(v_k\) is not saturated by M, the addition of the edge \(a_{k}b_{k}\) to M results in another acyclic matching within the graph G. This contradicts the maximality of M in G.

In the other direction, let M be an acyclic matching in G such that for every \(i\in [n]\), either \(a_{i}b_{i}\in M\) or M saturates \(v_{i}\). Since every edge of G is either incident on some \(v_{i}, i\in [n]\) or is of the form \(a_{i}b_{i}, i\in [n]\), and for every \(i\in [n]\), \(|V_{M}\cap \{v_{i},a_{i},b_{i}\}|\le 2\), we say that M is maximal in G.

Now, we are ready to prove the claim. Note that we can conclude from the above discussion that in cases where there exists an edge in M from Type-III (for instance, \(v_{k}a_{k}\) for some \(k\in [n]\)), it is always possible to replace it with the corresponding Type-I edge (which will be \(a_{k}b_{k}\)) to obtain \(M'\). Note that given M is acyclic, \(M'\) is also acyclic. Now, it is left to prove that \(M'\) is maximal in G. Since \(M'\) is acyclic and for every \(i\in [n]\), either \(a_{i}b_{i}\in M'\) or \(M'\) saturates \(v_{i}\), as discussed earlier in the proof, we can conclude that \(M'\) is indeed maximal. Now, we can swap every Type-III edge with a Type-I edge, one by one, maintaining the size of the matching and the property of being maximal and acyclic. \(\square \)

Claim 4

If \(M_{B}^{*}\) is a minimum maximal acyclic matching in G and \(M_{A}^{*}\) is a maximum acyclic matching in H, then \(|M_{B}^{*}|=n-|M_{A}^{*}|\).

Proof

Consider the maximum acyclic matching \(M_{A}^{*}\) in H. This implies that \(n-2|M_{A}^{*}|\) vertices are unsaturated, and \(2|M_{A}^{*}|\) vertices are saturated by \(M_{A}^{*}\) in H. Define \(M_{B}= \{a_{i}b_{i} \mid v_{i}\) is unsaturated by \(M_{A}^{*}\}\cup M_{A}^{*}\) in G. One can readily observe that \(M_{B}\) is a maximal acyclic matching in G. Furthermore, as \(|M_{B}|=(|M_{A}^{*}|+n-2|M_{A}^{*}|)=n-|M_{A}^{*}|\), it follows that \(|M_{B}^{*}|\le n-|M_{A}^{*}|.\)

By Claim 3, there exists a minimum maximal acyclic matching \(M_{B}^{*}\) in G such that \(M_{B}^{*}\) contains edges from Type-I and Type-II only. Let \(M_{B_{I}}^{*}\cup M_{B_{II}}^{*}\) be a partition of \(M_{B}^{*}\) such that \(M_{B_{I}}^{*}\) contains edges from Type-I and \(M_{B_{II}}^{*}\) contains edges from Type-II. Since \(M_{B}^{*}\) is maximal, \(|M_{B_{I}}^{*}|=n-2|M_{B_{II}}^{*}|\). This implies that \(|M_{B}^{*}|=|M_{B_{II}}^{*}|+(n-2|M_{B_{II}}^{*}|)=n-|M_{B_{II}}^{*}|\). Since \(M_{B_{II}}^{*}\subset M_{B}^{*}\), \(M_{B_{II}}^{*}\) is an acyclic matching in H and \(|M_{B_{II}}^{*}|\le |M_{A}^{*}|\). As \(|M_{B_{II}}^{*}|=n-|M_{B}^{*}|\), \(n-|M_{B}^{*}|\le |M_{A}^{*}| \).

Therefore, \(|M^*_B| = n - |M^*_A|.\) \(\square \)

We now revisit the proof of Theorem 4. By Proposition 1, it is known that any 7-regular graph H satisfies the inequality \(|M_{A}^{*}|\ge \frac{n}{14}.\) Consequently, we can derive that \(|M_{B}^{*}|=n-|M_{A}^{*}|\le 14|M_{A}^{*}|-|M_{A}^{*}|=13|M_{A}^{*}|\). Additionally, consider a maximal acyclic matching M in graph G. By Claim 3, we can identify a maximal acyclic matching \(M_{B}\) in G such that \(|M|=|M_{B}|\) and \(M_{B}\) contains edges from Type-I and Type-II only. Let \(M_{B_{I}}\cup M_{B_{II}}\) be a partition of \(M_{B}\) such that \(M_{B_{I}}\) contains edges from Type-I and \(M_{B_{II}}\) contains edges from Type-II. Given the maximality of \(M_{B}\), it follows that \(|M_{B_{I}}|=(n-2|M_{B_{II}}|)\), resulting in \(|M_{B}|=n-|M_{B_{II}}|\). Here, \(M_{B_{II}}\) is a desired acyclic matching in H. For our convenience, let \(M_{B_{II}}=M_{A}\). Now, \(|M_{A}^{*}|- |M_{A}|=|M_{A}^{*}|-|M_{A}|+n-n=(n-|M_{A}|)-(n-|M_{A}^{*}|)\le |(|M_{B}^{*}|-|M_{B}|)|\) (by Claim 4). From the above two inequalities (\(|M_{B}^{*}|\le 13|M_{A}^{*}|\) and \(|M_{A}^{*}|- |M_{A}|\le |(|M_{B}^{*}|-|M_{B}|)|\)), it follows that it is an \(\textsf{L}\)-reduction where \(\beta =1\) and \(\alpha =13\). \(\square \)

4.1 Bipartite graphs with maximum degree 6

Theorem 5

Decide-Low-Acy-Matching is \({\textsf{NP}}\)-complete for bipartite graphs with maximum degree 6.

Proof

Given a bipartite graph G with maximum degree 6 and a matching M, it can be verified in polynomial time whether M is a maximal acyclic matching of G or not. Also, the number of edges in M is at most \(\ell \) or not can be checked in polynomial time. Hence, Decide-Low-Acy-Matching is in NP for bipartite graphs with maximum degree 6.

Next, we prove that Decide-Low-Acy-Matching is \({\textsf{NP}}\)-hard for bipartite graphs of degree at most 6 by establishing a polynomial-time reduction from 3-3-SAT (a variant of 3-SAT), where each variable occurs at most thrice in the 3-CNF formula, and no clause contains both a variable and its negation. Note that 3-3-SAT is \({\textsf{NP}}\)-complete (Tovey 1984).

Let \(\psi \) be an instance of 3-3-SAT with m clauses \(C_{1}, C_{2},..., C_{m}\) over p variables \(x_{1},x_{2},...,x_{p}.\) We construct a bipartite graph \(G_\psi \) on \(10p+2m\) vertices and at most \(11p+7m\) edges from \(\psi \) as follows.

• For each variable \(x_{i}\), where \(i\in [p]\), we construct a variable gadget \(F_{i}\) consisting of 10 vertices \(V(F_{i})=\{a_{i},b_{i},c_{i},d_{i},x_{i},y_{i},\overline{x}_{i},u_{i},v_{i},w_{i}\}\) and 11 edges \(E(F_{i})=\{a_ib_i,b_ic_i,\) \(c_id_i, d_ia_i,b_ix_i\) \(,x_iu_i,x_iy_i,y_iv_i, y_i\overline{x}_i,\overline{x}_ib_i, \overline{x}_iw_i\}\). For each \(i\in [p]\), note that \(F_{i}\) is a bipartite graph.

• For each clause \(C_{j}\), where \(j\in [m]\), we construct a clause gadget \(H_{j}\) consisiting of 2 vertices \(\{r_j, s_j\}\) and one edge \(\{r_{j}s_{j}\}\).

• Edges that link variable gadgets with clause gadgets are defined in the following way: If \(x_i\) is present in \(C_j\), then we introduce the edges \(r_{j}x_i\) and \(s_{j}y_i\). If \(\overline{x}_i\) is present in \(C_j\), then we introduce the edges \(r_{j}\overline{x}_i\) and \(s_{j}y_i\).

Graph \(G_{\psi }\) corresponding to the instance \(\psi = (x_{1} \vee x_{2} \vee \overline{x}_{3}) \wedge (\overline{x}_{1} \vee \overline{x}_{2} \vee x_{3}) \)

Full size image

Figure 1 illustrates the construction of graph \(G_{\psi }\) from an instance \(\psi \) of 3-3-SAT. Note that it takes polynomial time to construct graph \(G_{\psi }\) because it has \(10p+2m\) vertices and at most \(11p+7m\) edges.

Since every variable occurs a maximum of three times in \(\psi \), it follows that for each \( i \in [p]\), the degrees in graph \(G_{\psi }\) satisfy the conditions \(d_{G_{\psi }}(x_i) \le 6\), \(d_{G_{\psi }}(\overline{x}_i) \le 6\), and \(d_{G_{\psi }}(y_i) \le 6\). Furthermore, since each clause \(C_j\) has exactly 3 lals, \(d_{G_{\psi }}(r_j) = d_{G_{\psi }}(s_j) = 4\) for each \( j \in [m]\). As all other vertices in \(G_{\psi }\) have degree at most four, \(G_{\psi }\) has maximum degree at most 6. \(G_{\psi }\) is a bipartite graph as (i) each variable gadget and clause gadget is a bipartite graph, and (ii) vertex \(y_i\) in \(F_i\) can be adjacent to vertices \(s_k\) (where \(k\in [m]\)) in clause gadgets, and vertices \(x_i\) and \(\overline{x}_i\) in \(F_i\) can be adjacent to vertices \(r_k\) (where \(k\in [m]\)) in clause gadgets. Therefore, \(X=\{x_{i},\overline{x}_{i},a_{i},c_{i},v_{i}\mid i\in [p]\}\cup \{s_{j}\mid j\in [m]\}\) and \(Y=\{u_{i},y_{i},w_{i},b_{i},d_{i}\mid i\in [p]\}\cup \{r_{j}\mid j\in [m]\}\) is a bipartition of \(V(G_{\psi })\).

Now, we claim that \(\psi \) is satisfiable if and only if \(\mu '_{ac}(G_{\psi }) = 2p.\)

Suppose there exists a truth assignment \(\sigma \) that satisfies \(\psi \). From \(\sigma \), we construct an edge set \(M_{\sigma }\) of \(G_{\psi }\) as follows. If \(\sigma (x_i)\) = true, then \(x_{i}y_{i}\) and \(b_{i}c_{i}\) are in \(M_{\sigma }\), otherwise the edges \(\overline{x}_{i}y_{i}\) and \(b_{i}c_{i}\) are in \(M_{\sigma }\).

Since \(\sigma \) satisfies \(\psi \), every clause \(C_j\) in \(\psi \) receives at least one true literal \(l_t\) (\(l_t\) is either \(x_t\) or \(\overline{x}_t\)) under \(\sigma \). Since \(l_t\) in \(C_j\) evaluates to true under \(\sigma \), the edge \(l_ty_t\) is in \(M_{\sigma }\). As a result of which, the edge \(r_{j} s_{j}\) cannot be added to \(M_{\sigma }\) (otherwise, a cycle of length 4 will be created in the subgraph induced by the matched vertices). Since \(M_{\sigma }\) is a matching and \(l_ty_t\in M_{\sigma }\), \(y_t\overline{l_t},y_{t}s_{j},l_{t}r_{j} \notin M_{\sigma }\). At the same time, for each variable \(x_i\), as \(b_{i} c_{i} \in M_{\sigma }\), none of the edges from the set \(\{a_{i}d_{i}, a_{i}b_{i}, c_{i}d_{i},x_{i}b_{i},\overline{x}_{i}b_{i}\}\) can be added to \(M_{\sigma }\). Moreover, since the vertices \(b_{i}, y_{i}\) and \(x_{i}\) (or \(\overline{x}_{i}\)) are saturated by \(M_{\sigma }\), none of the edges from the set \(\{x_{i}u_{i}, y_{i} v_{i}, \overline{x}_{i}w_{i}\}\) can be added to \(M_{\sigma }\). It can be observed that the subgraph \(G[V(M_{\sigma })]\) is a disjoint union of p paths on 4 vertices, which implies that \(M_{\sigma }\) is an acyclic matching of \(G_{\psi }\). Hence, it follows that \(M_{\sigma }\) is a maximal acyclic matching of size exactly 2p.

For the converse part, let us assume that \(G_{\psi }\) has a maximal acyclic matching M of cardinality 2p. Under this assumption, we will prove that \(\psi \) is satisfiable. Let \(E_{i}=\{b_{i}c_{i},c_{i}d_{i},d_{i}a_{i},a_{i}b_{i}\}\) for each \(i\in [p]\). To prove that \(\psi \) is satisfiable, we need the following claims (Claims 5–7).

Claim 5

For each \(i \in [p]\), \(|M\cap E_{i}|= 1\).

Proof

First, let us assume that \(|M\cap E_{j}|>1\) for some \(j\in [p]\). In this case, \(G[V_{M}]\) contains the cycle \(b_{j},a_{j},d_{j},c_{j},b_{j}\) of length 4, a contradiction. Next, if \(|M\cap E_{j}|=0\) for some \(j\in [p]\), then \(M \cup \{d_{j}a_{j}\}\) is an acyclic matching of G, contradicting the maximality of M. Therefore, \(|E_{i} \cap M|= 1\) for each \(i \in [p]\). \(\square \)

Claim 6

For each \(i \in [p]\), \(|M\cap E(F_{i})|=2\), and M contains no other edges of \(G_\psi \).

Proof

As \(E_{i}\subset E(F_{i})\), it is clear by Claim 5 that \(|E(F_{i}) \cap M|\ge 1\) for each \(i\in [p]\). Next, suppose that for some \(l\in [p]\), \(|M\cap E(F_{l})|= 1\). By Claim 5, \(M\cap E(F_{l})\subseteq E_{l}\). Since M is maximal, \(M\cup \{x_lu_l\}\) is not an acyclic matching. So either (A.I) \(x_lr_j \in M\) for some \(j \in [m]\) or (A.II) \(y_ls_t \in M\) for some \(t \in [m]\) and some clause edge \(r_ks_k \in M\), for some \(k \in [m]\), corresponding to clause \(C_k\) containing \(x_l\), or (A.III) \(y_l\), \(\overline{x}_l\), and \(b_l\) are M-saturated (in this case, the M-mates of \(y_{l}\) and \(\overline{x}_l\) belong to \(V(G_{\psi })\setminus V(F_{l})\)). Similarly, as \(M\cup \{\overline{x}_lw_l\}\) is not an acyclic matching, so either (B.I) \(\overline{x}_lr_j \in M\) for some \(j \in [m]\) or (B.II) \(y_ls_t \in M\) for some \(t \in [m]\) and some clause edge \(r_ks_k \in M\), for some \(k \in [m]\), corresponding to clause \(C_k\) containing \(\overline{x}_l\), or (B.III) \(y_l\), \(x_l\), and \(b_l\) are M-saturated (in this case, the M-mates of \(y_{l}\) and \(x_l\) belong to \(V(G_{\psi })\setminus V(F_{l})\)). On the similar lines, as \(M\cup \{y_{l}v_{l}\}\) is not an acyclic matching, so, either (C.I) \(x_lr_j \in M\) (or \(\overline{x}_lr_j \in M\)) for some \(j \in [m]\) and some clause edge \(r_ks_k \in M\), for some \(k \in [m]\), corresponding to clause \(C_k\) containing \(x_l\) (or \(\overline{x}_l\)), (C.II) \(x_l\), \(\overline{x}_l\), and \(b_l\) are M-saturated (in this case, the M-mates of \(x_{l}\) and \(\overline{x}_l\) belong to \(V(G_{\psi })\setminus V(F_{l})\)), (C.III) \(y_ls_j \in M\) for some \(j \in [m]\).

From the discussion above, observe that at least two edges outside the variable gadgets must belong to M, and at least one of them must come from the set \(\{x_{l}r_{j}, \overline{x}_{l}r_{j}, y_{l}s_{j}\}\) for some \(j \in [m]\).

Furthermore, note that, as \(|M|=2p\), \(|E(F_{i}) \cap M|\ge 1\) for each \(i\in [p]\), and M contains at least two edges outside the variable gadgets, there must exist some variable gadget \(F_{q} (q \ne l)\) with \(|M\cap E(F_{q})|= 1\). Now, again M must contain at least two edges outside the variable gadgets, and at least one of them (the edges outside the variable gadget) should come from the set \(\{x_{q}r_{j'}, \overline{x}_{q}r_{j'}, y_{q}s_{j'}\}\) for some \(j' \in [m]\). It is easy to note that corresponding to each variable gadget \(F_{i}\) with \(|M\cap E(F_{i})|=1\), at least one unique edge and some other edges (these may be common among different variable gadgets) come from the non-variable gadgets. From the arguments given above, it is clear that \(|M|>2p\), a contradiction (to the fact that \(|M|=2p\)). Hence, \(|M\cap E(F_{i})|\ge 2\) for each \(i \in [p]\) and since \(|M|=2p\), \(|E(F_{i}) \cap M|= 2\) for each \(i \in [p]\). Therefore, every matching edge must come from the variable gadget only. \(\quad \square \)

Claim 7

For each \(i \in [p]\), M must contain exactly one edge from \(\{x_iy_i, \overline{x}_iy_i\} \) and exactly one edge from \(\{a_ib_i,b_ic_i\}\).

Proof

By Claim 6, every matching edge comes only from the variable gadgets and \(|M\cap E(F_{i})|=2\) for each \(i\in [p]\). Let \(i\in [p]\) be some fixed but arbitrary integer. Note that either \(x_iu_i\) or \(\overline{x}_iw_i\) is not there in M as M contains exactly two edges of \(F_i\), and by Claim 5, M contains exactly one edge from the edge set \(E_{i}=\{b_{i}c_{i},c_{i}d_{i},d_{i}a_{i},a_{i}b_{i}\}\). Without loss of generality, let \(x_iu_i \notin M\). Note that M must contain at least one edge from the set \(\{x_iy_i,y_i\overline{x}_i,\overline{x}_ib_i,b_ix_i\}\). Else, if \(M \cap \{x_iy_i,y_i\overline{x}_i,\overline{x}_ib_i,b_ix_i\}=\emptyset \), then \(M \cup \{x_iu_i\}\) is again an acyclic matching of \(G_{\psi }\) contradicting the maximality of M. Next, if neither \(x_{i}y_{i}\) nor \(\overline{x}_{i}y_{i}\) is in M, then \(M \cup \{y_iv_i\}\) is an acyclic matching of \(G_{\psi }\), a contradiction to the fact that M is maximal in \(G_{\psi }\). Without loss of generality, let \(x_iy_i \in M\). By Claim 6, for each \(i\in [p]\), \(|M\cap E(F_{i})|=2\) and by Claim 5, for each \(i\in [p]\), \(|M\cap E_{i}|=1\). Since \(x_{i}y_{i}\in M\), it implies that \(x_{i}u_{i},y_{i}v_{i},\overline{x}_{i}w_{i},y_{i}\overline{x}_{i},x_{i}b_{i},\overline{x}_{i}b_{i}\notin M\) (as the second matching edge of \(F_{i}\) will come from the set \(E_{i}\)). Next, note that if neither \(a_ib_i\) nor \(b_ic_i\) is in M, then \(M \cup \{\overline{x}_iw_i\}\) is again a maximal acyclic matching of \(G_{\psi }\), a contradiction to the fact that M is a maximal acyclic matching of \(G_{\psi }\). So M must contain exactly one edge from \(\{x_iy_i, \overline{x}_iy_i\} \) and exactly one edge from the set \(\{a_ib_i,b_ic_i\}\) for each \(i \in [p]\). \(\square \)

Since for each \(i \in [p]\), M contains exactly one of \(x_{i}y_{i}\) and \(\overline{x}_{i}y_{i}\), we define a satisfying truth assignment \(\sigma \) for \(\psi \) with \(\sigma (x_i)\) = true if and only if \(x_i y_i\in M\). Now since \(r_{j} s_{j} \notin M\), either \(r_{j}\) is adjacent to some \(x_{i}\) and \(x_{i}y_{i}\in M\) or \(r_{j}\) is adjacent to some \(\overline{x}_{i}\) and \(\overline{x}_{i}y_{i}\in M\). This implies that every clause receives at least one true literal under \(\sigma \). Therefore, \(\psi \) is satisfiable. \(\square \)

4.2 Planar perfect elimination bipartite graphs

In order to establish the \(\textsf{NP}\)-completeness, we give a polynomial-time reduction from the following problem:

Proposition 2

Krishnamoorthy and Deo (1979) Max-Forest is \({\textsf{NP}}\)-complete for planar bipartite graphs.

Theorem 6

Decide-Low-Acy-Matching is \({\textsf{NP}}\)-complete for planar perfect elimination bipartite graphs.

Proof

For a planar perfect elimination bipartite graph G and a matching M, note that Decide-Low-Acy-Matching belongs to the class NP.

Consider a planar bipartite graph denoted as G, which serves as an instance of the Max-Forest problem. Furthermore, let \(V(G)=Y \uplus X\), where \(Y=\{y_{1},\ldots ,y_{l}\}\) and \(X=\{x_{1},\ldots ,\) \(x_{k}\}\). We construct a graph \(G'\), which is planar perfect elimination bipartite, an instance of Decide-Low-Acy-Matching, as follows.

We construct \(G'\) from G by adding new vertices and edges to G. Let \(V(G')=Y' \uplus X'\). For every vertex \(x_i \in X\), we introduce a vertex set \(X_{i}= \{t_{i}, s_{i}, r_{i}, q_{i}, p_{i}\}\) of 5 vertices and an edge set \(E_{X_{i}}=\{x_{i}p_{i},x_{i}r_{i},x_{i}t_{i},\) \(p_{i}q_{i},q_{i}r_{i},r_{i}s_{i},\) \(t_{i}s_{i}\}\) of 7 edges to \(G'\). Similarly, for each vertex \(y_j \in Y\), we introduce a vertex set \(Y_j= \{e_{j},d_{j},c_{j},b_{j},a_{j}\}\) of 5 vertices and an edge set \(E_{Y_{j}}=\{y_{j}a_{j},y_{j}c_{j},\) \(y_{j}e_{j},a_{j}b_{j},b_{j}c_{j},c_{j}d_{j},\) \(e_{j}d_{j}\}\) of 7 edges to \(G'\). See Fig. 2 for an illustration of this construction.

Observe that \(G'\) is a bipartite graph with partitions, \(X'\) and \(Y'\), where \(X'=\{x_{i},q_{i},s_{i} \mid i\in [k]\}\cup \{a_{j}, c_{j}, e_{j} \mid j\in [l]\}\) and \(Y'=\{y_{j},b_{j},d_{j} \mid j\in [l]\} \cup \{p_{i},r_{i},t_{i} \mid i\in [k]\}\). Furthermore, \(G'\) is also a perfect elimination bipartite graph as \((a_{1}b_{1},a_2b_2,\ldots , a_{l}b_{l},e_{1}d_{1},\) \(e_2d_2,\ldots , e_{l}d_{l}, y_{1}c_{1}, y_2c_2 \) \(,\ldots , y_{l}c_{l},p_{1}q_{1},\) \(p_2q_2,\ldots ,p_{k}q_{k},\) \(t_{1}s_{1}, t_2s_2,\ldots , t_{k}s_{k},x_{1}r_{1}, x_2r_2,\ldots , x_{k}r_{k})\) is a perfect edge elimination ordering of \(G'\). Additionally, it is important to recognize that due to the input graph G being planar, the resultant graph \(G'\) is also planar. Finally, see that it takes polynomial time to construct \(G'\) from G because \(|Y'|=6|Y|\), \(|X'|=6|X|\), and \(|E(G')|=7|Y|+7|X|+|E(G)|\).

An illustration of the construction of \(G'\) from G

Full size image

Now, consider the following claims (Claims 8-11).

Claim 8

If M is a minimum maximal acyclic matching in \(G'\), then, \(1\le |M\cap E_{X_{i}}|\le 2\), for each \(i \in [k]\), and \(1\le |M\cap E_{Y_{j}}|\le 2\), for each \(j\in [l]\). Furthermore, (a) \(x_{i}r_{i}\in M\) if and only if \(|E_{X_{i}}\cap M|=1\), (b) \(y_{j}c_j \in M\) if and only if \(|E_{Y_{j}} \cap M|=1\).

Proof

It is easy to note that \(1\le |M\cap E_{X_{i}}|\le 2\), for each \(i \in [k]\), and \(1\le |M\cap E_{Y_{j}}|\le 2\), for each \(j \in [l]\) (as M is maximal in \(G'\)). For the second part of the claim, we will prove only the first statement as the proof of the second statement is similar. Let us first assume that \(|M\cap E_{X_{i}}|=1\) for some fixed \(i \in [k]\). Now, consider the following two possible cases.

Case 1 \(x_{i}\) is not saturated by M

If M does not saturate \(x_i\), then note that \(|E_{X_{i}}\cap M|=2\) (as M is maximal). It contradicts our assumption that \(|E_{X_{i}}\cap M|=1\). So, this case does not arise.

Case 2 \(x_{i}\) is saturated by M

If \(x_ir_i\in M\), then we are done. So, first, assume that \(x_ip_i\) (resp. \(x_it_i\)) belongs to M. Since \(|M\cap E_{X_{i}}|=1\), in this case, edge \(r_{i}s_{i}\) (resp. \(q_{i}r_{i}\)) can be added to M without violating the condition of an acyclic matching, which is a contradiction to the fact that M is maximal in \(G'\). Thus, the only possibility left is that \(x_{i}y_{j}\in M\) for some \(y_{j}\in Y\). In this case, we can construct another maximal acyclic matching \(M'\) as follows: Let \(M'=(M \cup \{x_{i}r_{i},y_{j}c_{j}\}) {\setminus } (\{x_{i}y_{j}\} \cup (E_{X_{i}}\cap M) \cup (E_{Y_{j}}\cap M))\). Since \(|M'|<|M|\), it is a contradiction to the fact that M has minimum cardinality in \(G'\). Hence, if \(|M\cap E_{X_{i}}|=1\), then \(x_ir_i\in M\).

Conversely, let \(x_{i}r_{i}\in M\). Since \(G[V_M]\) is acyclic, it is easy to see that none of the remaining edges from the edge set \(E_{X_{i}}\) can be in M. Hence, \(|M\cap E_{X_{i}}|=1\). \(\square \)

Claim 9

Given that M is a minimum maximal acyclic matching in \(G'\), the following are true: (a) \(x_{i}r_{i}\in M\) whenever \(x_{i}\in V_{M}\) for some \(i\in [k]\), (b) \(y_{j}c_j \in M\) whenever \(y_{j}\in V_{M}\) for some \(j\in [l]\).

Proof

We will prove only the first statement as the proof of the second statement is similar. For all \(i\in [k]\), if \(x_{i}\in V_{M}\) implies that \(x_{i}r_{i}\in M\), then we are done. So assume there exists an \(i\in [k]\) such that \(x_{i}\in V_{M}\) but \(x_{i}r_{i}\notin M\). This implies that \(|M\cap E_{X_{i}}|=2\) (by Claim 8). If the M-mate of \(x_{i}\) is either \(p_{i}\) or \(t_{i}\), then define \(M'=(M{\setminus } (M\cap E_{X_{i}}))\cup \{x_{i}r_{i}\}\). Note that \(M'\) is a maximal acyclic matching in \(G'\) and \(|M'|<|M|\), a contradiction to the fact that M has minimum cardinality in \(G'\).

Next, assume that the M-mate of \(x_{i}\) is \(y_{j}\) for some \(j\in [l]\). By Claim 8, \(|M\cap E_{Y_{j}}|=2\). Define \(M'=(M \cup \{x_{i}r_{i},y_{j}c_{j}\}) {\setminus } (\{x_{i}y_{j}\} \cup (M\cap E_{X_{i}}) \cup (M \cap E_{Y_{j}}))\). Note that \(M'\) is a maximal acyclic matching in \(G'\) and \(|M'|<|M|\). Since \(|M'|<|M|\), it contradicts the fact that M has minimum cardinality in \(G'\). Thus, if \(x_{i}\in V_{M}\), then \(x_{i}r_{i}\in M\). \(\square \)

Claim 10

If \(S_{ac}\) is a maximum acyclic set of G, then there exists a minimum maximal acyclic matching \(M_{ac}\) in \(G'\) such that \(|M_{ac}|=2|Y|+2|X|-|S_{ac}|\).

Proof

Let \(S_{ac}\) be a maximum acyclic set of G. Define a matching \(M_{ac}=\{x_{i}r_{i}\mid x_{i}\in S_{ac}, i\in [k] \} \cup \{y_{j}c_{j} \mid y_{j}\in S_{ac}, j\in [l] \} \cup \{p_{i}q_{i},t_{i}s_{i}\mid x_{i}\notin S_{ac}, i\in [k] \} \cup \{a_{j}b_{j},e_{j}d_{j}\mid y_{j}\notin S_{ac}, j\in [l]\}\) in \(G'\). Note that \(|M_{ac}|=|S_{ac}|+2\cdot (|X|+|Y|-|S_{ac}|)=2|Y|+2|X|-|S_{ac}|\). Next, we will show that \(M_{ac}\) is a minimum maximal acyclic matching in \(G'\).

Given that \(S_{ac}\) is an acyclic set, it is evident that \(G[V_{M_{ac}}]\) is also acyclic. Now, we aim to establish that \(M_{ac}\) is maximal in \(G'\). As indicated in Claim 8, it is clear that no additional edges from the sets \(E_{X_{i}}\) and \(E_{Y_{j}}\) (with the exception of those already included) can be incorporated into \(M_{ac}\). Furthermore, for the sake of contradiction, let us assume the existence of an edge \(x_{\alpha }y_{\beta }\in E(G)\) such that \(G[\{ x_{\alpha }, y_{\beta }\} \cup V_{M_{ac}}]\) is a forest. It is clear that \(y_{\beta },x_{\alpha }\notin S_{ac}\) (else by the definition of \(M_{ac}\), \(y_{\beta }\) and \(x_{\alpha }\) must already be saturated by \(M_{ac}\)). Given that \(G[\{x_{\alpha }, y_{\beta }\} \cup V_{M_{ac}}]\) is a forest, it follows that \(S_{ac}\cup \{x_{\alpha },y_{\beta } \}\) must also be an acyclic set of G. This contradicts the fact that \(S_{ac}\) is a maximum acyclic set of G. Therefore, we conclude that \(M_{ac}\) is maximal as well as an acyclic matching in \(G'\).

Now, we will show that \(M_{ac}\) has the smallest possible size. To achieve this, consider a minimum maximal acyclic matching M in \(G'\). We claim that \(|M|=|M_{ac}|\). By Claim 8, for each \(i \in [k]\) and for each \(j \in [l]\), we have \(1\le |M\cap E_{Y_{j}}|,|M\cap E_{X_{i}}|\le 2\). Let \(S=(V_M\cap Y) \cup (V_M\cap X) \). For every \(x_{i}\in S\), where \(i\in [k]\), by Claim 9, \(x_{i}r_{i}\in M\), and by Claim 8, for such an \(x_i\), \(|M\cap E_{X_{i}}|=1\). Similarly, for every \(y_{j}\in S\), where \(j\in [l]\), by Claim 9, \(y_{j}c_{j}\in M\), and by Claim 8, for such a \(y_{j}\), \(|M\cap E_{Y_{j}}|=1\) Moreover, by Claims 8 and 9, for \(x_{i},y_{j}\notin S\), \(|M\cap E_{X_{i}}|=|M\cap E_{Y_{j}}|=2\). Given that M is maximal, we obtain \(|M|=2|Y|+2|X|-|S|\). Note that the set S is an acyclic set as it comprises a subset of M-saturated vertices of an acyclic matching. As \(S_{ac}\) is a maximum acyclic set of G, \(|S_{ac}|\ge |S|\), thus \(|M_{ac}|=2|Y|+2|X|-|S_{ac}|\le 2|Y|+2|X|-|S|=|M|\). As M represents a minimum maximal acyclic matching, its size cannot be smaller than that of any other maximal acyclic matching in the graph \(G'\). Consequently, we have \(|M_{ac}| = |M|\). \(\square \)

Claim 11

If \(M_{ac}\) is a minimum maximal acyclic matching in \(G'\), then there exists a maximum acyclic set \(S_{ac}\) of G such that \(|M_{ac}|=2|Y|+2|X|-|S_{ac}|\).

Proof

Let \(M_{ac}\) be a minimum maximal acyclic matching in \(G'\). Let \(S_{ac}=(V_{M_{ac}}\cap X)\cup (V_{M_{ac}}\cap Y)\). As \(S_{ac}\subseteq V_{M_{ac}}\), then, clearly, \(S_{ac}\) is an acyclic set of G. Further, by Claim 8, for each i and j such that \(x_{i},y_{j}\notin S_{ac}\), \(|M_{ac}\cap E_{X_{i}}|=|M_{ac}\cap E_{Y_{j}}|=2\). Next, by Claim 9, note that for each i and j such that \(x_{i},y_{j}\in S_{ac}\), \(x_{i}r_{i},y_{j}c_{j}\in M_{ac}\), which in turn by Claim 8 implies that \(|M_{ac}\cap E_{X_{i}}|=|M_{ac}\cap E_{Y_{j}}|=1\). By the arguments given above, we observe that \(|S_{ac}|=2|Y|+2|X|-|M_{ac}|\). Now, we will show that \(S_{ac}\) is a maximum acyclic set of G. For this purpose, consider a maximum acyclic set, say S, of G. We claim that \(|S|=|S_{ac}|\). By the proof of Claim 10, observe that, given a maximum acyclic set S of G, we can construct a minimum maximal acyclic matching, say M, in \(G'\) such that \(|M|=2|Y|+2|X|-|S|\). If \(|S|>|S_{ac}|\), then \(|M_{ac}|=2|Y|+2|X|-|S_{ac}|> 2|Y|+2|X|-|S|=|M| \). This leads to a contradiction to the fact that \(M_{ac}\) is a minimum cardinality maximal acyclic matching in \(G'\). Thus, \(|S|=|S_{ac}|\). \(\square \)

By Proposition 2 and Claims 10–11, we prove the \({\textsf{NP}}\)-completeness. \(\square \)

In this section, we present a reduction from 3-SAT, with the constraint that none of the clauses includes both a variable and its negation. It is well-established that 3-SAT is \({\textsf{NP}}\)-complete (Garey and Johnson 1979).

Lemma 1

Let \(\psi =C_1 \wedge C_2 \wedge \ldots \wedge C_m\) be an instance of 3-SAT over p variables \(X=\{x_1, x_2, \ldots ,x_p\}\). Then, for every instance \(\psi \) of 3-SAT, and for every integer \(\alpha \ge 2\), there exists a bipartite graph \(G_{\psi ,\alpha }\) on \(8p+2\alpha p(m+p)\) vertices such that the following condition holds:

Proof

For a given instance \(\psi \) of 3-SAT with a set \(\{C_{1}, C_{2},\ldots ,C_{m}\}\) of m clauses and a set \(\{x_{1},x_{2},\ldots ,x_{p}\}\) of p variables, and for a given integer \(\alpha \ge 2\), we construct a bipartite graph \(G_{\psi ,\alpha }\) on \(8p+2pm\alpha +2 \alpha p^{2}\) vertices in the following way:

• For each variable \(x_i\), we construct a variable gadget consisting of \(8 + 2\alpha p\) vertices \( \{a_{i,k}, d_{i,k} \mid k \in [p\alpha ]\} \cup \{x_i, \overline{x}_i, y_i, u_i, v_i, w_i, b_i, c_i\}\) and edges \(\{x_{i}y_{i},y_{i}\overline{x}_{i},\) \(\overline{x}_{i}b_{i}, b_{i}x_{i},x_{i}u_{i},\) \(y_{i}v_{i},\overline{x}_{i}w_{i},b_{i}c_{i}\}\cup \{b_{i}a_{i,k},a_{i,k}d_{i,k},c_{i}d_{i,k} \mid k \in [p\alpha ]\}\). See Fig. 3 for an illustration. It is easy to observe that the vertex gadget forms a bipartite graph.

• For every clause \(C_j\), we create a clause gadget that consists of \(2p\alpha \) vertices \(\{r_{j,k}, s_{j,k} \mid k \in [p\alpha ]\}\) and \(p\alpha \) edges \(\{r_{j,k}s_{j,k} \mid k \in [p\alpha ]\}.\)

• Edges that connect vertex gadgets with clause gadgets are defined as follows: When \(x_i\) is present in the clause \(C_j\), then we introduce the edges \(\{s_{j,k}y_i, r_{j,k}x_i \mid k \in [p\alpha ]\}\). When \(\overline{x}_i\) is present in the clause \(C_j\), then we introduce the edges \(\{r_{j,k}\overline{x}_i, s_{j,k}y_i \mid k \in [p\alpha ]\}\).

Graph \(G_{\psi ,\alpha }\) corresponding to \(\psi =(x_{1} \vee \overline{x}_{2} \vee x_{3})\wedge (\overline{x}_1 \vee x_2 \vee \overline{x}_3)\), an instance of 3-SAT. An edge from a vertex v to a box symbolizes \(p\alpha \) edges between v and every vertex contained within that box

Full size image

We refer to Fig. 3, for an illustration of this construction. Note that \(G_{\psi ,\alpha }\) is a bipartite graph with \(V(G_{\psi ,\alpha })=2\alpha p(m+p)+8p\) and \(E(G_{\psi ,\alpha })\le \alpha p(7\,m+3p)+8p\).

Claim 12

\(G_{\psi ,\alpha }\) has a maximal acyclic matching M of cardinality at most 2p whenever \(\psi \) is satisfiable.

Proof

Let us assume that \(\psi \) is satisfiable and there exists a truth assignment \(\sigma \) that satisfies every clause in \(\psi \). Now, from the truth assignment \(\sigma \), we construct a maximal acyclic matching \(M_{\sigma }\) of \(G_{\psi ,\alpha }\) as follows: If \(\sigma (x_{i})\) is true, then include the edges \(x_{i}y_{i}\) and \(b_{i} c_{i}\) in \(M_{\sigma }\), otherwise include the edges \(\overline{x}_{i}y_{i}\) and \(b_{i}c_{i}\) in \(M_{\sigma }\).

Since \(\psi \) is satisfiable, every clause \(C_j\) in \(\psi \) receives at least one true literal \(l_t\) (\(l_t\) is either \(x_t\) or \(\overline{x}_t\)) under the truth assignment \(\sigma \). Since \(l_t \in C_{j}\) and \(l_t\) evaluates to true under \(\sigma \), \(l_ty_t \in M_{\sigma }\). As a result of which, none of the edges of the form \(r_{j,k}s_{j,k}\), \(r_{j,k}l_t\) and \(s_{j,k}y_t\) (for any \( k \in [p\alpha ]\)) can be added to \(M_{\sigma }\) (because the inclusion of any one of these edges to \(M_{\sigma }\) will violate the property of an acyclic matching).

If all literals present in \(C_{j}\) evaluate to true under \(\sigma \), then the edges joining the clause gadget \(C_{j}\) and variable gadgets cannot be added to \(M_{\sigma }\). So, let \(l_{t'} \in C_{j}\) such that \(\sigma (l_{t'})\) = false. By the construction of \(M_{\sigma }\), we know that \(\overline{l}_{t'}y_{t'},b_{t'}c_{t'}\in M_{\sigma }\). The edges of the form \(\{s_{j,k}y_{t'} \mid k \in [p\alpha ]\}\) cannot be added to \(M_{\sigma }\) as \(y_{t'}\) is already saturated by \(M_{\sigma }\). Next, as the vertex set \(\{y_{t'},b_{t'},\overline{l}_{t'}\}\) is saturated by \(M_{\sigma }\), the edges of the form \(\{r_{j,k}l_{t'} \mid k \in [p\alpha ]\}\) cannot be added to \(M_{\sigma }\) as otherwise, a cycle of the form \(l_{t'},y_{t'},\overline{l}_{t'},b_{t'},l_{t'}\) will be created in \(G[V(M_{\sigma })]\). Thus, the edges connecting the clause gadget corresponding to \(C_j\) and other literals in \(C_j\) cannot be added to \(M_{\sigma }\).

Next, since \(b_{i}c_{i} \in M_{\sigma }\), none of the edges from the set \(\{a_{i,k}d_{i,k}, b_{i} a_{i,k}, c_{i}d_{i,k} \mid k \in [p\alpha ]\}\) can be added to \(M_{\sigma }\). Moreover, since \(M_{\sigma }\) is a matching and the vertices \(b_{i}, y_{i}\) and \(x_{i}\) (or \(\overline{x}_{i}\)) are saturated by \(M_{\sigma }\), none of the edges of the form \(\{b_{i}x_{i},b_{i}\overline{x}_{i}, y_{i}v_{i},y_{i}\overline{x}_{i},x_{i}u_{i}\}\) (or \(\{b_{i}x_{i},b_{i}\overline{x}_{i}, y_{i}v_{i},y_{i}\overline{x}_{i}, \overline{x}_{i}w_{i}\}\)) can be added to \(M_{\sigma }\). Furthermore, the edge \(\overline{x}_{i}w_{i}\) (or \(x_{i}u_{i}\)) cannot be added to \(M_{\sigma }\), otherwise, a cycle \(x_{i},y_{i},\overline{x}_{i},b_{i},x_{i}\) will be created. Next, it can be observed that the subgraph \(G[V({M_{\sigma }})]\) is a disjoint union of paths on four vertices, which implies that \(M_{\sigma }\) is an acyclic matching in \(G_{\psi , \alpha }\). Based on the above observations, it follows that \(M_{\sigma }\) is maximal as well as acyclic with cardinality exactly 2p. This completes the proof of Claim 12. \(\square \)

Claim 13

If \(\psi \) is not satisfiable, then \(\mu '_{ac}(G_{\psi ,\alpha })\ge p\alpha +1.\)

Proof

Let us assume that \(\psi \) is not satisfiable. Now, the aim is to prove that there does not exist any maximal acyclic matching M in \(G_{\psi ,\alpha }\) that has cardinality at least \(p\alpha + 1.\) Further, to arrive at a contradiction, let us assume that \(\mu '_{ac}(G_{\psi ,\alpha }) \le p\alpha \) and let M be a minimum maximal acyclic matching in \(G_{\psi ,\alpha }\). Suppose M contains an edge \(r_{j,k}s_{j,k}\) from a clause gadget for the clause \(C_j\). Here \(k \in [p\alpha ]\). If M does not contain an edge of the form \(l_t r_{j,k'}\) or \(y_t s_{j,k'}\) (where \(l_t\) is a literal in \(C_i\)) then by maximality of M it follows that M must contain the set \(A=\{r_{j,k}s_{j,k}\mid k \in [p\alpha ]\}\). In other cases, M may contain at most 3 edges of the form \(l_t r_{j,k'}\) (or \(y_t s_{j,k'}\)) where \(l_t\) is a literal and \(k'\) is an index other than k. Again, by the maximality of M, it can be proved that M contains \(p\alpha \) edges incident on the vertices of the clause gadget \(C_j\). Since \(M\cup \{b_{i}c_{i}\}\) for some \(i\in [p]\) is also an acyclic matching in \(G_{\psi ,\alpha }\), it contradicts the assumption that M is maximal in \(G_{\psi ,\alpha }\). Thus M does not contain any edge of the form \(r_{j,k}s_{j,k}\), for any \( j \in [m]\) and \( k \in [p\alpha ]\). Now, for M to be maximal, every clause \(C_j\) in \(\psi \) contains a literal \(l_t\) such that both the vertices \(l_t\) and \(y_t\) are saturated by M. By similar arguments, it can be observed that M does not contain any edge of the form \(a_{i,k}d_{i,k}\) for any \(k \in [p\alpha ]\) and \(i\in [p]\). Since M is a maximal acyclic matching and it must not contain an edge of the form \(a_{i,k}d_{i,k}\) (for any \(i \in [p]\) and any \(k \in [p\alpha ]\)), the vertices \(b_{i}\) and \(c_{i}\) should be saturated by M, for all \(i \in [p]\). Now, since vertex \(b_{i}\) is saturated by M (for every \(i\in [p]\)), so at most two vertices from the set \(\{x_{i},y_{i}, \overline{x}_{i}\}\) can be saturated by M. Next, for each \(i \in [p]\), we claim that exactly one of \(x_{i}\) and \(\overline{x}_{i}\) is saturated by M. It is so because if both of them (\(x_{i}\) and \(\overline{x}_{i}\)) are saturated by M, then \(y_{i}\) must be unsaturated and in that case, \(r_{j,k}s_{j,k}\) can be added to M for some clause \(C_{j}\) containing the literal \(l_{i} \in \{x_i, \overline{x}_i\}\), which will lead to a contradiction to what we have proved earlier (M does not contain any edge of the form \(r_{j,k}s_{j,k}\), for any \( j \in [m]\) and \( k \in [p\alpha ]\)).

Next, assume that both \(x_{i}\) and \(\overline{x}_i\) are not saturated by M. This implies that the edges of the form \(\{x_{i}r_{j,k}, \overline{x}_{i}r_{j,k}\} \) for \(k\in [p\alpha ]\) do not belong to M. Also, \(b_{i}\) is saturated by M for each \(i\in [p]\). Now, it implies that \(M\cup \{ x_{i}u_{i}\}\) (or \(M\cup \{\overline{x}_{i}w_{i}\}\)) is also an acyclic matching, which contradicts the maximality of M in G. Thus, either \(x_{i}\) or \(\overline{x}_{i}\) is saturated by M. Now, we construct a truth assignment \(\sigma _M\) by setting \(\sigma _M(x_{i})\) = true, if \(x_{i}\) is saturated by M, and \(\sigma _M(x_{i})\) = false otherwise. Each clause in \(\psi \) is satisfied by \(\sigma _M\) because if all the literals in a clause \(C_j\) evaluate to false under \(\sigma _M\), then the maximality of M would imply that edges of the form \(r_{j,k} s_{j,k}\) are in M, and it leads to the inequality \(|M| > p\alpha \). Since \(|M| \le p\alpha \), \(\sigma _M\) satisfies \(\psi \). This contradicts our assumption that \(\psi \) is unsatisfiable. Hence, \(\mu '_{ac}(G_{\psi , \alpha }) > \alpha p\). \(\square \)

Lemma 1 is a consequence of Claim 12and 13. \(\square \)

Theorem 7

Given a graph G, it is hard to approximate Low-Acy-Matching within a factor of \(n^{1-\epsilon }\) for any constant \(\epsilon >0\) unless \({\textsf{P}}={\textsf{NP}}\) even when G is a bipartite graph. Here, \(n=|V(G)|\).

Proof

First, note that if Low-Acy-Matching cannot be approximated within a factor of \(n^{1-\epsilon }\) for some constant \(\epsilon >0\), then it cannot be approximated within a factor of \(n^{1-\epsilon '}\), where \(\epsilon '>\epsilon \). So, we assume that \(0<\epsilon <1\). Further, for a given constant \(\epsilon > 0\), we define \(k \ge \big \lceil \frac{3}{\epsilon }\big \rceil \). Consider an instance \(\psi \) of the 3-SAT problem, with p variables and m clauses. Construct the bipartite graph \(G_{\psi ,\alpha }\) as outlined in the proof of Lemma 1, utilizing the instance \(\psi \) and setting \(\alpha \) to be equal to \(2p^{k-2}\). It is easy to see that graph \(G_{\psi , \alpha }\) has \(n=8p+4p^{k-1}(p+m)\) vertices. Furthermore, it is apparent that \(n \ge p^{k} \). Also, we assume that \(p \ge m\) (this assumption does not alter the \({\textsf{NP}}\)-completeness of 3-SAT (Garey and Johnson 1979)).

Next, we claim that it is unlikely that there exists a polynomial-time algorithm that approximates Low-Acy-Matching within a factor of \(p^{k - 2}\) for the class of graphs \(G_{\psi ,\alpha }\). Assuming a contradiction, let us assume the existence of an algorithm ALG capable of approximating Low-Acy-Matching within a factor of \(p^{k - 2}\). Consequently, let \(M_{ALG}\) represent a maximal acyclic matching in \(G_{\psi ,\alpha }\) computed by ALG. Now, based on Lemma 1, if \(\psi \) is satisfiable, then \(|M_{ALG}|\le p^{k-2}\cdot \mu '_{ac}(G_{\psi ,\alpha }) \le 2p^{k-1}\). On the other hand, if \(\psi \) is not satisfiable, then \(|M_{ALG}|>\alpha p>2p^{k-1}\). Given that ALG runs within polynomial time and that the construction of \(G_{\psi ,\alpha }\) from \(\psi \) also takes polynomial time, by comparing the size of the matching found by ALG with \(2p^{k-1}\), we can determine the satisfiability of \(\sigma \) in polynomial time. This would imply that \({\textsf{P}}= {\textsf{NP}}\).

Now, we estimate \(p^{k-2}\) in terms of \(|V(G_{\psi ,\alpha })|\). Since \(n = 8p + 4p^{k-1}(p+m)\), we have \(p^{k-2} = \frac{n-8p}{4p(p+m)}\). As we have assumed that \(p \ge m\), it holds that \(p^{k-2} \ge \frac{n-8p}{8p^2}\). Next, we assume that \(p \ge 8\). Since \(p^{k-2} \ge \frac{n-8p}{8p^2} = \frac{n}{8p^2}- \frac{1}{p} \ge \frac{n^{1 - 2/k}}{8} - \frac{1}{8}\), for sufficiently large values of n (\(n\ge 9^{k}\)), we have \(\frac{n^{1--2/k}}{8} - \frac{1}{8}\ge n^{1--3/k}\). Therefore, \( p^{k-2} \ge n^{1-3/k} \ge n^{1 - \epsilon }\). Thus, as \(p^{k-2} \ge n^{1-\epsilon }\), it is \({\textsf{NP}}\)-hard to approximate Low-Acy-Matching within a factor of \(n^{1-\epsilon }\), for any constant \(\epsilon > 0\). \(\square \)

In this section, we establish the \(\textsf{APX}\)-hardness of the Low-Acy-Matching problem when restricted to 4-regular graphs. Our approach involves creating an \(\textsf{L}\)-reduction from an instance of the Min-IND problem for 3-regular graphs. Given a graph G, in Min-IND, the aim is to find a vertex set S of minimum cardinality such that S is an independent dominating set of G. It is known that Min-IND is \(\textsf{APX}\)-complete for 3-regular graphs (Kann 1992). Furthermore, it is essential to acknowledge that an independent dominating set is essentially a maximal independent set, and vice versa.

Theorem 8

Low-Acy-Matching is \(\textsf{APX}\)-hard for 4-regular graphs.

Proof

Given a 3-regular graph G with \(V(G)=\{v_{1},\ldots ,\) \(v_{n}\}\), an instance of Min-IND, we construct a 4-regular graph \(G'\), an instance of Low-Acy-Matching as follows: For every vertex \(v_{i}\in V(G)\), we create two duplicate vertices in \(V(G')\), denoted as \(v^{1}_{i}\) and \(v^{2}_{i}\), and connect them with an edge represented as \(v^1_iv^2_i\). For each edge \(v_{i}v_{j}\in E(G)\), we connect the vertices \(v^1_i\) and \(v^1_j\) using the gadget \(H^1_{ij}\), which consists of 8 vertices, namely, \(\{v_{i}^{1},e_{ij}^{1},a_{ij}^{1},c_{ij}^{1},b_{ij}^{1},d_{ij}^{1},f_{ij}^{1},v_{j}^{1}\}\) and 13 edges, namely, \(\{v_{i}^{1}e_{ij}^{1},e_{ij}^{1}f_{ij}^{1},f_{ij}^{1}v_{j}^{1},e_{ij}^{1}a_{ij}^{1},\) \(e_{ij}^{1}c_{ij}^{1}, a_{ij}^{1}c_{ij}^{1}, a_{ij}^{1}b_{ij}^{1},c_{ij}^{1}d_{ij}^{1}, b_{ij}^{1}d_{ij}^{1}, a_{ij}^{1}d_{ij}^{1}, b_{ij}^{1}c_{ij}^{1},b_{ij}^{1}f_{ij}^{1},d_{ij}^{1}f_{ij}^{1} \}\), and connect the vertices \(v^2_i\) and \(v^2_j\) using the gadget \(H^2_{ij}\) (note that the gadget \(H^2_{ij}\) is the same as \(H^1_{ij}\), only the superscript is different). Figure 4a and b illustrates the gadget \(H_{ij}^{1}\) and the subgraph \(H_{ij}\) of \(G'\) corresponding to the edge \(v_iv_j\) in G, respectively. This marks the completion of the construction for graph \(G'\)

Based on the construction above, it can be inferred that \(G'\) is a 4-regular graph, given that G is a 3-regular graph. Also, it is worth noting that constructing \(G'\) from G can be done in polynomial time as \(|V(G')|=20|V(G)|\) and \(|E(G')|=40|V(G)|\). Let \(m = |E(G)|\) and \(n=|V(G)|\), throughout this section. Also, let \(t\in \{1,2\}\).

a Gadget \(H_{ij}^{1}\). b Subgraph \(H_{ij}\) of \(G'\) corresponding to edge \(v_{i}v_{j}\) in G

Full size image

Now, consider the following claim.

Claim 14

If G has an independent dominating set of cardinality k, then \(G'\) has a maximal acyclic matching of cardinality \(2m + k\).

Proof

Consider \(D=\{v_{1},\ldots ,v_{k}\}\) as an independent dominating set of G. Given the vertex set D, we define \(M_{D}= \{e_{ij}^{1}f_{ij}^{1},e_{ij}^{2}f_{ij}^{2}\mid v_{i}v_{j}\in E(G)\} \cup \{v^{1}_{i}v^{2}_{i}\mid v_{i}\in D\}\). Clearly, \(|M_{D}|=k+2\,m\) and \(M_D\) qualifies as a matching in \(G'\) because no two edges within \(M_D\) have a shared vertex. Furthermore, \(M_D\) qualifies as an acyclic matching in \(G'\) due to the following reasons: (i) D includes at most one endpoint of every edge present in G and (ii) from each edge gadget \(H_{ij}\), \(M_D\) contains at most 3 edges with endpoints that do not form any induced cycles.

Now, we claim that \(M_D\) represents a maximal acyclic matching in \(G'\). First, let e be an edge from \(H^1_{ij}\) (or \(H^2_{ij}\)), which is not in \(M_D\). Then, note that the endpoints of the edges in \(\{e\} \cup M_D\) either induce a cycle, or \(\{e\} \cup M_D\) is not a matching in \(G'\). Next, let \(e = v^1_iv^2_i\) for some vertex \(v_i \notin D\). Since D is an independent dominating set of G, there must exist some \(v_{j}\in D\) such that \(v_{i}v_j\in E(G)\). Since \(v^1_jv^2_j\in M_{D}\), \(M_D \cup \{e\}\) induces a cycle of the form \(v_{i}^{1},e_{ij}^{1},f_{ij}^{1},v_{j}^{1},v_{j}^{2},f_{ij}^{2},e_{ij}^{2},v_{i}^{2},v_{i}^{1}\). Thus, \(M_{D}\cup \{e\}\) is not an acyclic matching. Thus, \(M_{D}\) is a maximal acyclic matching in \(G'\). \(\square \)

Now, let us introduce the following notations that will be utilized in the course of proving Theorem 8.

An edge gadget \(H_{ij}\) is said to be in proper order in relation to an acyclic matching M in \(G'\) under any of the following conditions: i) \(M\cap E(H_{ij})=\{e_{ij}^{1}f_{ij}^{1},e_{ij}^{2}f_{ij}^{2}\}\), ii) \(M\cap E(H_{ij})=\{e_{ij}^{1}f_{ij}^{1},e_{ij}^{2}f_{ij}^{2},v_{i}^{1}v_{i}^{2}\}\), or iii) \(M\cap E(H_{ij})=\{e_{ij}^{1}f_{ij}^{1},e_{ij}^{2}f_{ij}^{2},v_{j}^{1}v_{j}^{2}\}\). Furthermore, for some acyclic matching M in \(G'\) and for each \(e \in E(G)\), we define \(r(e,M)=|E(H_{e}) \cap M|\). Note that if M is a maximal acyclic matching in \(G'\), then \(r(e,M)\ge 2\). With these terminologies in mind, we say that an acyclic matching M is in proper order when all the edge gadgets in \(G'\) are in proper order with respect to M. It is worth noting that the matching \(M_D\), which was constructed in the proof of Claim 14, is indeed in proper order. Now, we proceed to establish Claim 15.

Claim 15

In graph \(G'\), there exists a minimum cardinality maximal acyclic matching that is in a proper order.

Proof

Let M be a minimum maximal acyclic matching in \(G'\), which is not in proper order. Now, we construct (in polynomial time) a maximal acyclic matching \(\overline{M}\) in \(G'\), which is in proper order, and \(|\overline{M}| = |M|\).

Let S be the set of edges in G such that the corresponding edge gadget in \(G'\) is not in proper order with respect to the matching M. Let \(S' = \{ e \in S \mid r(e, M) \ge 3\}\) and \(T = S {\setminus } S'\).

Next, we observe that the degree of a vertex in (V(T), T) is either 1 or 2. Let \(e =v_iv_j\) be an edge in T. Since \(r(e, M) = 2\) (by the definition of T) and \(v_{i}^1v_{i}^2, v_{j}^1v_{j}^2\) are not in M (else, \(r(e,M)\ne 2\)), at least one vertex from \(\{v_{i}^1, v_{i}^2\}\) and at least one vertex from \(\{ v_{j}^1,v_{j}^2\}\) must be saturated by M through an edge outside \(H_{e}\) (else, M will not be maximal). Also, these edges are from the edge gadgets corresponding to the edges adjacent to e in G. Next, note that if \(e'=v_xv_y\) and M contains an edge from the set \(\{v_x^1e_{xy}^{1}\), \(v_x^2e_{xy}^{2},v_y^1f_{xy}^{1}, v_y^1f_{xy}^{1}\}\), then \(r(e', M) \ge 3\), which further implies that \(e'\in S'\). Thus, it can be proved that at least one edge adjacent to e with common vertex \(v_i\) as well as \(v_j\) is not in T. Furthermore, it implies that every edge in T is adjacent to an edge in \(S'\).

From M, we construct an acyclic matching \(M'\) as follows. For each edge \(e(=v_{i}v_{j}) \in S\), we remove the edge set \(M \cap E(H_e)\) from M and add the edge set \(\{e^1_{ij}f^1_{ij}, e^2_{ij}f^2_{ij}\}\) to M. It is easy to observe that \(M'\) is an acyclic matching in \(G'\). Moreover, \(M'\) is in proper order, and \(|M'| \le |M|\). However, \(M'\) need not be a maximal acyclic matching in \(G'\). Let \(X = \{v_i \in V(G) \mid v^1_{i}v^2_{i} \in M'\}\). It is easy to observe that if X is an independent dominating set of G, then \(M'\) is a maximal acyclic matching \(G'\). In case it is not, then we extend X to \(\overline{X}\) so that \(\overline{X}\) is an independent dominating set of G. Now, we define \(\overline{M} = M' \cup \{v^1_{i}v^2_{i} \mid v_i \in (\overline{X} {\setminus } X)\}\). From the proof of Claim 14, it follows that \(\overline{M}\) is a maximal acyclic matching in \(G'\).

Next, we prove that \(|\overline{M}| \le |M|\). For every edge \(e \in S'\), \(r(e, M) - r(e, M') \ge 1\). This implies that \(|M| \ge |M'| + |S'|\). Since \(|\overline{M}| = |M'| + |\overline{X} {\setminus } X|\), it is enough to show that \(|S'| \ge |\overline{X} \setminus X|\). For this, we consider the graph (V[S], S) and prove that every vertex in \((\overline{X} \setminus X)\) is incident with at least one edge from the edge set \(S'\). Recall that every edge in T is adjacent to an edge in \(S'\). Therefore, for every vertex \(v \in (\overline{X} {\setminus } X)\), there exists an edge \(e' \in S'\), which is incident on v. This implies that \(|S'| \ge |\overline{X} {\setminus } X|\) (as, in a graph \(H=(V(H),E(H))\) without isolated vertices, \(|E(H)|\ge |D|\), for any independent dominating set D of H).

From these observations, it follows that if a maximal acyclic matching M in \(G'\) is not in proper order, then, in polynomial time, we can construct a maximal acyclic matching \(\overline{M}\) in \(G'\) such that it is in proper order and \(|\overline{M}| \le |M|\). This proves the claim. \(\square \)

Given the existence of a minimum maximal acyclic matching in \(G'\), which also adheres to the proper order condition (as indicated by Claim 15), we can make the assumption, without loss of generality, that all maximal acyclic matchings in \(G'\) are in the proper order. As a consequence, the subsequent conclusion can be drawn.

Claim 16

Let M be a maximal acyclic matching in \(G'\). Furthermore, let \(D =\{v_i \mid v^1_{i}v^2_{i} \in M\}\). Then, \(|M| = 2\,m + |D|\) and D is an independent dominating set of G.

One can notice that \(2m=3n\) due to the fact that G is a 3-regular graph. Also, by Claim 14 and Claim 16, we can deduce the following.

Claim 17

If \(D^*\) is a minimum cardinality independent dominating set of G and \(M^*\) is a minimum cardinality maximal acyclic matching in \(G'\), then \(|M^*|=3n+|D^*|\).

It has been established in Goddard and Henning (2013) that for any independent dominating set D within a 3-regular graph G, the following holds: \(\frac{n}{4}\le |D|\le \frac{n}{2}\). Consequently, we can deduce that \(|M^{*}|=3n+|D^{*}|\le 12 |D^{*}|+|D^{*}|=13|D^{*}|\).

Moreover, according to Claim 14 and Claim 16, starting from any maximal acyclic matching \(M'\) in \(G'\), it is possible to derive an independent dominating set D for the graph G such that \(|D|\le |M'|-3n\). Therefore, we have \(|M'|-|M^{*}|=(|M'|-3n)-(|M^{*}|-3n)\ge |D|-|D^{*}|\) (as per Claim 17). These two inequalities, namely \(|M^{*}|\le 13|D^{*}|\) and \(|M'|-|M^{*}|\ge |D|-|D^{*}|\), suggest that this is an \(\textsf{L}\)-reduction where \(\beta =1\) and \(\alpha =13\). \(\square \)

In this paper, we showed the difference between the hardness complexity of Low-Acy-Matching and Max-Acy-Matching. Furthermore, we established that the Decide-Low-Acy-Matching problem is NP-complete for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs. We also proved that it is impossible to approximate the Low-Acy-Matching problem within a ratio of \(n^{1-\epsilon }\) for any \(\epsilon >0\) unless \({\textsf{P}}={\textsf{NP}}\), even when dealing with bipartite graphs. Additionally, we established the \(\textsf{APX}\)-hardness of the Low-Acy-Matching problem in the context of 4-regular graphs.

It would be of particular interest to explore the computational complexity of Low-Acy-Matching within graph classes such as chordal bipartite graphs and chordal graphs. Notably, there is a lack of lower bounds for the minimum cardinality of maximal acyclic matchings, even in the case of r-regular graphs, where \(r\ge 3\) is a fixed positive integer. In contrast, the literature contains established bounds for related parameters, such as the minimum cardinality of maximal induced (uniquely restricted) matchings, as mentioned in references (Chaudhary and Panda 2021; Orlovich et al. 2008). Furthermore, exploring the parameterized complexity of finding minimum maximal acyclic matchings holds great potential as a future research direction.