CS Paper Radar

Optimal Online Weighted Connectivity Augmentation

Mohit Garg, Felix Hommelsheim, Alexander Lindermayr

cs.DS ·submitted 2026-10-30 17:14 UTC · v1
theory

Abstract

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes $(k+1)$-edge-connected. The goal is to minimize the total cost of the purchased links. We obtain a deterministic polynomial-time $O(\log n)$-competitive algorithm for WCAP, improving the previous $O(\log^2 n)$ bound (SODA 2026). Our bound is asymptotically optimal, even for randomized algorithms in the random-order model. The general problem reduces to the case where the underlying graph is a cycle, for which link costs in $\{0,1\}$ already yield an $Ω(\log n)$ lower bound. Surprisingly, for unit costs on a cycle, we obtain a deterministic polynomial-time $4$-competitive algorithm, improving the previous $O(\log n)$ bound (SODA 2026), and prove that this ratio is optimal among deterministic algorithms. Thus, with unit costs, cycles are easier than trees, where the optimal competitive ratio is $Θ(\log n)$.

Comment
32 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.83
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.18

Online Survivable Network Design with Arbitrarily Small Connectivity Loss

cs.DS ·2026-11-12 ·MohammadTaghi Hajiaghayi, Saeed Seddighin
similarity 0.80
Abstract

In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. Each request is a pair of vertices $(s,t)$ with a connectivity requirement $k$, and the algorithm must irrevocably buy edges so that $s$ and $t$ are joined by $k$ edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~\cite{GKR12} obtain an $O(k\log^3 n)$-competitive algorithm, where $k$ is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~\cite{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of $2+\varepsilon$. We show that relaxing the connectivity requirement by a factor of only $1+\varepsilon$ suffices to obtain a polylogarithmic competitive ratio.

0.19

Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting Set

cs.DS ·2026-11-05 ·Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, Michael Zlatin
hot direction similarity 0.75
Abstract

We study the Online Connectivity Augmentation Problem (OCAP) with cut arrivals. In this problem, we are given a $k$-edge-connected graph $G = (V,E)$ with $|V| = n$ and a set of links $L \subseteq \binom{V}{2}$. In each iteration, a minimum cut arrives to be augmented, and we seek to maintain a smallest set of links crossing all such cuts. This problem is a special case of online hitting set in which the ground set is $L$ and a sequence of sets to be hit arrive from $\mathcal{C} = \{δ_L(C) : |δ_E(C)| = k\}$. As such, OCAP admits a $O(\log^2 n)$-competitive algorithm using the classical algorithm for Online Set Cover of Alon, Awerbuch, Azar, Buchbinder, and Naor. If $k$ is odd, then OCAP reduces to the case where $G$ is a tree. This case was studied by Naor, Umboh, and Williamson, who gave an optimal $O(\log n)$-competitive algorithm, which even holds in weighted setting. Recently, Garg and Subramanian gave an $O(\log n)$-competitive algorithm for unweighted OCAP which holds in the popular node-arrival model, but not for cut-arrivals. No better than $O(\log^2 n)$-competitive algorithm is known for weighted OCAP. In this paper, we provide a nearly optimal $O(\log n \log \log n)$-competitive algorithm for weighted OCAP under cut-arrivals and an optimal $O(\log n)$-competitive algorithm for unweighted OCAP with cut-arrivals. We also give an $O(1)$ algorithm for Online Cycle Augmentation under node-arrivals. Since no $o(\log n)$-competitive algorithm is possible on a cycle with cut-arrivals, this establishes a separation between the best competitive ratio achievable in the two arrival models.

0.49

Hardness of Online Directed Steiner Network

cs.DS ·2026-09-18 ·Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.72
Abstract

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

0.40

Pairwise Reconnection for Cost-Distance Steiner Trees

cs.DS ·2026-11-06 ·Edgar Perner
theory similarity 0.70
Abstract

The Uniform Cost-Distance Steiner Tree Problem asks for a rooted tree that minimizes the connection cost plus a weighted sum of root-to-terminal distances. We develop an algorithm that constructs two candidate trees: one based on direct connections to the root and another that pairs selected vertices and connects each pair to the root. The algorithm selects the tree with the smaller objective value. The resulting randomized algorithm achieves expected approximation factors of $1.698$ in the spanning case and $2.041$ in the general case, and it can be derandomized in polynomial time. The pairwise matching analysis charges part of the augmentation cost directly to the connection and delay costs of an optimal solution, rather than only to the separated lower bound used in previous analyses. This allows the $1.698$ factor to fall below the maximum multiplicative gap of $1+1/\sqrt{2}$ between the optimum value and that lower bound. We give instance families with approximation-ratio lower bounds approaching $1+1/\sqrt{2}$ for cut-and-reconnect algorithms that start from a minimum spanning tree and $3/2$ for the present algorithm. Finally, we show that the Uniform Cost-Distance Steiner Tree Problem and the Steiner-tree version of the Cable-Trench Problem are approximation equivalent up to an arbitrarily small additive loss.

0.20

Optimal Non-Adaptive Vantage Point Selection

cs.DS ·2026-09-09 ·Jie Gao, Nicole Wein, Chang Wu
theory similarity 0.70
Abstract

We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of estimating bottleneck capacities on the Internet. The input is a weighted undirected graph with unique shortest paths where every edge has a distinct unknown \emph{capacity}. When the algorithm \emph{queries} a vertex $v$, it reveals the minimum-capacity edge on the shortest path from $v$ to every other vertex reachable from $v$. The goal is to maximize the total number of revealed edges. The quality of an algorithm is measured by its competitive ratio against an optimal algorithm that knows all edge capacities a priori. We first consider the foundational single-query setting, where both the algorithm and the optimal algorithm are restricted to a single query. There is a trivial upper bound of $O(n)$ on the competitive ratio and the best known lower bound was $\tildeΩ(\sqrt{n})$. We provide an algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible competitive ratio is $\tildeΘ(n^{2/3})$. Furthermore, we extend our results to the general setting where the optimal algorithm is allowed $k$ queries and our algorithm is allowed $αk$ queries for $α\geq 1$. We present a randomized non-adaptive algorithm and matching lower bound (up to polylogarithmic factors) showing that the best possible expected competitive ratio for non-adaptive algorithms is the following surprisingly complex bound: $$ \tildeΘ\left( \min\left\{ \frac{n}{αk}, \max\left( \sqrt{\frac{n}α}, \frac{n^{2/3}}{αk^{1/3}} \right) \right\} \right). $$

0.23

Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation

cs.DS ·2026-09-10 ·Tomohiro Koana, Soh Kumabe
similarity 0.69
Abstract

Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.

0.16

A Sublogarithmic Competitive Algorithm for Online Graph Exploration

cs.DS ·2026-11-10 ·Max Klimm
similarity 0.69
Abstract

In online graph exploration, an agent must visit every vertex of an unknown weighted graph and return to its start, learning the incident edges at each vertex it visits. On $n$-vertex graphs, the best known competitive ratio has been $O(\log n)$, achieved by several algorithms, among them the hierarchical depth-first search of Megow, Mehlhorn, and Schweitzer. We give an algorithm with competitive ratio ${(2+o(1))}\ln n/\ln\ln n$ for known~$n$. Like hierarchical depth-first search, it groups the edges into geometric weight classes and searches depth-first between components of lighter edges. Unlike it, the agent tours each component along a minimum spanning tree for the original weights, so only crossings between components pay for rounding, and the base $b$ of the weight class can grow with~$n$. The leading constant $2$ is tight for our choice of base. Without knowing $n$, restarts with increasing size guesses give upper bounds with leading constant $4$ for a fixed schedule and $2$ in expectation for a randomly shifted schedule. If the weights lie in a known range $[1,2^k]$ with $k\ge4$, choosing $b=k/\log_2 k$ gives a competitive ratio of $O(k/\log k)$ without knowing $n$.

0.25