CS Paper Radar

Size-Independent Survival Bounds for Routing Without a Map

Krišjānis Petručeņa

cs.DS ·submitted 2026-11-17 21:47 UTC · v1
theory

Abstract

A walker, such as a packet carrying a secret share, must reach a known target in an unknown graph while avoiding a fixed set of fatal vertices (compromised relays in the packet interpretation). It learns a vertex's neighbours only on reaching that vertex safely, remembers its observations, and is promised a safe route. We prove that a randomised depth-first strategy guarantees a success probability depending only on the maximum degree and the number of fatal vertices, not on the size of the graph. Planarity is not required for this guarantee, and planar examples attain the bound at every sufficiently large graph size. At those sizes, when the degree cap is at least three, the guarantee is optimal among strict depth-first strategies. Whether strategies allowed to switch between unfinished branches can guarantee a larger worst-case survival probability remains open. For unknown trees and for graphs of maximum degree two, we determine the exact best worst-case success probability over all routing strategies. Explicit examples compare our strategy with random-priority frontier routing and ordinary random walks, showing how exploration order can prevent survival probability from declining as the graph grows.

Comment
38 pages, 11 figures. Follow-up to arXiv:2609.00893

Closest papers

Nearest neighbours by meaning across the whole index.

Random-Priority Frontier Routing: Tight $Θ(n^c)$ Bounds Against $c$-Node Cartels

cs.DS ·2026-09-01 ·Krišjānis Petručena
theory similarity 0.76
Abstract · 4 pages

We study path diversification in trusted-node networks, where sensitive material is relayed through intermediate nodes, some of which may be compromised. Our randomized routing rule assigns each vertex an independent random priority and repeatedly expands the highest-priority vertex on the global frontier of the explored region. Let $G$ have $n$ vertices, let $s,t$ be honest endpoints, and let $C$ be a set of $c$ compromised intermediate vertices, called a cartel, whose deletion leaves $s$ and $t$ connected. For every fixed $c$ and every fixed target probability $q\in(0,1)$, we prove that $Θ(n^c)$ independent executions are sufficient in the worst case for some route to avoid $C$ with probability at least $q$.

0.22

Sublogarithmic Online Graph Exploration

cs.DS cs.DM ·2026-11-10 ·Julia Baligacs
similarity 0.65
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

Safe Exploration of Arbitrary Dynamic Dangerous Networks

cs.DC ·2026-09-17 ·Caterina Feletti, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
theory similarity 0.65
Abstract

Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes.

0.05

Optimal (Randomized) Compact Routing Schemes

cs.DS cs.NI ·2026-11-03 ·Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty
hot direction similarity 0.65
Abstract

Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.

0.35

Blindfolded pursuit with delays of your choice

cs.GT ·2026-08-27 ·Torben Schürenberg, Maximilian J. Stahlberg
similarity 0.63
Abstract

We study pursuit-evasion games on graphs with a single pursuer and an invisible evader. The pursuer may assign integer travel times to the edges of the graph and specify a finite sequence of vertices to query, one per time step. The evader then chooses a walk over the same time horizon, aiming to elude all queries. With unit travel times, the setting in which the evader must move at every time step is known as the hunter and rabbit game, while the variant in which the evader can wait at a vertex can be phrased as a firefighting game: the vertices of a burning graph must be extinguished, and any vertex left burning reignites its neighbors. For both settings, we show that the power to choose travel times allows a single pursuer to succeed in polynomial time on any graph. This contrasts with unweighted graphs, where the number of hunters or firefighters needed can grow linearly in the number of vertices. If the evader, in addition to waiting, may start at an earlier time unknown to the pursuer, we show that the pursuer still wins on any graph given exponential time.

0.25

A Sublogarithmic Competitive Algorithm for Online Graph Exploration

cs.DS ·2026-11-10 ·Max Klimm
similarity 0.63
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

Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

cs.AI stat.MLcs.LG ·2026-09-30 ·Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz, Maxime Schwarzer, Tobias Huerten +1 more
theory similarity 0.62
Abstract

Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC~7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $Δ$ from optimal, and an $L$-layer graph neural network (GNN) read out at the deciding node is exactly an $L$-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(Δ)$ reproduces the RFC~7181 covering greedy, and at width $O(c_{\max}Δ)$ its metric-aware weighted analogue, inheriting the $(1+\lnΔ_2)$-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches $\text{cost}/\text{opt}=1.030\pm0.001$ against greedy's $1.138$, closing $79.1\%$ of the gap at $100\%$ coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to $1.344$, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on $200/200$ unit-cost instances, and on $40{,}308$ instances of real battalion mobility the frozen model closes $48\%$ of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.

0.23

A Low-Diameter Nash-Williams--Tutte Theorem

cs.DM math.COcs.DS ·2026-11-03 ·Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai, Ting-An Wu
theory similarity 0.61
Abstract

The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

0.29