<p>This is a combination of comments from me and Chandra Chekuri above, elaborated a bit.</p>

<p>As background, if you have a partial matching then its symmetric difference with the optimal matching can be decomposed into disjoint alternating paths (and possibly also some alternating cycles but those can be ignored). <a href="https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm">Hopcroft–Karp</a> maintains a partial matching as it proceeds in a sequence of stages. Each stage exhausts all the shortest alternating paths left over from the previous stage, and increases the shortest alternating path length by at least two (because the length must be odd). Each stage takes linear time. The exact algorithm can be proven to take $O(\sqrt n)$ stages, leading to a nonlinear total runtime.</p>

<p>First, the additive approximation. If the shortest alternating path length is $k$, then the symmetric difference between your matching and optimal can have at most $n/k$ disjoint alternating paths, so the difference in cardinality between your matching and optimal is at most $n/k$. So if you set $k=1/\epsilon$ for your favorite constant $\epsilon$, and stop after $k/2$ stages, you should get an additive approximation of $\epsilon n$ to the optimal matching, in time $O((m+n)/\epsilon=O(m+n)$.</p>

<p>Now, for a multiplicative approximation, again suppose that the shortest alternating path length is $k$, and observe that each alternating path includes at least $(k-1)/2$ edges that are already part of your matching. So the ratio between the number of edges you already have in the alternating paths and the number you can get by adding one more edge per alternating path is at most $$\frac{k-1}{2}\left/\left(\frac{k-1}{2}+1\right)\right.\approx 1-\frac{2}{k}.$$ Therefore, if you set $k\approx 2/\epsilon$, and again do only $k/2$ stages before stopping, you will get a $(1-\epsilon)$-approximation, again in time $O(m+n)$.</p>

CC BY-SA 3.0
2014-12-03T07:30:25.553Z
2014-12-03T07:36:35.703Z
2014-12-03T07:36:35.703Z
David Eppstein
<p>I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$.  So the graph is:</p>

<p>$$G(A ∪ B, E)\ \ where\ \  |A| = |B| = n, \ \ \ \ E ⊆ A × B \  \ \ and\ \ \  |E| = m$$</p>

<p>The algorithm should produce an $\epsilon$-approximate maximum matching $M_{\epsilon}$ such that:</p>

<p>$$|M_{\epsilon}| \geq (1-\epsilon)M_{optimal} \ \ \ for\ \ \ 0 \leq \epsilon \leq 1$$</p>

<p>I am aware that the Hopcroft-Karp algorithm can produce an $M_{optimal}$ but I have heard one can modify Hopcroft-Karp to produce an $\epsilon$-approximate maximum matching ($M_{\epsilon}$) instead.  I am currently out of ideas in how to approach this.</p>

<p>To clarify: I am only concerned about unweighted matchings.</p>

CC BY-SA 3.0
2014-12-02T20:51:55.437Z
Why do you have to modify anything?  An (optimal) maximum matching is an ε-approximate maximum matching.  Do you need a faster algorithm than Hopcroft–Karp?  Or do you have some other requirements?  Please state your requirements in the question.
Tsuyoshi Ito
CC BY-SA 3.0
2014-12-02T22:09:37.030Z
@TsuyoshiIto Im hoping to find an algorithm that is faster than Hopcroft-Karp because I only have to find an approximation now, instead of the maximum/optimal matching.  I believe there is a simple way to devise an algorithm that finds this $\epsilon$-approximate matching in $O(m/\epsilon)$ and I believe that we can accomplish this by modifying Hopcroft-Karp in some way - I'm currently stuck out of ideas.
Bitwise
CC BY-SA 3.0
2014-12-03T03:11:46.850Z
Maybe you were thinking of the easy additive approximation (to within $\epsilon n$ edges) obtained by stopping when the paths grow to length $\Theta(1/\epsilon)$?
David Eppstein
CC BY-SA 3.0
2014-12-03T04:15:12.733Z
@DavidEppstein I think stopping the augmenting path algorithm after paths reach $\Omega(1/\epsilon)$ should give a $(1-\epsilon)$-approximation, no?
Chandra Chekuri
CC BY-SA 3.0
2014-12-03T05:49:06.643Z
@DavidEppstein You're right, that's the method I'm hoping to understand. I would appreciate it if you could elaborate on that as an answer below. I'm particularly confused about proving the run-time, so any explanation about that would be helpful.
Bitwise
CC BY-SA 3.0
2014-12-03T22:09:11.533Z
As I said, you should state the requirement in the question, not in a comment.
Tsuyoshi Ito
<graph-theory><graph-algorithms><approximation-algorithms><matching>
Modifying Hopcroft-Karp algorithm to get approximate bipartite matching
Bitwise
# Modifying Hopcroft-Karp algorithm to get approximate bipartite matching

(Asked by: username_0 on 2014-12-02)

I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M\_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$. So the graph is:

$$G(A ∪ B, E)\ \ where\ \ |A| = |B| = n, \ \ \ \ E ⊆ A × B \ \ \ and\ \ \ |E| = m$$

The algorithm should produce an $\epsilon$-approximate maximum matching $M\_{\epsilon}$ such that:

$$|M\_{\epsilon}| \geq (1-\epsilon)M\_{optimal} \ \ \ for\ \ \ 0 \leq \epsilon \leq 1$$

I am aware that the Hopcroft-Karp algorithm can produce an $M\_{optimal}$ but I have heard one can modify Hopcroft-Karp to produce an $\epsilon$-approximate maximum matching ($M\_{\epsilon}$) instead. I am currently out of ideas in how to approach this.

To clarify: I am only concerned about unweighted matchings.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, matching

> **Comments:**
> **username_1**: Why do you have to modify anything?  An (optimal) maximum matching is an ε-approximate maximum matching.  Do you need a faster algorithm than Hopcroft–Karp?  Or do you have some other requirements?  Please state your requirements in the question.  
> **username_0**: @TsuyoshiIto Im hoping to find an algorithm that is faster than Hopcroft-Karp because I only have to find an approximation now, instead of the maximum/optimal matching.  I believe there is a simple way to devise an algorithm that finds this $\epsilon$-approximate matching in $O(m/\epsilon)$ and I believe that we can accomplish this by modifying Hopcroft-Karp in some way - I'm currently stuck out of ideas.  
> **username_2**: Maybe you were thinking of the easy additive approximation (to within $\epsilon n$ edges) obtained by stopping when the paths grow to length $\Theta(1/\epsilon)$?  
> **username_3**: @DavidEppstein I think stopping the augmenting path algorithm after paths reach $\Omega(1/\epsilon)$ should give a $(1-\epsilon)$-approximation, no?  
> **username_0**: @DavidEppstein You're right, that's the method I'm hoping to understand. I would appreciate it if you could elaborate on that as an answer below. I'm particularly confused about proving the run-time, so any explanation about that would be helpful.  
> **username_1**: As I said, you should state the requirement in the question, not in a comment.  

---

## 1 answers

### Answer by username_2 on 2014-12-03. Score: 9 | Accepted answer

This is a combination of comments from me and username_3 above, elaborated a bit.

As background, if you have a partial matching then its symmetric difference with the optimal matching can be decomposed into disjoint alternating paths (and possibly also some alternating cycles but those can be ignored). [Hopcroft–Karp](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm) maintains a partial matching as it proceeds in a sequence of stages. Each stage exhausts all the shortest alternating paths left over from the previous stage, and increases the shortest alternating path length by at least two (because the length must be odd). Each stage takes linear time. The exact algorithm can be proven to take $O(\sqrt n)$ stages, leading to a nonlinear total runtime.

First, the additive approximation. If the shortest alternating path length is $k$, then the symmetric difference between your matching and optimal can have at most $n/k$ disjoint alternating paths, so the difference in cardinality between your matching and optimal is at most $n/k$. So if you set $k=1/\epsilon$ for your favorite constant $\epsilon$, and stop after $k/2$ stages, you should get an additive approximation of $\epsilon n$ to the optimal matching, in time $O((m+n)/\epsilon=O(m+n)$.

Now, for a multiplicative approximation, again suppose that the shortest alternating path length is $k$, and observe that each alternating path includes at least $(k-1)/2$ edges that are already part of your matching. So the ratio between the number of edges you already have in the alternating paths and the number you can get by adding one more edge per alternating path is at most $$\frac{k-1}{2}\left/\left(\frac{k-1}{2}+1\right)\right.\approx 1-\frac{2}{k}.$$ Therefore, if you set $k\approx 2/\epsilon$, and again do only $k/2$ stages before stopping, you will get a $(1-\epsilon)$-approximation, again in time $O(m+n)$.


---

