Mobility Matters
Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Online exploration of weighted graphs

Online exploration of weighted graphs

One agent must visit every node of an unknown weighted graph and return to its start node, learning the edges at each node only when it gets there; how close to a shortest tour can its cost be?

Problem statement and measurescollapse
12cost 0s112cost 1s11102cost 2s11102cost 3s11102cost 4s111012cost 6s1110112cost 7s1110112cost 8s1110112cost 9s1110112cost 10s1110112cost 12sAAStart at s: the agent sees only the two edges at s; it takes the lighter oneb = 10 > √3·2 + 2 ≈ 5.5: the edge ahead is too heavy, so turn backIt crossed the other boundary edge; at q1, b = 1 ≤ √3·2 + 12, so go onEvery node visited: return to s along a shortest pathFinal: cost 12, which equals the shortest tour here
Online exploration of a cycle by HeavyTest Baligács et al. 2026b: the agent learns an edge and its weight only when it reaches one of its ends (weights are shown once known; visited nodes are green). The explored part is a path with a boundary edge at each end. With \(b\) the weight of the edge ahead, \(a\) the distance back to \(s\) and \(d\) the distance from \(s\) to the far end of the other boundary edge, the agent goes on if \(b \le \sqrt3\,a + d\) and otherwise turns back, crossing the other boundary edge. Here it refuses the edge of weight 10, which a shortest tour also avoids, and its cost equals the optimum of 12. In the worst case the ratio is \((1+\sqrt3)/2\), the best possible for a deterministic agent on cycles Miyazaki et al. 2009. One frame per edge crossed.

A single agent starts at a node \(s\) of an unknown connected undirected graph \(G=(V,E)\) with \(n\) nodes; every edge \(e\) has a non-negative weight \(\mathrm{wt}(e)\). Nodes and edges carry distinct identifiers. When the agent visits a node for the first time it learns the identifiers of its neighbours and the identifiers and weights of the edges to them. Crossing an edge has a cost equal to its weight. The agent must visit every node and return to the start node \(s\); its walk is then a tour. An algorithm is measured by its competitive ratio: the supremum, over all graphs and start nodes, of the cost of its tour divided by \(\mathrm{OPT}\), the cost of a shortest closed walk that visits every node (an optimal travelling-salesperson tour of \(G\)); for a randomized algorithm the expected cost is used. Unless a setting says otherwise the algorithm is deterministic, the graph is arbitrary and nothing about it is known in advance. Memory and computation are unbounded: the question is what the lack of information costs. Since \(\mathrm{OPT}\) lies between the weight of a minimum spanning tree and twice that weight, a depth-first search that ignores the weights already explores trees optimally, and the difficulty lies in the cycles.

Measures: Competitive ratio, worst-case cost of the agent's tour divided by OPT, the cost of a shortest tour.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a courier in a city without a map. At each crossing the courier sees the roads that leave it, where they lead and how long they are, and must visit every crossing and come home, walking as little as possible. The city is a graph: crossings are nodes and roads are edges, and each edge has a weight \(\ge 0\), its length. The courier is an agent that starts at the start node \(s\). Nodes and edges have distinct names. When the agent first visits a node, it learns the names of its neighbours and the weights of the edges to them. Crossing an edge costs its weight, and the cost of a walk is the total. The agent must visit every node and return to \(s\), and its walk is then a tour. We compare it with \(\mathrm{OPT}\), the cost of a shortest tour, which someone who knew the graph could take. The competitive ratio is the worst case, over all graphs and start nodes, of the agent's cost divided by \(\mathrm{OPT}\). In the standard version the graph is arbitrary and the agent is deterministic: it tosses no coins. Memory and computation are unlimited, so the only difficulty is the missing information.

1AlgorithmOn a cycle: go on, or turn back Weighted cycles → Baligács et al. 2026b

Suppose the graph is a cycle. The explored part is then always a path, with a boundary edge at each end: an edge from a visited node to a node not yet visited. The agent stands at one end.

  1. First cross the lighter of the two edges at \(s\).
  2. Let \(b\) be the weight of the boundary edge ahead, \(a\) the distance back to \(s\), and \(d\) the distance from \(s\) to the far end of the other boundary edge. Going on costs \(b\), and turning back to cross the other boundary edge costs \(a + d\).
  3. Go on if \(b \le \sqrt3\, a + d\). Otherwise turn back and cross the other boundary edge.
  4. When every node has been visited, return to \(s\) along a shortest path.
Why it works and what it costs. The rule is HeavyTest of Baligács et al. 2026b. It weighs two risks: crossing a heavy edge that a shortest tour would avoid, and walking all the way back for an edge that a shortest tour would use. Their proof shows that the factor \(\sqrt3\) gives the competitive ratio \((1+\sqrt3)/2 \approx 1.366\). No deterministic agent does better on cycles Miyazaki et al. 2009, whose algorithm reached the same ratio first with a rule that also uses the cost spent so far. An agent that tosses coins does better on cycles, at most \(1.3144\).

Why it matters. It isolates the basic dilemma of online exploration, whether to pay for the edge in front or go back, and solves it exactly.

2AlgorithmDepth-first search, and why weights make it hard Arbitrary weighted graphs → Miyazaki et al. 2009

Depth-first search ignores the weights: go to an unvisited neighbour while there is one, otherwise go back the way you came, and stop when you are back at \(s\) with nothing left to try. The edges it uses to reach new nodes form a tree that contains every node, and it crosses each of them exactly twice.

Why it works and what it costs. On a tree a shortest tour also crosses every edge twice, so depth-first search is optimal there. If every edge has weight 1, depth-first search costs \(2(n-1)\), while any tour crosses at least \(n\) edges, so the ratio is below 2 (Theorem 4 of Miyazaki et al. 2009). With weights it can be arbitrarily bad. On a cycle it may cross a very heavy edge twice, where a shortest tour goes out and back on the light side. A shortest tour costs between the weight of a minimum spanning tree (the lightest set of edges that connects all nodes) and twice that. The challenge is to explore at a cost close to that weight without knowing the graph.

Why it matters. It shows where the difficulty lies: not in visiting everything, but in avoiding heavy edges that are not yet known to be avoidable.

3AlgorithmBlocking: depth-first search that waits for lighter edges Graphs excluding a fixed minor → Baligács et al. 2026a

Fix a number \(\chi > 0\). A boundary edge of weight \(w\) is blocked if some lighter boundary edge leads to an unvisited node at distance at most \((1+\chi)\,w\) from the visited end of the first edge, along visited nodes.

  1. Run depth-first search, but never cross a blocked edge.
  2. Whenever a blocked edge becomes unblocked, walk to it, cross it, and start a new depth-first search from there.
  3. Stop when every node has been visited, and return to \(s\).
Why it works and what it costs. Each boundary edge that the agent crosses pays for its own trip, at most \(2(\chi+2)\) times its weight (Observation 6). So the question is how heavy these edges are together compared with a minimum spanning tree. Baligács, Disser, Heinrich and Schweitzer show that they behave like a light spanner: a set of edges that keeps every distance within a factor \(1+\chi\) and weighs at most a constant times a minimum spanning tree. Every class of graphs that excludes a fixed minor, for example planar graphs, has light spanners, so there Blocking is constant-competitive Baligács et al. 2026a. On planar graphs the ratio is 16, the bound of Kalyanasundaram and Pruhs Kalyanasundaram & Pruhs 1994, as reported by Baligács et al. 2026a. On all graphs, with \(\chi = \log n\), it is \(O(\log n)\)-competitive, but no choice of \(\chi\) makes it constant. Whether any algorithm is constant-competitive on all graphs is open; no deterministic algorithm is better than 4 Baligács 2026.

Why it matters. It is the main tool for the central open question of Kalyanasundaram and Pruhs, and it ties online exploration to spanners, a basic object of graph theory.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Competitive ratio
Arbitrary weighted graphs standard
The question of Kalyanasundaram and Pruhs: the competitive ratio is between 4 and \(O(\log n)\), and whether it is constant is open.
polynomial gap \(O(\log n)\) vs \(4\) online graph revelation
Known graph, weight estimates
If the graph is known and every weight is known up to a factor \(\vartheta \le 2\), following a shortest tour for the lower estimates is \(\vartheta\)-competitive, and nothing does better.
polynomial gap \(\vartheta\) vs \(\min(\vartheta, 2)\) online graph revelation
Complete graphs, uniform weight estimates
On complete graphs whose weights all lie in \([1, \vartheta]\) with \(\vartheta < 2\), recomputing the best walk after each step is \(\tfrac{1+\vartheta}{2}\)-competitive, which is optimal.
tight \(\tfrac{1+\vartheta}{2}\) vs \(\tfrac{1+\vartheta}{2}\) online graph revelation
Graphs excluding a fixed minor
Blocking is constant-competitive on every class of graphs that excludes a fixed minor, through light spanners.
tight \(O(1)\) vs \(4\) online graph revelation
Planar graphs
The first class with a constant ratio: 16-competitive since 1993, against a lower bound of 4 that holds already on planar graphs.
tight \(16\) vs \(4\) online graph revelation
Weighted cycles
On a cycle the deterministic competitive ratio is exactly \((1+\sqrt3)/2 \approx 1.366\).
tight \(\tfrac{1+\sqrt3}{2}\) vs \(\tfrac{1+\sqrt3}{2}\) online graph revelation
Weighted cycles, randomized agent
A randomized agent beats the deterministic ratio on cycles: at most \(1.3144\), against a lower bound of \(1.1155\).
tight \(1+\tfrac{(3-\sqrt2)^2}{8}\) vs \(1+\tfrac{\sqrt2}{8+3\sqrt2}\) online graph revelation

Open questions 8

Arbitrary weighted graphs

  1. Is there a deterministic algorithm with a constant competitive ratio (Kalyanasundaram and Pruhs Kalyanasundaram & Pruhs 1994, as reported by Baligács 2026)?
  2. Is there an \(o(\log n)\)-competitive algorithm? Blocking with parameter \(\chi\) (their \(\delta\)) is \(\Omega(\log n)\)-competitive for \(\chi = o(\log n/\log\log n)\) and for \(\chi = \Omega(\log n)\), and \(\Omega(\log n/\log\log n)\)-competitive for every \(\chi\); the range in between is open Baligács et al. 2026a.
  3. Does randomization lower the competitive ratio on general graphs? It does on cycles Baligács et al. 2026b.

Known graph, weight estimates

  1. Does every graph admit a \(\tfrac{1+\vartheta}{2}\)-competitive algorithm when all weights are announced in the same interval \([1, \vartheta]\) with \(\vartheta \le 2\)? Conjectured by Gehnen et al. 2025.

Graphs excluding a fixed minor

  1. How does the best constant depend on the excluded minor \(H\), and on the genus for graphs of bounded genus Baligács et al. 2026a?

Planar graphs

  1. Close 4 against 16 on planar graphs.

Weighted cycles, randomized agent

  1. Determine the randomized competitive ratio on cycles: \(1.1155\) against \(1.3144\) Baligács et al. 2026b.
  2. Must an optimal randomized algorithm on cycles be forward-greedy Baligács et al. 2026b?

What the community started looking at

Kalyanasundaram and Pruhs posed the problem, asked whether some algorithm has a constant competitive ratio and gave one for planar graphs Kalyanasundaram & Pruhs 1994, as reported by Baligács 2026 and Baligács et al. 2026a. The question is still open. The nearest-neighbour rule (always go to the closest unvisited node), analysed as a travelling-salesperson heuristic by Rosenkrantz, Stearns and Lewis in 1977, is \(\Theta(\log n)\)-competitive, and no algorithm is known to do better on all graphs, as reported by Baligács 2026. Megow, Mehlhorn and Schweitzer (2012) revisited the planar algorithm as Blocking and extended it to graphs of bounded genus (as reported by Baligács et al. 2026a); Baligács, Disser, Heinrich and Schweitzer extended it to every class that excludes a fixed minor, by relating Blocking to light spanners Baligács et al. 2026a. Lower bounds for deterministic algorithms rose from 2, which holds on unweighted planar graphs and is matched there by depth-first search Miyazaki et al. 2009, through 2.5 (Dobrev, Královič and Markou, 2012, as reported by Baligács 2026) and \(10/3\), which also holds on planar graphs Birx et al. 2021, to 4 Baligács 2026. On cycles the deterministic ratio is exactly \((1+\sqrt3)/2\) Miyazaki et al. 2009, and randomization was first shown to help there in 2026 Baligács et al. 2026b. Gehnen, Klasing and Naquin introduced a semi-online version in which the graph is known and only the weights are uncertain Gehnen et al. 2025.

Variant of Graph exploration by a single agent

The same task for one agent (visit every node and return to the start node), in the tradition of online algorithms: nodes carry identifiers, edges carry weights, memory and computation are unbounded, and an algorithm is judged by its competitive ratio against a shortest tour rather than by its memory. Results do not transfer in either direction without care: the parent counts moves on anonymous unweighted graphs, this problem counts weight on labelled weighted graphs. The setting directed-labelled of the parent Deng & Papadimitriou 1999 is the analogue for unweighted directed graphs.

Related problems

Collaborative exploration: Collective tree exploration also measures algorithms by their competitive ratio against the offline optimum, but for \(k\) agents on unweighted trees and for time; here one agent explores a weighted graph and its cost is compared with a shortest tour.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Brandt et al. 2020a Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs. Tadpole graphs (a cycle with a path attached): the greedy nearest-neighbour rule is 2-competitive for any non-negative weights, matching the lower bound \(2 - \varepsilon\) obtained from the construction of Miyazaki et al. 2009; also advice complexity on cycles and tadpoles. Abstract read.
  • van den Akker et al. 2024 Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs. Online exploration by 2 to 4 agents that share what they see, on cycles and tadpole graphs, for the time and for the longest walk: optimal ratios in several cases (1 with two agents on cycles for the longest walk). Abstract read.
  • Böckenhauer et al. 2018 The Graph Exploration Problem with Advice. Advice complexity of online exploration in the fixed graph scenario (directed or undirected, cyclic or not, unit or individual costs): how many bits of advice an optimal tour needs. A preprint; abstract read.
  • Böckenhauer et al. 2016 Online Exploration of Rectangular Grids. The agent knows the graph but sees edge weights (1 or \(k\)) only at their ends: lower bound \(11/9\) and a 4-competitive algorithm on ladders; greedy has a linear ratio on directed ladders and grids. Abstract read.

All settings

The assumption tree (7 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Competitive ratio); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Node identifiers › Randomness › Knowledge of the graph › Excluded minors › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge of the graph

0nothing known in advance1the graph is known, each weight only up to an interval

Gehnen, Klasing and Naquin introduced weight estimates to model a traveller who knows the street map but learns the actual travel time of a road only on reaching it; the setting lies between the offline travelling-salesperson problem and online exploration Gehnen et al. 2025. With \(\vartheta = 1\) it is the offline problem; as \(\vartheta\) grows it approaches online exploration, whose lower bounds apply once the intervals are wide enough (Section 2 of Gehnen et al. 2025).

Formal definitions
0nothing known
The agent knows nothing about \(G\) before it starts; the edges at a node and their weights are revealed when the agent first visits the node.
1weight estimates
The agent is given \(G\) and, for every edge \(e\), an interval \([\mathrm{wt}^-(e), \mathrm{wt}^+(e)]\) that contains \(\mathrm{wt}(e)\), with \(\mathrm{wt}^+(e) \le \vartheta\,\mathrm{wt}^-(e)\) for a factor \(\vartheta \ge 1\) (their \(\alpha\)); the exact weight of \(e\) is revealed when the agent visits an end of \(e\) Gehnen et al. 2025.

Excluded minors

0any connected graph1excludes a fixed graph \(H\) as a minor2planar

Restricting the graph class is how constant competitive ratios have been obtained: Kalyanasundaram and Pruhs for planar graphs Kalyanasundaram & Pruhs 1994, Megow, Mehlhorn and Schweitzer for graphs of bounded genus (2012, as reported by Baligács et al. 2026a), and Baligács, Disser, Heinrich and Schweitzer for every class with a forbidden minor, which they show subsumes all classes previously known to admit a ratio of \(o(\log n)\) Baligács et al. 2026a.

Formal definitions
0any graph
\(G\) is any connected graph.
1\(H\)-minor-free
For a fixed graph \(H\), no graph obtained from \(G\) by deleting nodes and edges and contracting edges is isomorphic to \(H\). Graphs of bounded genus and of bounded treewidth are such classes; bounds may depend on \(H\).
2planar
\(G\) can be drawn in the plane without crossing edges; equivalently it has neither \(K_5\) nor \(K_{3,3}\) as a minor.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.