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

Dec 11, 2024

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

Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 33 and the communication range is 11.
Sep 30, 2026

Robust and Learned Online Matching in Growing Trees

We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret O(nlog⁡2n)O(\sqrt{n}\log^2 n), using O(n2log⁡n)O(n^2\log n) arithmetic operations and O(n)O(n) stored entries. The exact minimax rate remains open.
Jun 17, 2026

Learning Augmented Exact Exponential Algorithms

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.