Metraipolis › archive › dc_d9ccae1f44bc
A Linear-Time Approximation Scheme for the Densest Subgraph Problem — arXiv:2608.11094
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11094
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T06:37:02.767Z
- SHA-256 of the archived text
99962f8927896c7abf36ba76bbd02c7a919c7d26019b2dffceceab662151eef5- Stable URL of this page
https://metraipolis.com/documento/dc_d9ccae1f44bc
How to cite
A Linear-Time Approximation Scheme for the Densest Subgraph Problem — arXiv:2608.11094 — arXiv (en), https://arxiv.org/abs/2608.11094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d9ccae1f44bc (Metraipolis archive dc_d9ccae1f44bc, sha256 99962f8927896c7abf36ba76bbd02c7a919c7d26019b2dffceceab662151eef5)
BibTeX
@misc{dcd9ccae1f44bc,
title = {A Linear-Time Approximation Scheme for the Densest Subgraph Problem — arXiv:2608.11094},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11094},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d9ccae1f44bc; sha256 99962f8927896c7abf36ba76bbd02c7a919c7d26019b2dffceceab662151eef5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-12 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.11094 — 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-19T06:28:19.216Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).