CS Paper Radar

A Sublogarithmic Competitive Algorithm for Online Graph Exploration

Max Klimm

cs.DS ·submitted 2026-11-10 21:31 UTC · v1

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$.

Closest papers

Nearest neighbours by meaning across the whole index.

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.85
Abstract

We study the online graph exploration problem, in which an agent must visit every vertex of an initially unknown weighted graph on $n$ vertices and return to its starting vertex. In this model, a vertex's incident edges and their weights are revealed when it is first visited. Despite extensive research, the best known competitive guarantee for general graphs had remained $\mathcal{O}(\log n)$, a bound already established in 1977 for the greedy TSP heuristic Nearest Neighbor. Subsequent approaches, including hierarchical depth-first search (hDFS) and Blocking, achieve better guarantees on restricted graph classes but have logarithmic or worse competitive ratios on general graphs. This raises the question of whether the logarithmic barrier is inherent and Nearest Neighbor is asymptotically optimal. We answer this question in the negative by giving an $\mathcal{O}(\log n/\log \log n)$-competitive algorithm. Our algorithm is a slight modification of hDFS, and we establish its competitive guarantee with a surprisingly short proof.

0.22

Polylogarithmic Collective Tree Exploration

cs.DS ·2026-09-22 ·Romain Cosson, Laurent Massoulié
similarity 0.72
Abstract

We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O(\log^2 k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.

0.29

Collective Tree Exploration with Predictions

cs.DS cs.MA ·2026-11-12 ·Romain Cosson, Yichen Huang, Michael Mitzenmacher, Ali Vakilian
benchmark similarity 0.71
Abstract

We study collective tree exploration with subtree-size predictions. In this problem, a team of $k$ mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex $u$ is discovered, the team receives a prediction $\hat n_u$ of the number of nodes $n_u$ in the subtree rooted at $u$. We provide algorithmic guarantees under two error measures: the maximum error $E=\max_u|\widehat n_u-n_u|$ and the multiplicative distortion $μ= (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u)$. For the maximum error, we present a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in $O(\text{OPT}+E)$ rounds, where $\text{OPT} = Θ(n/k+D)$ is the offline benchmark, and we show that there is no deterministic algorithm that admits an $O(\text{OPT})+o(E)$ guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in $\widetilde O(\min\{ \sqrtμ\log k, μ\log\log k+μ^{1.5} \})$, where the $\widetilde O(\cdot)$ may hide logarithmic factors in $μ$.

0.16

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

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.69
Abstract · 32 pages, 12 figures

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)$.

0.25

Online Survivable Network Design with Arbitrarily Small Connectivity Loss

cs.DS ·2026-11-12 ·MohammadTaghi Hajiaghayi, Saeed Seddighin
similarity 0.67
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

The Tight Competitive Ratio of Greedy for Online Steiner Forest

cs.DS ·2026-10-29 ·Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade
theory similarity 0.66
Abstract

The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair. The natural greedy algorithm connects each terminal pair by a shortest path after making all previously purchased edges free. Awerbuch, Azar, and Bartal (SODA 1996) proved that this algorithm is $O(log^2 k)$-competitive and conjectured an $O(log k)$ bound, where $k$ is the number of terminal pairs. Bamas, Drygala, and Maggiori (SODA 2022) obtained an $O(\log \NumPairs\log\log \NumPairs)$ bound for greedy on a restricted class of inputs, leaving the general case open. In this paper, we resolve the competitive ratio of the greedy algorithm for online Steiner Forest, proving that it is tightly $Θ(log(k) log log(k))$. Specifically, we establish an $O(log(k) log log(k))$ upper bound for arbitrary instances and construct a matching $Ω(log(k) log log(k))$ lower bound. Our results refute the $O(log k)$ conjecture of Awerbuch, Azar, and Bartal and establish a tight $Θ(log log k)$ separation between the greedy algorithm and the best possible online algorithm for Steiner Forest.

0.23

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.65
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