cs.DSNov 12, 2026

Collective Tree Exploration with Predictions

Authors: Romain Cosson, Yichen Huang, Michael Mitzenmacher, Ali Vakilian

Organizations: Computer Science Department, Courant Institute, New York University. · John A. Paulson School of Engineering and Applied Science, Harvard University. · Rutgers University.

Abstract

We study collective tree exploration with subtree-size predictions. In this problem, a team of kk mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex uu is discovered, the team receives a prediction n^u\hat n_u of the number of nodes nun_u in the subtree rooted at uu. We provide algorithmic guarantees under two error measures: the maximum error E=max⁡u∣n^u−nu∣E=\max_u|\widehat n_u-n_u| and the multiplicative distortion μ=(max⁡un^u/nu)(max⁡unu/n^u)μ= (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u). For the maximum error, we present a deterministic algorithm that explores any tree with nn nodes and depth DD in O(OPT+E)O(\text{OPT}+E) rounds, where OPT=Θ(n/k+D)\text{OPT} = Θ(n/k+D) is the offline benchmark, and we show that there is no deterministic algorithm that admits an O(OPT)+o(E)O(\text{OPT})+o(E) guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in O~(min⁡{μlog⁡k,μlog⁡log⁡k+μ1.5})\widetilde O(\min\{ \sqrtμ\log k, μ\log\log k+μ^{1.5} \}), where the O~(⋅)\widetilde O(\cdot) may hide logarithmic factors in μμ.

Figures & tables

Explore similar work

CardsList
  1. Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

    Dec 11, 2024Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2Multi-Agent Path Finding

  2. Robust and Learned Online Matching in Growing Trees

    Sep 30, 2026Marek Gałązka, Hanna WdowickaAdaptive Learning

  3. Learning Augmented Exact Exponential Algorithms

    Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms