Problem 16: Graph Matchings
| Suggested by | Andrew McGregor |
|---|---|
| Source | Kanpur 2006 |
| Short link | https://sublinear.info/16 |
Given a weighted graph with $n$ nodes and $m$ edges, the maximum weighted matching (MWM) problem is to find the set of edges of maximum weight such that no two edges share an end-point. MWM is a classic graph problem and exact polynomial solutions are known [Edmonds-65,Gabow-90,HopcroftK-73,MicaliV-80]. The fastest of these algorithms solves the maximum weighted matching problem with running time $O(nm+ n^2 \log n)$. For massive graphs this is still too much and there has been recent work on finding faster approximate algorithms. For the unweighted problem, a linear-time approximation-scheme is known [KalantariS-95]. The best general result is a linear time $(2/3-\epsilon)$-approximation [DrakeH-03,PettieS-04].
Algorithms in the data stream model were presented in [McGregor-05]. These include $O(n\log n)$-space, $O_\epsilon(1)$-pass algorithms that return a $(1-\epsilon)$-approximation in the unweighted case and a $(1/2-\epsilon)$-approximation in the weighted case. Both are also linear time algorithm in the RAM model. The algorithms for unweighted matching are based on finding augmenting paths[1] for an existing matching. Many of the ideas used for finding augmenting paths in the unweighted case carry over to the weighted case. However, it seems that the intrinsic difficulty in achieving a $(1-\epsilon)$-approximation in the weighted case is that there may be augmenting cycles[2]. It seems hard to find augmenting cycles in the streaming model. Is there a lower-bound or does there exist an $O_\epsilon(1)$-pass $O(n\log n)$-space algorithm that returns an $(1-\epsilon)$-approximation for MWM? In the RAM model, does there exist a linear time $(1-\epsilon)$-approximation for MWM?
