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.
Weighted cycles, randomized agent
verifiedA randomized agent beats the deterministic ratio on cycles: at most \(1.3144\), against a lower bound of \(1.1155\).
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: private coins
- Each agent additionally has access to independent fair coin flips; guarantees hold with probability 1, in expectation, or with high probability, as stated per result.
- 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: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
What is known
- any randomized algorithm, against an adversary that fixes the cycle in advance (oblivious)
- Yao's principle on three cycles of four nodes that look the same from the start node (Theorem 3)
- only for forward-greedy algorithms: those that cross the edge ahead whenever its weight \(b\) is at most \(a + d\), the cost of turning back to the unvisited end of the other boundary edge; RandHeavyTest is one (Theorem 4)
Results, in order of publication
Introductory and current best (Theorem 2), about \(1.3144\): RandHeavyTest with parameter \(1/2\) crosses the edge ahead when \(b \le \tfrac32 a + d\) and otherwise with probability \(a/(2(b-d-a))\). The proof is a supermartingale argument with a stopping time.
Open questions
Determine the randomized competitive ratio on cycles: \(1.1155\) against \(1.3144\) Baligács et al. 2026b.
Must an optimal randomized algorithm on cycles be forward-greedy Baligács et al. 2026b?
Notes
Baligács, Hązła and Volk give the first proof that randomization helps in online graph exploration; Miyazaki, Morimoto and Okabe, who settled deterministic algorithms on cycles, name randomized algorithms as future work Miyazaki et al. 2009. The revealed part of the graph depends on the agent's earlier random choices, which is what makes randomized exploration hard to analyse. Checked against the full text (arXiv v1, 2026), a preprint.
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.