Graph exploration by a single agent

The \(n^2\) upper bound is attributed by the authors to Michail and Spirakis. They also give \(O(n^{1.5}\mathrm{tw}^{1.5}\log n)\) for treewidth \(\mathrm{tw}\), \(O(n^{1.8}\log n)\) for planar and \(2n-2\) for cycles, and show inapproximability within \(O(n^{1-\varepsilon})\).

Parameterized by \(\sigma\), the number of classes of the 2-dimensional Weisfeiler–Leman colouring of the temporal graph (their \(q\)), \(1 \le \sigma \le n\); vertex-transitive and distance-regular underlying graphs have \(\sigma = 1\). The walk is computed deterministically in polynomial time, for a long enough lifetime (Theorem 1.1). Some instances need \(\Omega(n\log n)\) steps for constant \(\sigma\) and \(\Omega(\sigma n)\) for every \(\sigma\) (Theorem 1.3), so the bound is tight up to polylogarithmic factors. It improves an earlier bound in the number of automorphism orbits (at least \(\sigma\)), which needed superpolynomial computation, as reported by Kammer et al. 2026.

Corollary 1.3 (arXiv v1; their \(k\) is \(\mu\) here), for always-connected temporal graphs with enough snapshots, from any start node. It suffices that at most \(\mu\) edges of one fixed spanning tree of the underlying graph are missing in each snapshot (Theorem 1.1). The schedule is computed by a Las Vegas algorithm in expected polynomial time, and deterministically in polynomial time when \(\mu\) is constant (Theorem 1.2). It improves the \(O(\mu n\log n)\) of Erlebach and Spooner and is within a factor \(\mu\) of their \(\Omega(n\log\mu)\) lower bound, both as reported by Lahtin & Zamaraev 2027; for constant \(\mu\) exploration takes \(\Theta(n)\) steps.

Theorem 2 of the full version (arXiv v2). The underlying graph is divided into parts with few boundary nodes; each part is explored by a team of agents (Theorem 1, on always \(S\)-connected temporal graphs, in which every snapshot joins every node to some node of a fixed set \(S\)), and the team schedule is turned into one for a single agent. For small \(\mathrm{tw}\) it is below the \(O(n^{3/2}\sqrt{\mathrm{tw}\log n})\) of Bastide et al. 2025. Carnevale 2026 cites \(\mathrm{tw}^{11/2}\) for the brief announcement, which was not read.

Theorem 1.3 (arXiv v2), from every start node, for every always-connected temporal graph with \(n^2\) snapshots, where \(\overline{\Delta}\) (their \(D\)) is the average temporal maximum degree: the average over the nodes \(v\) of the largest degree of \(v\) in any snapshot. If every snapshot has maximum degree at most \(\Delta\) then \(\overline{\Delta} \le \Delta\), which gives \(O(n^{3/2}\sqrt{\Delta\log n})\) (Corollary 1.4), and \(O(n^{3/2}\sqrt{\log n})\) for constant \(\Delta\) against the \(O(n^{7/4})\) of Erlebach, Kammer, Luo, Sajenko and Spooner. An underlying graph with \(m\) edges has \(\overline{\Delta} \le 2m/n\) (Corollary 1.5, stated for average degree), which gives \(O(n\sqrt{m\log n})\): \(O(n^{3/2}\sqrt{\log n})\) for planar underlying graphs and \(O(n^{3/2}\sqrt{\mathrm{tw}\log n})\) for treewidth \(\mathrm{tw}\), against \(O(n^{1.8}\log n)\) and \(O(n^{1.5}\mathrm{tw}^{1.5}\log n)\) Erlebach et al. 2021 and \(O(n^{7/4}\log n)\) and \(O(\mathrm{tw}\,n^{3/2}\log n)\) by Adamson, Gusev, Malyshev and Zamaraev, the last three as reported by Bastide et al. 2025. The bound is below \(n^2\) when \(\overline{\Delta} = o(n/\log n)\). The key lemma: any set \(X\) of nodes contains two nodes joined by a temporal walk within \(2\overline{\Delta}n/|X|+1\) steps (Lemma 1.8); in each block of \(n\) steps a walk then visits about \(\sqrt{|X|/(\overline{\Delta}\log|X|)}\) of the \(|X|\) nodes not yet visited (Lemma 3.2). The authors state, without a detailed proof, that the walk can be computed in polynomial time. Preprint.