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 measuresexpand
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.
Arbitrary weighted graphs
standard settingverifiedThe question of Kalyanasundaram and Pruhs: the competitive ratio is between 4 and \(O(\log n)\), and whether it is constant is open.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Knowledge of the graph: nothing 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.
- Excluded minors: any graph
- \(G\) is any connected graph.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- deterministic algorithms; the adversary builds the graph as the agent explores it
- holds on subcubic planar graphs (Theorem 1)
- holds even if the agent is told \(n\), if it learns only the identifiers and weights of the edges at a node and not the identifiers of the neighbours, and if the weights satisfy the triangle inequality: none of these changes the competitive ratio (Proposition 2, Corollary 5)
Results, in order of publication
Theorem 2 (Corollary 13c): Blocking with parameter \(\log n\). The same ratio as the nearest-neighbour rule of Rosenkrantz, Stearns and Lewis (1977) and hierarchical depth-first search of Megow, Mehlhorn and Schweitzer (2012), as reported; neither paper is in the bibliography.
Open questions
Is there a deterministic algorithm with a constant competitive ratio (Kalyanasundaram and Pruhs Kalyanasundaram & Pruhs 1994, as reported by Baligács 2026)?
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.
Does randomization lower the competitive ratio on general graphs? It does on cycles Baligács et al. 2026b.
Notes
The restrictions of Baligács 2026 (Proposition 2) also say what a sensible algorithm may not need: the identifiers of unvisited neighbours, knowledge of \(n\), degrees above 3 and weights that violate the triangle inequality do not change the ratio; they are lost when proving bounds that grow with \(n\). Theorem 3 of Baligács et al. 2026a rules out Blocking with any parameter as a constant-competitive algorithm. Bounds checked against the full texts (arXiv versions).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Known graph, weight estimates
Graphs excluding a fixed minor
Planar graphs
Weighted cycles
Weighted cycles, randomized agent
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.