Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.13264 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914563103916032 |
|---|---|
| author | Davies-Peck, Peter |
| author_facet | Davies-Peck, Peter |
| contents | The classic lower bound of Kuhn, Moscibroda and Wattenhofer [JACM 2016] states that approximate maximum matching and approximate vertex cover (among other problems) in the LOCAL model require $Ω(\min\{\sqrt{\frac{\log n}{\log\log n}}, \frac{\log Δ}{\log\log Δ}\})$ rounds, for any polylogarithmic or smaller approximation ratio. As a function of $Δ$, this complexity was subsequently matched for constant-approximate weighted vertex cover [Bar-Yehuda, Censor-Hillel and Schwartzman, JACM 2017] and constant-approximate maximum matching [Bar-Yehuda, Censor-Hillel, Ghaffari and Schwartzman, PODC 2017]. One might expect, therefore, that the true complexity should be $Θ(\frac{\log Δ}{\log\log Δ})$, and the $n$-dependent term in the lower bound is just an artefact of the proof method.
We show that this is not the case, and a term dependent on $n$ is in fact required. Specifically, we show randomized algorithms for $2+\varepsilon$-approximate maximum matching and approximate (weighted) minimum vertex cover taking $O(\frac{\log n}{\log^2 \log n})$ rounds. Our algorithms are based on a novel graph decomposition result generalizing the method of Miller, Peng and Xu [SPAA 2013], which we use to reduce the `effective' degree of high-degree graphs. We expect that this decomposition may be of further use for other problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13264 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition Davies-Peck, Peter Data Structures and Algorithms The classic lower bound of Kuhn, Moscibroda and Wattenhofer [JACM 2016] states that approximate maximum matching and approximate vertex cover (among other problems) in the LOCAL model require $Ω(\min\{\sqrt{\frac{\log n}{\log\log n}}, \frac{\log Δ}{\log\log Δ}\})$ rounds, for any polylogarithmic or smaller approximation ratio. As a function of $Δ$, this complexity was subsequently matched for constant-approximate weighted vertex cover [Bar-Yehuda, Censor-Hillel and Schwartzman, JACM 2017] and constant-approximate maximum matching [Bar-Yehuda, Censor-Hillel, Ghaffari and Schwartzman, PODC 2017]. One might expect, therefore, that the true complexity should be $Θ(\frac{\log Δ}{\log\log Δ})$, and the $n$-dependent term in the lower bound is just an artefact of the proof method. We show that this is not the case, and a term dependent on $n$ is in fact required. Specifically, we show randomized algorithms for $2+\varepsilon$-approximate maximum matching and approximate (weighted) minimum vertex cover taking $O(\frac{\log n}{\log^2 \log n})$ rounds. Our algorithms are based on a novel graph decomposition result generalizing the method of Miller, Peng and Xu [SPAA 2013], which we use to reduce the `effective' degree of high-degree graphs. We expect that this decomposition may be of further use for other problems. |
| title | Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.13264 |