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.
Known graph, weight estimates
verifiedIf 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.
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: weight 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: any graph
- \(G\) is any connected graph.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
The agent knows \(G\) and, for each edge, an interval that contains its weight, with ratio at most \(\vartheta\) between the ends; the weight is revealed when the agent reaches an end of the edge. In Gehnen et al. 2025 the agent must walk from \(s\) to a given node \(t \ne s\) through all nodes; the authors note that the bounds carry over to tours up to one edge.
What is known
- a recursive instance of paths whose weights are announced in \([1, \vartheta]\); the adversary reveals each weight when the agent arrives (Theorem 3 for \(\vartheta \le 2\); Remark 4 gives 2 for \(\vartheta \ge 2\))
Results, in order of publication
Introductory and current best (Theorem 5): compute a shortest walk for the lower ends of the intervals and follow it, ignoring the revealed weights.
Open questions
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.
Notes
Gehnen, Klasing and Naquin. Lower-bound constructions for online exploration hide the structure of the graph (dead ends), which is impossible here; they transfer only when the intervals are wide (Section 2 of Gehnen et al. 2025). Checked against the full text (arXiv v1, 2025); a LATIN 2026 version is cited by Baligács et al. 2026b and was not read.
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
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.