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.
Graphs excluding a fixed minor
verifiedBlocking is constant-competitive on every class of graphs that excludes a fixed minor, through light spanners.
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: \(H\)-minor-free
- For a fixed graph \(H\), no graph obtained from \(G\) by deleting nodes and edges and contracting edges is isomorphic to \(H\). Graphs of bounded genus and of bounded treewidth are such classes; bounds may depend on \(H\).
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- planar bound: holds for every non-planar excluded minor \(H\), since planar graphs have only planar minors
- deterministic algorithms
Results, in order of publication
Introductory and current best (Theorem 1; Corollaries 11 and 13b). Blocking with parameter \(\chi\) (their \(\delta\)) is \(2(\chi+2)\Upsilon\)-competitive on every class closed under subgraphs in which every graph has a \((1+\chi)\)-spanner of weight at most \(\Upsilon\) times that of a minimum spanning tree (Theorem 9), and \(H\)-minor-free graphs have such spanners with \(\Upsilon\) depending on \(H\) and \(\chi\). On graphs of genus at most \(\mathfrak g\) the ratio is \(16(1+\tfrac23\mathfrak g)\) (Corollary 13a), slightly better than \(16(1+2\mathfrak g)\) of Megow, Mehlhorn and Schweitzer, as reported.
Open questions
How does the best constant depend on the excluded minor \(H\), and on the genus for graphs of bounded genus Baligács et al. 2026a?
Notes
Baligács, Disser, Heinrich and Schweitzer run the connection both ways: the exploration analysis also gives greedy \((1+\varepsilon)\)-spanners of lightness at most \((1+\tfrac2\varepsilon)(1+\tfrac{2\mathfrak g}{1+\varepsilon})\) on graphs of genus \(\mathfrak g\) (Theorem 4), tight for planar graphs. They suggest that a non-constant lower bound for exploration may require dense graphs of high girth or expanders (Section 4). Checked against the full text (arXiv v1, 2023); the cited version is the JCSS article.
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.