Reproduce “Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Peter Davies-Peck

Peter Davies-Peck of Durham University devised randomized LOCAL algorithms for 2+ε-approximate maximum matching and minimum weighted vertex cover, achieving O(log n / log^2 log n) rounds for high-degree graphs, thereby demonstrating that the n-dependent term in established lower bounds is a genuine component of complexity rather than a proof artifact.

Key insights

  • The n-dependent term in the Kuhn, Moscibroda, and Wattenhofer lower bound is genuinely necessary for the complexity of distributed approximate matching and vertex cover in high-degree graphs.
  • The O(log Δ / log log Δ) round complexity, previously considered tight, is not universally tight and can be surpassed when Δ is large, demonstrating a log log n-factor improvement.
  • Generalized graph decomposition provides a flexible new tool for reducing effective degree in distributed algorithms, applicable beyond the memorylessness property of specific distributions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.