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.
Planar graphs
draftThe first class with a constant ratio: 16-competitive since 1993, against a lower bound of 4 that holds already on planar graphs.
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: planar
- \(G\) can be drawn in the plane without crossing edges; equivalently it has neither \(K_5\) nor \(K_{3,3}\) as a minor.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- deterministic algorithms
- subcubic planar graphs (Theorem 1)
Results, in order of publication
Introductory and current best, as reported by Baligács et al. 2026a and Gehnen et al. 2025; not read. Corollary 13a of Baligács et al. 2026a with genus 0 recovers 16 for Blocking with parameter 2, through planar spanners of lightness \(1+2/\chi\).
Open questions
Close 4 against 16 on planar graphs.
Notes
Draft because the introductory paper was not read; the bound 16 was checked as a consequence of Corollary 10 of Baligács et al. 2026a.
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.