2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Dec 2 '14 at 20:51
  • $\begingroup$ @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. $\endgroup$ – Bitwise Dec 2 '14 at 22:09
  • $\begingroup$ 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)$? $\endgroup$ – David Eppstein Dec 3 '14 at 3:11
  • $\begingroup$ @DavidEppstein I think stopping the augmenting path algorithm after paths reach $\Omega(1/\epsilon)$ should give a $(1-\epsilon)$-approximation, no? $\endgroup$ – Chandra Chekuri Dec 3 '14 at 4:15
  • $\begingroup$ @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. $\endgroup$ – Bitwise Dec 3 '14 at 5:49
8
$\begingroup$

This is a combination of comments from me and Chandra Chekuri 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 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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.