Metraipolis › archive › dc_2d72360eb50b

An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest — arXiv:2610.09932

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09932
License (as archived)
CC0-1.0
Archived
2026-10-08T12:49:44.199Z
SHA-256 of the archived text
6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646
Stable URL of this page
https://metraipolis.com/documento/dc_2d72360eb50b

How to cite

An $n^{0.3+\varepsilon}$-Approximation for Steiner $k$-Forest — arXiv:2610.09932 — arXiv (en), https://arxiv.org/abs/2610.09932 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2d72360eb50b (Metraipolis archive dc_2d72360eb50b, sha256 6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646)
BibTeX
@misc{dc2d72360eb50b,
  title = {An $n^0.3+varepsilon$-Approximation for Steiner $k$-Forest — arXiv:2610.09932},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09932},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2d72360eb50b; sha256 6ce4c98d97a5d1a2a0432d3e69360bf3dffeb4f729c3188b4467c3d7b4b4d646},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09932. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give an $n^{0.3+\varepsilon}$-approximation algorithm for the Steiner $k$-Forest problem, for any constant $\varepsilon>0$. As a function of $n$, this improves over the $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation of Gupta et al. [ESA'07, TALG'10] which has stood for nearly two decades for the general case, as well as the later $n^{0.448}$-approximation of Dinitz et. al [APPROX-RANDOM'14, TALG'17] for the uniform weight case. On the other hand, we show that, due to lower bounds on the Densest $k$-Subgraph problem, the $O(\sqrt k)$-approximation for Steiner $k$-Forest likely cannot be improved. Specifically, we show that for any sufficiently small $\varepsilon>0$, an $O(k^{1/2-\varepsilon})$-approximation for Steiner $k$-Forest would surpass known degree-$n^{\Omega(\varepsilon^2)}$ Sum-of-Squares integrality gaps for Densest k-Subgraph and refute the corresponding dense-versus-random conjecture.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.09932 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:19:30.204Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).