key: cord-0044022-nvpljvo1
authors: Panda, B. S.; Chaudhary, Juhi
title: Acyclic Matching in Some Subclasses of Graphs
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_31
sha: a29706d7b53db8650b4c81d5093e82e8f0c9f9ed
doc_id: 44022
cord_uid: nvpljvo1

A subset [Formula: see text] of edges of a graph [Formula: see text] is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called an acyclic matching if G[V(M)], the subgraph of G induced by the M-saturated vertices of G is acyclic. The Acyclic Matching Problem is the problem of finding an acyclic matching of maximum size. The decision version of the Acyclic Matching Problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the decision version of the Acyclic Matching Problem remains NP-complete for comb-convex bipartite graphs and dually-chordal graphs. On the positive side, we present linear time algorithms to compute an acyclic matching of maximum size in split graphs and proper interval graphs. Finally, we show that the Acyclic Matching Problem is hard to approximate within a factor of [Formula: see text] for any [Formula: see text], unless [Formula: see text] and the Acyclic Matching Problem is APX-complete for [Formula: see text]-regular graphs for [Formula: see text], where k is a constant.

A subset M ⊆ E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. Vertices that are incident on the edges of a matching M are called M -saturated vertices and are denoted by V (M ). In this paper, we study an important variant of matching called acyclic matching (see [3, 5, 9] ). A matching M in G is called an acyclic matching if G[V (M )], the subgraph of G induced by the M -saturated vertices of G is acyclic. The Acyclic Matching Problem asks to find an acyclic matching of maximum size in a given graph G. The acyclic matching number of G, denoted by μ ac (G) is the maximum size of an acyclic matching in G.

More formally, the Acyclic Matching Problem and its decision version are defined as follows: Goddard et al. [5] introduced the concept of acyclic matching along with some other variants of the matching and proved that the Acyclic Matching Decide Problem is NP-complete for general graphs. Later, Panda and Pradhan [9] strengthened this result by showing that the Acyclic Matching Decide Problem remains NP-complete for bipartite graphs and even for perfect-elimination bipartite graphs, which is a subclass of bipartite graphs. They also gave a dynamic programming based algorithm to find an acyclic matching of maximum size in bipartite permutation graphs. Baste et al. [2] showed that finding a maximum size 1-degenerate matching in a graph G is equivalent to finding a maximum acyclic matching in G. They further proved that a maximum 1-degenerate matching could be found in polynomial time in chordal graphs, but the time complexity is very high. Recently, Fürst and Rautenbach showed that it is hard to decide whether a given bipartite graph of maximum degree at most four has a maximum matching that is acyclic [4] . They further characterized the graphs for which every maximum matching is acyclic and give linear time algorithms to compute a maximum acyclic matching in graph classes like P 4 -free graphs and 2P 3 -free graphs [4] . There are no approximation results known for the Acyclic Matching Problem till now.

In this paper, we study the complexity status of the Acyclic Matching Problem and the Acyclic Matching Decide Problem in some subclasses of graphs. The main contributions of this paper are summarized below.

1. We prove that the Acyclic Matching Decide Problem is NP-complete for tree-convex bipartite graphs by showing that it is NP-complete for combconvex bipartite graphs which is a subclass of tree-convex bipartite graphs. 2. We prove that the Acyclic Matching Decide Problem is NP-complete for dually chordal graphs. 3. We prove that a maximum size acyclic matching can be computed in linear time in split graphs and proper interval graphs. 4. We prove that it is hard to approximate the Acyclic Matching Problem within a factor of n 1− for any > 0, unless P = NP . 5. We prove that the Acyclic Matching Problem is APX-complete for 2k + 1-regular graphs for k ≥ 3, where k is a constant.

We consider only simple and connected graphs. For a graph G = (V, E), let n denotes the number of vertices and m denotes the number of edges in G. The open and closed neighborhood of a vertex u ∈ V are denoted by N (u) and

is called a bipartite graph if its vertex set V can be partitioned into two independent sets X and Y , such that every edge of G joins a vertex in X to a vertex in Y . A comb is a graph obtained by attaching a pendant vertex (tooth) to every vertex of a path (backbone). A bipartite graph G = (X, Y, E) is said to be a tree-convex bipartite graph, if a tree T = (X, E X ) can be defined on X such that for every vertex y ∈ Y , the vertices in N G (y) induces a subtree of T . It can be noted that tree-convex bipartite graphs are recognizable in linear time and the associated tree T can also be constructed in linear time [11] . If the tree T in a tree-convex bipartite graph is a comb, then G is called a comb-convex bipartite graph.

A graph G = (V, E) is called a chordal graph if every cycle in G of length at least four has a chord, that is, an edge joining two non-consecutive vertices of the cycle. A graph G = (V, E) is called a split graph if its vertex set V can be partitioned into two sets I and C such that I is an independent set and C is a clique. Let F be a family of sets. The intersection graph of F is obtained by taking each set in F as a vertex and joining two sets in F if and only if they have a nonempty intersection. A graph G is called a proper interval graph if it is the intersection graph of a family F of intervals on the real line such that no intervals in F contains another.

is called a dually chordal graph if it has a maximum neighborhood ordering.

It has been shown in [9] that the Acyclic Matching Decide Problem is NPcomplete for bipartite graphs. In this subsection, we strengthen this result by showing that the Acyclic Matching Decide Problem remains NP-complete for tree-convex bipartite graphs, which is a subclass of bipartite graphs by showing that it is NP-complete for comb-convex bipartite graphs. Proof. Clearly, the Acyclic Matching Decide Problem belongs to the class NP for comb-convex bipartite graphs. To show the NP-completeness, we give a polynomial reduction from the Acyclic Matching Decide Problem for bipartite graphs, which is already known to be NP-complete [9] .

Given a bipartite graph G = (X, Y, E), we construct a comb-convex bipartite graph H = (X H , Y H , E H ) as follows:

Let

The constructed graph H is a combconvex bipartite graph if X is taken as the backbone and X is taken as the teeth of a comb C. Further, note that given a bipartite graph G, the graph H can be constructed in polynomial time. Now, the following claim is sufficient to complete the proof of the theorem.

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

forms a cycle, which is a contradiction. Thus, M can include at most one edge from E .

Next, let x i y i ∈ M for some x i ∈ X . Since G is connected, y i will have a neighbor (say x k ) in X. Note that x k must be unsaturated by M because otherwise if x k y k ∈ M for some y k ∈ Y , then G[{x k , y k , x i , y i }] will form a cycle, which is a contradiction to the fact that M is acyclic.

Otherwise, let us assume that G[V (M )] contains a cycle C . If C does not contain the vertex x k , then C is also a cycle in G[V (M )]. This contradicts the fact that M is an acyclic matching. So, C contains the vertex

, which is a contradiction. Hence, M is acyclic and it is a required acyclic matching in G of size at least k. ♦ Hence, the Acyclic Matching Decide Problem is NP-complete for comb-convex bipartite graphs. Corollary 1. The Acyclic Matching Decide Problem is NP-complete for tree-convex bipartite graphs.

The Acyclic Matching Problem is polynomial time solvable for chordal graphs [2] and hence for strongly chordal graphs. In this subsection, we show that the Acyclic Matching Decide Problem is NP-complete for dually chordal graphs which is a superclass of strongly chordal graphs.

Proof. Clearly, the Acyclic Matching Decide Problem belongs to the class NP for dually chordal graphs. To show the NP-completeness, we give a polynomial reduction from the Acyclic Matching Decide Problem for general graphs, which is already known to be NP-complete [5] .

Given a graph G = (V, E), we construct a dually chordal graph H = (V H , E H ) as follows:

Therefore, it is easy to see that the constructed graph H = (V H , E H ) is a dually chordal graph. Also, note that given a graph G, the graph H can be constructed in polynomial time. Now, the following claim is sufficient to complete the proof of the theorem.

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

Proof. Necessity: Let M be an acyclic matching in G of size at least k. Since G is a vertex induced subgraph of H, so M is an acyclic matching in graph H of size at least k. Sufficiency: Let M be an acyclic matching in graph H of size at least k,

forms a cycle, which is a contradiction.

As |M | ≥ k > 1, vertex v 0 is not saturated by M , that is, M does not have any edge of the form v 0 v i for any v i ∈ V . Thus, M is a required acyclic matching in graph G of size at least k. ♦ Hence, the Acyclic Matching Decide Problem is NP-complete for dually chordal graphs.

In this subsection, we show that an acyclic matching of maximum size can be computed in linear time for split graphs which is a subclass of chordal graphs, where the complexity of computing a maximum size acyclic matching is O(n 7 ).

Let G = (V, E) be a split graph. Throughout this section, I ∪ C represents a given partition of the vertex set V , where I is an independent set and C is a clique in G. Now, the following lemma shows that the cardinality of an acyclic matching in a split graph G = (V, E) can be either 1 or 2 only.

Proof. Let M be an acyclic matching in G and let |M | ≥ 3. Let

Since I is an independent set, we can assume without loss of generality that b 1 , b 2 , b 3 ∈ C. This leads to a contradiction as

Next, we will characterize the split graphs depending on the size of an acyclic matching in G. For this purpose, let us recall the definition of threshold graphs, which is a proper subclass of split graphs.

A split graph G = (V, E) is called a threshold graph if the vertices in I can be linearly ordered,

This linear ordering of a threshold graph can be computed in linear time [6] . 

Proof. Necessity: Let M be an acyclic matching in G and let

Since C is a clique and I is an independent set, exactly two vertices from the set {a i , a j , b i , b j } belong to C and the other two belongs to I. Without loss of generality, let us assume that a i , a j ∈ C and

Sufficiency: Let us assume that there exist two vertices v 1 , v 2 ∈ I such that Proof. Necessity: Let G = (V, E) be a split graph and let M be a maximum acyclic matching in G such that |M | = 1. For the sake of contradiction, let us suppose that G is not a threshold graph. Then, there will exist a pair of vertices

is a path graph. Since |M | = 2, this leads to a contradiction to the fact that M is a maximum acyclic matching in G. Hence, G is a threshold graph.

Sufficiency: Let G = (V, E) be a threshold graph and let (v 1 , v 2 , . . . v |I| ) be an ordering of I, such that

Hence, by Lemma 1 and Lemma 2, it is easy to see that |M | = 1.

Based on the above discussions we have the following theorem. Proof. Due to space restriction, the proof has been deferred to the longer version of the paper.

In this subsection, we show that an acyclic matching of maximum size can be computed in linear time for proper interval graphs which is a subclass of chordal graphs, where the complexity of computing a maximum size acyclic matching is O(n 7 ).

Let v n−1 , . . . , v 1 ) i.e., the reverse of α, is also a PEO of G. It has been characterized in [7] that a graph is proper interval if and only if it has a BCO. Proof. The result easily follows from Observation 5. ♦

σ = (v 1 , v 2 , . . . , v n ) be a BCO of a proper interval graph G. If v i v j ∈ E, then v k v j ∈ E for all k, i ≤ k ≤ j − 1. Observation 6. Let σ = (v 1 , v 2 , . . . , v n ) be a BCO of

v i in σ. If v i < v j in σ, then L[v i ] ≤ L[v j ].

v i and v j such that v i < v j in σ and L[v i ] > L[v j ]. Then by Observation 5, v j L[v i ] ∈ E but since L[v j ] < L[v i ],

and let M be an acyclic matching in G. If the edges u 1 w 1 , u 2 w 2 ∈ M such that u 1 < w 1 and u 2 < w 2 in σ, then either w 1 < u 2 or w 2 < u 1 .

Proof. Let us assume without loss of generality that there exist two edges e 1 = u 1 w 1 and e 2 = u 2 w 2 such that u 1 < w 2 < w 1 in σ. Now, the G[{u 1 , w 2 , w 1 }] forms a cycle, which is a contradiction. Thus, either w 1 < u 2 or w 2 < u 1 . Proof. Let G be a proper interval graph with a BCO σ = (v 1 , v 2 , . . . , v n ) and let M be a maximum acyclic matching in G. Let v a v b be the first edge with respect to σ that belongs to M . Let us assume without loss of generality that

is acyclic and hence the edge v 1 v 2 can be added to M . This leads to a contradiction to the fact that M is a maximum acyclic matching in G. = (v a , v b , . . . , v k ) be an ordering obtained from σ by removing some vertices from σ. Then, σ is also a BCO of some proper interval graph G , where G is a subgraph of G. Hence, we have the following corollary to Lemma 4. σ = (v a , v b , . . . , v k ) is a BCO of a subgraph G of a Proof. Due to space restriction, the proof has been deferred to the longer version of the paper.

else if (L[F [Gi]] + 1 = v k ) < L[F [Gi] + 1]) and L[v k ] = L[F [Gi] + 1] then i = i + 1; Gi = Gi−1 \ {F [Gi−1], . . . , L[F [Gi−1]]}; while (L[v k ] = L[F [Gi] + 1]) do temp = v k ; v k = v k + 1; Gi = Gi \ temp; Gi = Gi \ {v k+1 ,

Let G = (V, E) be a graph with n vertices. It is easy to note that the maximum size of an acyclic matching in G can be at most n 2 . So, the Acyclic Matching Problem can be approximated within a factor of n in polynomial time. In this section, we show that for any > 0, it is hard to approximate the Acyclic Matching Problem within a factor of n 1− , unless P = NP .

To prove the result, we will need the following theorem for the Maximum Independent Set Problem. Theorem 9. [12] The Maximum Independent Set Problem for a graph G cannot be approximated within a factor of n 1− for any > 0, unless P = NP . Now, consider the following construction: 

Clearly, H can be constructed in polynomial time as |V H | = 2|V | and |E H | = 4|E| + |V |.

Also, note that the edges in H can be one of the following four types:

Now, we will discuss some lemmas that will be used in the proof of the main theorem of this section. Let us recall that V H (M ) denotes the set of M -saturated vertices of graph H. 

, which is a contradiction. Hence, M is acyclic. In this way, an acyclic matching of same size can be obtained by replacing an edge of T ype-IV with a corresponding T ype-III edge.

Using the similar arguments, we can show that an acyclic matching of same size can be obtained by replacing an edge of T ype-III with a corresponding T ype-II edge. Proof. Due to space restriction, the proof has been deferred to the longer version of the paper. ♦

The following lemma shows that the described reduction is exactly what we need. Hence, we obtain, |I * (G)| ≤ α|I ALG (G)| = n 1− |I ALG (G)| = (2n) 1− |I ALG (G)| = (2) 1− (n) 1− |I ALG (G)|.

If we choose , such that 2 1− < n − , then

Hence, |I * (G)| < (n) 1− |I ALG (G)|, which leads to a contradiction to Theorem 9. Therefore, the Acyclic Matching Problem cannot be approximated within a factor of n 1− for any > 0, unless P = NP .

In this section, we show that the Acyclic Matching Problem is APXcomplete for 2k + 1-regular graphs for k ≥ 3, where k is a constant.

To prove the result, we first show that the Acyclic Matching Problem is approximable within a constant factor when restricted to k-regular graphs for k ≥ 3, where k is a constant. For the purpose, consider the following algorithm: Proof. Given a k-regular graph G, construct an acyclic matching M ac of G by using algorithm Approx-AM(G). In each step, after adding an edge in the matching M ac , we are removing at most k 2 edges, hence kn 2[2k(k−1)+1] ≤ |M ac |. Moreover, it is easy to see that the size of any matching can be at most n 2 . Hence, the Acyclic Matching Problem is approximable within a factor of 2k(k−1)+1 k in k-regular graphs, where k is a constant. ♦

To prove the result, we will need the following theorem for the Maximum Independent Set Problem. Theorem 11. [1, 10] The Maximum Independent Set Problem is APXcomplete for k-regular graphs for k ≥ 3.

If G is a k-regular graph in Construction 1, then the constructed graph H is a 2k + 1-regular graph for k ≥ 3. Now, we are ready to prove the APX-completeness of the Acyclic Matching Problem for 2k + 1-regular graphs for k ≥ 3, where k is a constant. For this purpose, we recall the concept of L-reduction. Given two NP optimization problems π 1 and π 2 and a polynomial time transformation f from instances of π 1 to instances of π 2 , we say that f is an L-reduction if there are positive constants α and β such that for every instance x of π 1 :

1. opt π2 (f (x)) ≤ α.opt π1 (x); 2. for every feasible solution y of f (x) with objective value m π2 (f (x), y) = c 2 , we can find a solution y of x in polynomial time with m π1 (x, y ) = c 1 such that |opt π1 (x) − c 1 | ≤ β.|opt π2 (f (x)) − c 2 |.

Theorem 13. The Acyclic Matching Problem is APX-complete for 2k+1regular graphs for k ≥ 3, where k is a constant.

Proof. By Lemma 9, it is clear that the Acyclic Matching Problem for 2k + 1-regular graphs for k ≥ 3 belongs to the class APX. By Theorem 11, it is enough to construct an L-reduction from the instances of the Maximum Independent Set Problem for k-regular graphs to the instances of the Acyclic Matching Problem for 2k + 1-regular graphs. Given a k-regular graph G = (V, E), where V = {v 1 , v 2 , . . . , v n }. We construct a graph H = (V H , E H ), an instance of the Acyclic Matching Problem by Construction 1. It is easy to see by Lemma 7 and Corollary 3 that the reduction described in Construction 1 is an L-reduction with α = 1 and β = 1. Therefore, the Acyclic Matching Problem is APX-complete for 2k + 1regular graphs for k ≥ 3, where k is a constant.

In this paper, we have shown that the Acyclic Matching Decide Problem is NP-complete for comb-convex bipartite graphs and dually chordal graphs. On the positive side, we have shown that the Acyclic Matching Problem can be solved in linear time in split graphs and proper interval graphs. Apart from these, we have shown that the Acyclic Matching Problem cannot be approximated within a factor of n 1− for any > 0, unless P = NP . We have also shown that the Acyclic Matching Problem is APX-complete for 2k +1regular graphs for k ≥ 3, where k is a constant. Further, it will be interesting to study better approximation algorithms for this problem for bipartite graphs and other important graph classes.

Some APX-completeness results for cubic graphs

Degenerate matchings and edge colorings

A lower bound on the acyclic matching number of subcubic graphs

On some hard and some tractable cases of the maximum acyclic matching problem

Generalized subgraph-restricted matchings in graphs

Linear-time certifying recognition algorithms and forbidden induced subgraphs

Elimination orderings of chordal graphs

A linear time recognition algorithm for proper interval graphs

Acyclic matchings in subclasses of bipartite graphs

Optimization, approximation, and complexity classes

A review of tree convex sets test

Linear degree extractors and the inapproximability of max clique and chromatic number