Metraipolis › archive › dc_32f5abf08a8a
A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation — arXiv:2608.03830
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.03830
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T13:09:34.243Z
- SHA-256 of the archived text
0580afb8ad96e592f986bd5a3a9d5588d363078fef9e41544d7c38ede83c9b4d- Stable URL of this page
https://metraipolis.com/documento/dc_32f5abf08a8a
How to cite
A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation — arXiv:2608.03830 — arXiv (en), https://arxiv.org/abs/2608.03830 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_32f5abf08a8a (Metraipolis archive dc_32f5abf08a8a, sha256 0580afb8ad96e592f986bd5a3a9d5588d363078fef9e41544d7c38ede83c9b4d)
BibTeX
@misc{dc32f5abf08a8a,
title = {A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation — arXiv:2608.03830},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.03830},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_32f5abf08a8a; sha256 0580afb8ad96e592f986bd5a3a9d5588d363078fef9e41544d7c38ede83c9b4d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03830. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is $2$-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted $\lambda$-vertex-connectivity augmentation for every $\lambda\leq 4$ [Carmesin and Ramanujan, SODA 2026], and an $O^*((k+\lambda)^{O(k)})$-time algorithm for arbitrary $\lambda$ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time $O^*(36^kW)$. Thus, for $\lambda=2$, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. We reduce the problem to a boundary-pair variant of $2$-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the $2$-vertex-connected spanning graphs.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.03830 — 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-31T12:57:43.021Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).