2026/08/04 by Tomohiro Koana, Soh Kumabe
Computer Science · #cs.DS
arxiv created 2026/08/04 · arxiv updated 2026/08/05
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,…,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^*(kO(k))-time algorithms for unweighted λ-vertex-connectivity augmentation for every λ≤ 4 [Carmesin and Ramanujan, SODA 2026], and an O^*((k+λ)O(k))-time algorithm for arbitrary λ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time O^*(36kW). Thus, for λ=2, the unweighted running time improves from O^*(kO(k)) to O^*(36k), 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.