Problem 16: Graph Matchings

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
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?

Notes

  1. An augmenting path is a simple paths of odd length such that every second edge in the current matching.
  2. An augmenting cycle is an even length cycles such that every second edge is in the matching and swapping the matched edges for the unmatched edges will increase the weight of the matching.