Research map / Graph learning / Graph algorithms and clustering
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a tight factor-revealing LP for the approximation ratio of bipartite (β, β⁻)-EDCS matchings, showing (6,5)-EDCS achieves about 0.677 and beats the long-believed 2/3 limit.
Problem
The approximation ratio of edge-degree constrained subgraphs (EDCS) as a matching sparsifier is known only loosely (2/3 - O(1/β)), especially for small β, so the trade-off between sparsity β and approximation quality is unclear.
Approach
Model any bipartite graph and its EDCS via vertex and edge profiles (degree, Hall's witness membership, matched status in M and M*) and write a factor-revealing LP whose optimum exactly equals the EDCS approximation ratio; solve it numerically over all small (β, β⁻) to reveal that even β with β⁻=β-1 can beat 2/3, with (6,5) best at 0.677.
Key results
- The factor-revealing LP gives the exact approximation ratio of (β, β⁻)-EDCS for bipartite graphs; the best ratio over β, β⁻ in [1,100] is 0.6774 at (β, β⁻)=(6,5).
- For odd β≥7, (β, β-1)-EDCS yields exactly 2/3 approximation; for even β, (β, β-1)-EDCS exceeds 2/3 and converges to 2/3 as β grows (e.g., (10,9) gives 0.6721 and (8,7) gives 0.6756).
- For β⁻ ≤ β-2, the ratio stays below 2/3 (e.g., (10,8) gives 0.6153), approaching 2/3 as β grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use β=6 and β⁻=5 instead of the previous non-tight LP analysis | EDCS approximation analysis · Bipartite maximum matching | approximation ratio: 0.6 -> 0.6774 | Helped |
| Set β=6 and β⁻=5 rather than β=6 and β⁻=4 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.5 -> 0.6774 | Helped |
| Set β=8 and β⁻=7 rather than β=8 and β⁻=6 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.5783 -> 0.6756 | Helped |
| Set β=10 and β⁻=9 rather than β=10 and β⁻=8 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6153 -> 0.6721 | Helped |
| Increase β for even β with β⁻=β−1 beyond 6 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6774 -> 0.6756 -> 0.6721 | Hurt |
| Set β=20 and β⁻=19 rather than β=20 and β⁻=18 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6428 -> 0.6678 | Helped |
| Set β=100 and β⁻=99 rather than β=100 and β⁻=98 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6621 -> 0.6667 | Helped |
| Increase β for (β, β−2)-EDCS (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.4782 -> 0.6621 | Helped |
| Use an even β with β⁻=β−1 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6774 | Helped |
| Use β=6 and β⁻=5 rather than a larger even β with β⁻=β−1 (ablation) | EDCS · Bipartite maximum matching | approximation ratio: 0.6774 | Helped |
| Increase the gap c in (β, β−c)-EDCS (ablation) | EDCS · Bipartite maximum matching | approximation ratio | Hurt |
Surprising findings
- A (6,5)-EDCS beats the widely believed 2/3 approximation limit for EDCS, with ratio about 0.677.
- Increasing β does not monotonically improve the EDCS approximation ratio; the best choice is the small β=6.
Limitations
- The tight analysis applies to bipartite graphs; general graph analysis is not provided.
- Results are numerical (Gurobi-solved LP) for β up to 100 and a pattern for larger β is not proven analytically.
- Reported ratios are from numerical LP solutions rather than closed-form proofs.
Experimental setup
Metrics: approximation ratio of EDCS matching to maximum matching (LP
Baselines: 2/3-approximation bound for EDCS (Bernstein-Stein analysis) hierarchical EDCS factor-revealing LP (0.6 for (6,5))
Builds on: EDCS (Bernstein and Stein) Extended Hall's Theorem factor-revealing LP for hierarchical EDCS
Closest papers by meaning
- The Computational Complexity of Weighted Greedy Matching (AAAI 2017 · similarity 0.88)
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.86)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.86)
- M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering (ICLR 2024 · similarity 0.86)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.86)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.