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
verifiedOn a cycle the deterministic competitive ratio is exactly \((1+\sqrt3)/2 \approx 1.366\).
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: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
What is known
- deterministic algorithms
- Theorem 1: no \(((1+\sqrt3)/2 - \varepsilon)\)-competitive algorithm, for every constant \(\varepsilon > 0\)
Results, in order of publication
Theorem 2, algorithm Dist: at each step the agent crosses the boundary edge ahead if and only if its weight is at most \(\sqrt3\) times the known distance to the unvisited end of the other boundary edge, minus the cost so far less the distance back to \(s\); otherwise it turns back. Its choices depend on the cost so far. Before it, Asahiro, Miyano, Miyazaki and Yoshimuta showed that the nearest-neighbour rule is \(3/2\)-competitive on cycles, against a lower bound of \(5/4\) (SOFSEM 2007), as reported by Miyazaki et al. 2009.
Theorem 1, algorithm HeavyTest: with \(b\) the weight of the boundary edge at the agent, \(a\) its distance back to \(s\) and \(d\) the distance from \(s\) to the unvisited end of the other boundary edge (so turning back costs \(a + d\)), cross the edge ahead if and only if \(b \le \sqrt3\,a + d\). It depends only on the current state, and its analysis is shorter.
Open questions
None recorded for this variant.
Notes
On a cycle the explored part is a path with two boundary edges, and the only decision is whether to continue or turn back; the difficulty is an edge heavier than all others together, which a shortest tour avoids. Trees are explored optimally by depth-first search Baligács et al. 2026b.
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
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.