A 2/3-Approximation Algorithm for the Residual Maximum Matching Problem in General Graphs

Introduction

An edge coloring partitions the edges of a graph into matchings, with each color class consisting of edges that have no common endpoints. This structure also describes pairwise tasks performed in successive stages: tasks in the same stage cannot share an endpoint, whereas vertex resources can be reused in different stages. When two stages have strict priorities, the first stage must accommodate as many tasks as possible, and the number of tasks in the second stage is then maximized over the remaining edges. The resulting optimization problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number.

In their work on edge coloring, Gabow, Nishizeki, Kariv, Leven, and Terada introduced the lexicographical matching problem, which lexicographically maximizes the cardinalities of two edge-disjoint matchings, and established related hardness results [1]. This model is equivalent to the residual maximum matching problem. Kamalian and Mkrtchyan further studied residual matching numbers after the deletion of a maximum matching and proved that the associated optimization problems remain NP-hard even for connected bipartite graphs of maximum degree three [2]. Once the first matching is fixed, a maximum matching of the residual graph can be found in polynomial time; the difficulty lies in choosing the first maximum matching.

Let $\nu(G)$ denote the matching number of $G$, and let $L(G)$ and $l(G)$ denote, respectively, the largest and smallest residual matching numbers obtained by deleting a maximum matching. Khojabaghyan and Mkrtchyan proved that $L(G) \le2l(G)$ for every graph and that $L(G) \le3l(G)/2$ when $G$ has a perfect matching [3]. Thus, an arbitrary maximum matching gives a 1/2-approximation in general graphs and a 2/3-approximation in graphs with a perfect matching. Mkrtchyan subsequently studied the approximation complexity of these parameters [4], using the above 1/2 guarantee for general graphs and proving that, unless $P = NP$, for every $0 < \varepsilon< 1/88$ there is no polynomial-time $(1-\varepsilon)$-approximation algorithm for $L(G)$ on connected bipartite graphs.

The maximum 2-edge-colorable subgraph problem, in contrast, maximizes the total number of edges in two edge-disjoint matchings. Kosowski gave a 5/6-approximation algorithm [5], and Chen, Konno, and Matsushita improved the guarantee to approximately 0.842 [6]. Chen, Fan, and Wang further studied parameterized algorithms for finding two edge-disjoint matchings and approximation algorithms for their total weight [7]. These results optimize the combined size or weight of the two matchings, whereas the lexicographical model requires the first matching to have cardinality exactly $\nu(G)$. A maximum 2-edge-colorable subgraph need not contain a maximum matching of the original graph [4]. Consequently, approximation guarantees for the combined objective do not directly yield guarantees for $L(G)$.

We improve the above 1/2 baseline for general graphs to 2/3. Our algorithm uses single-edge exchanges involving free vertices: an edge of the current maximum matching is replaced by an adjacent edge whose other endpoint is free, and the exchange is accepted only if it increases the residual matching number. Each accepted exchange preserves the maximum cardinality of the first matching and increases the residual matching number by one. Using standard maximum matching algorithms [8, 9], the procedure runs in $O(n^5)$ time and $O(n^2)$ space. The key observation is that, at termination, every edge of the maximum matching whose individual addition to the residual graph increases its matching number, called a critical edge, has neither endpoint adjacent to a free vertex. Combining this structural property with a deficit bound for noncritical edges and an assignment argument on oriented alternating paths and cycles, we establish the 2/3 approximation guarantee, extending the ratio for graphs with a perfect matching to general graphs. A seven-vertex example shows that the 2/3 bound implied by this termination condition is tight.

Problem definition and preliminaries

Problem definition

Let $G = (V, E)$ be a finite simple undirected graph with $n = |V|$ and unweighted edges. Write $\nu(G)$ for the cardinality of a maximum matching of $G$, and let $\mathcal{M}(G)$ be the set of all maximum matchings of $G$. For an edge set $S \subseteq E$, let $V(S)$ denote the set of its endpoints, and let $G - S$ denote the graph obtained by deleting only the edges of $S$ and retaining all vertices. For an edge $e$ not already present in a graph $G$, let $G + e$ denote the graph obtained by adding $e$.

The objective is to maximize the residual matching number after deleting a maximum matching:

Different maximum matchings may yield different residual matching numbers. For example, the five-vertex path in Figure 1 has $\nu(G) = 2$, but deleting the maximum matchings $M = \{12, 45\}$ and $M' = \{23, 45\}$ gives $\nu(G - M) = 1$ and $\nu(G - M') = 2$, respectively.

Symmetric difference and alternating paths

For two matchings $A$ and $B$, their symmetric difference is $A \mathbin{\triangle} B = (A \setminus B) \cup(B \setminus A)$. In the graph formed by these edges, every connected component containing an edge is an alternating path or an even cycle, with edges of $A \setminus B$ and $B \setminus A$ appearing alternately. If the first and last edges of a path both belong to $A \setminus B$, then the path contains one more $A$-edge than $B$-edge. Replacing the $B$-edges on the path by its $A$-edges therefore yields a matching with one more edge than $B$ [8].

In particular, if $A$ and $B$ are both maximum matchings of the same graph, every path component must contain equal numbers of the two types of edges. Otherwise, exchanging the two types along that path would increase one of the matchings, contradicting its maximum cardinality. Thus, every connected component of $A \triangle B$ containing an edge is an alternating path of even length or an alternating cycle, with equal numbers of $A$-edges and $B$-edges [9].

The single-edge exchange algorithm

The exchange criterion

Let $M$ be the current maximum matching, and let $H = G - M$ and $\mu= \nu(H)$. The vertices in $V \setminus V(M)$ are called $M$-free vertices. An edge $e \in M$ is critical with respect to $H$ if $\nu(H + e) = \mu+ 1$, and noncritical if $\nu(H + e) = \mu$.

Let $u$ be an $M$-free vertex, and suppose that $vw \in M$ and $uv \in E$. Set

Since $u$ is free, $M'$ is a matching of the same cardinality as $M$ and is therefore also maximum. Figure 2 illustrates this exchange.

Proof. Adding one edge increases the matching number by at most one. If $vw$ is critical, then $\nu(H+vw)=\mu+1$. Take a matching $N^+$ of cardinality $\mu+1$ in $H+vw$. It must contain $vw$; otherwise it would be a matching in $H$, contradicting $\nu(H)=\mu$. Since $uv$ and $vw$ share the vertex $v$, the matching $N^+$ does not contain $uv$ and is therefore also a matching in $H+vw-uv=G-M'$. Together with $G-M'\subseteq H+vw$, this gives

Hence $\nu(G-M')=\mu+1$.

Conversely, if $\nu(G-M')=\mu+1$, then the inclusion $G-M'\subseteq H+vw$ gives

Thus $\nu(H+vw)=\mu+1$, so $vw$ is critical.

The algorithm and its termination property

Algorithm 1 starts with an arbitrary maximum matching and repeatedly performs the improving exchanges described in Lemma 1.

Proof. By Lemma 1, each successful exchange preserves the maximum cardinality of $M$ and increases the integer $\mu$ by one. Since $\mu\leq\lfloor n/2\rfloor$, the number of exchanges is bounded. At termination, every matching edge with an endpoint adjacent to a free vertex has been tested without yielding an improvement. Thus property (S) holds.

Algorithm 1 Single-edge exchange algorithm

Input: A finite simple undirected graph $G$.

Output: A maximum matching $M$ of $G$ and a maximum matching $N$ of the residual graph $G - M$.

1. Find an arbitrary maximum matching $M$ of $G$.

2. Set $H = G - M$. Find a maximum matching $N$ of $H$, and set $\mu= |N|$ and $U = V \setminus V(M)$.

3. Scan the edges $vw \in M$ in a fixed order. If neither endpoint has a neighbor in $U$, continue the scan.

4. Otherwise, choose any vertex $u$ with $u \in U$ and $uv \in E$, and compute $\nu(H + vw)$.

5. If $\nu(H + vw) = \mu+ 1$, set $M \leftarrow(M \setminus\{vw\}) \cup\{uv\}$ and return to Step 2.

6. If the scan ends without a successful exchange, output $(M,N)$.

Equivalently, property (S) states that neither endpoint of any critical edge in $M$ has a neighbor in $U$.

A deficit bound for noncritical edges

Lemma 2. Let $M$ be a maximum matching of a graph $G$, and let $H = G - M$ and $\mu= \nu(H)$. Let $N_0$ be a matching of cardinality $\mu- t$ in $H$, and let $Z \subseteq M$ consist of edges that are noncritical with respect to $H$. If $V(Z) \cap V(N_0) = \varnothing$, then

Proof. Take a maximum matching $N$ of $H$ and set $R = N_0 \cup Z$. By the vertex-disjointness assumption, $R$ is a matching and $|R| = \mu- t + |Z|$. In $R \mathbin{\triangle} N$, let $p$ count the path components with one more $R$-edge than $N$-edge, and let $q$ count those with one more $N$-edge than $R$-edge. The remaining components do not affect the difference in cardinalities, so

Each path counted by $p$ contains at least two edges of $Z$. Indeed, if it contains no edge of $Z$, as in Figure 3(a), then the entire path lies in $H$ and is an $N$-augmenting path, contradicting the maximum cardinality of $N$. If it contains exactly one edge $e \in Z$, as in Figure 3(b), then the entire path lies in $H + e$, and augmenting along it yields a matching of cardinality $\mu+ 1$. However, $e$ is noncritical, so $\nu(H + e) = \mu$, a contradiction.

These $p$ paths are pairwise vertex-disjoint, and each contains at least two edges of $Z$. They therefore contain at least $2p$ distinct edges of $Z$ in total, giving $2p \le|Z|$. Together with (5), this yields $|Z| - t \le|Z|/2$, which proves the claim.

The approximation guarantee for general graphs

Throughout this section, let $M$ be a maximum matching satisfying property (S), and write $H = G - M$ and $\mu= \nu(H)$. Take an optimal matching pair $(F, Q)$, where $F$ is a maximum matching of $G$, $Q$ is a maximum matching of $G - F$, and $|Q| = L(G)$. For brevity, write $L = L(G)$.

The comparison matching and noncritical conflict edges

Define

We call $K$ the conflict edge set. Since $F \cap Q = \varnothing$, we have $K \subseteq M \setminus F$. Moreover, $F \setminus M$ is a matching in $H$, so

Let $r = |(M \setminus F) \setminus K| = a - c$. Figure 4 illustrates the relationships among these edge sets.

Deleting the conflict edges from $Q$ gives a matching of cardinality $L - c$ in $H$. Following the comparison matching construction used in [3] to prove the bound for graphs with a perfect matching, let $W = V(K)$ and set

We have $X \cap M = \varnothing$. Indeed, suppose that $f \in X \cap M$. Since the endpoints of $f$ are already covered by $K \subseteq M$, the matching property of $M$ implies $f \in K \subseteq Q$, contradicting $F \cap Q = \varnothing$. Furthermore, $Q \setminus M = Q \setminus K$. Because $Q$ is a matching, the edges of $Q \setminus K$ have no common endpoints with the edges of $K$, and hence all their endpoints lie outside $W = V(K)$. Both endpoints of every edge of $X$, on the other hand, lie in $W$. Thus $Q \setminus M$ and $X$ are vertex-disjoint. As both are matchings in $H$,

is a matching in $H$, satisfying

Figure 5 illustrates this construction: after deleting the conflict edge set $K$ from $Q$, we add the edges of $X$ between endpoints of $K$ to obtain the matching $N_0$ in $H$.

Let $Z$ be the set of noncritical edges in $K$ that are vertex-disjoint from $X$, and write $z = |Z|$.

Proof. Since $Z \subseteq K \subseteq M$, the set $Z$ is a matching disjoint from $E(H)$, and each of its edges is noncritical with respect to $H$. As $K \subseteq Q$ and $Q$ is a matching, $Z$ is vertex-disjoint from $Q \setminus M$; by definition, $Z$ is also vertex-disjoint from $X$. Hence $V(Z) \cap V(N_0) = \varnothing$. Applying Lemma 2 to $N_0$ in (8) proves the claim. $\square$

An assignment argument on oriented alternating components

The remaining conflict edges $K \setminus Z$ consist of critical edges and noncritical edges sharing an endpoint with an edge of $X$. We use the alternating structure of $M \mathbin{\triangle} F$ to bound their number.

Proof. Since $M$ and $F$ are both maximum matchings, every component of $M \mathbin{\triangle} F$ containing an edge is an alternating path of even length or an even cycle. Orient each path from its $F$-free endpoint to its $M$-free endpoint, and choose either cyclic orientation for each cycle. Then each edge of $M \setminus F$ is immediately followed by a unique adjacent edge of $F \setminus M$, as illustrated in Figure 6.

For a critical edge $e \in K$, let $f$ be the edge of $F \setminus M$ immediately following it. There must be an edge $e' \in M \setminus F$ immediately after $f$. On a cycle, this follows from the alternating structure. On a path, if $f$ were the last edge, it would join an endpoint of $e$ to an $M$-free vertex; property (S) would then force $e$ to be noncritical, a contradiction. Thus $e$, $f$, $e'$ are three consecutive edges. If $e' \in K$, both endpoints of $f$ lie in $W$, so $f \in X$; assign $e$ to $f$. If $e' \notin K$, assign $e$ to $e' \in(M \setminus F) \setminus K$.

For a noncritical edge $e \in K \setminus Z$, the definition ensures that $e$ shares an endpoint with at least one edge of $X$; assign $e$ to any such edge. Every edge of $K \setminus Z$ has now been assigned exactly once. The three cases are illustrated in Figure 7.

Each edge $f \in X$ receives assignments only from edges of $K$ sharing an endpoint with it. Since $K$ is a matching, each endpoint of $f$ is incident to at most one edge of $K$, so $f$ receives at most two assignments. An edge $e' \in(M \setminus F) \setminus K$ receives an assignment only under the second rule for critical edges, which requires the consecutive order $e$, $f$, $e'$. Once the orientation is fixed, the predecessor $f$ of $e'$ and the predecessor $e$ of $f$ on the path or cycle are both unique. Hence $e'$ receives at most one assignment. The two types of receiving edges accommodate at most $2x+r$ assignments in total, and therefore $|K \setminus Z| = c-z \le2x+r$.

The main theorem

Proof. By Lemmas 3 and 4,

Substituting $t=\mu-(L-c+x)$ and $r=a-c$ gives

Using $a\le\mu$ from (6), we obtain

Thus $\mu\ge2L/3$. □

Running time and tightness

Running time

Proof. A maximum matching in a general graph can be found in $O(n^3)$ time and $O(n^2)$ space [8, 9]. Each scan considers at most $\lfloor n/2 \rfloor$ matching edges. For each edge, finding a free neighbor takes $O(n)$ time, and the maximum matching subroutine is called at most once to compute the matching number after adding that edge back. Thus each scan takes $O(n^4)$ time. By Proposition 1, there are at most $O(n)$ successful exchanges. Initialization and the recomputation of a residual maximum matching in each round are also covered by this bound. Hence the total running time is

An adjacency-matrix representation of the graph, together with sequential reuse of the workspace of the maximum matching subroutine, requires $O(n^2)$ total space.

Tightness of the termination condition

Proof. Let $V = \{0, 1, 2, 3, 4, 5, 6\}$ and

Set $M = \{14, 23, 56\}$, as shown in Figure 8(a). Since $|V| = 7$, we have $\nu(G) \le3$, so $M$ is maximum. The nonisolated part of the residual graph $H = G - M$ is the path $2 - 1 - 0 - 4 - 5$, and thus $\nu(H) = 2$.

The only $M$-free vertex is 0, whose only neighbors are 1 and 4. Hence 14 is the only matching edge that needs to be tested. The nonisolated vertices of $H + 14$ are still 0, 1, 2, 4, 5, so its matching number is at most two. Consequently, $\nu(H + 14) = \nu(H) = 2$, and property (S) holds. On the other hand, $F = \{01, 23, 45\}$ and $Q = \{04, 12, 56\}$ are two edge-disjoint matchings, each with three edges, as shown in Figure 8(b). Thus $L(G) = 3$, and $\nu(G - M) = 2L(G)/3$.

Conclusion

We have presented a $2/3$-approximation algorithm for the residual maximum matching problem in general unweighted graphs. Through single-edge exchanges involving free vertices, the algorithm obtains a maximum matching satisfying a local termination condition. A deficit bound for noncritical edges and an assignment argument on oriented alternating components together establish the approximation guarantee implied by this condition, and an example attains the bound. Further research may investigate whether stronger local improvement conditions can yield a ratio better than $2/3$, and how the structural analysis developed here can be extended to the residual maximum matching problem in weighted graphs.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

The authors used an AI assistant for translation and language revision, manuscript organization, mathematical discussion, and reference checking. The authors reviewed and edited the content as needed and assume full responsibility for all content.