Algorithmic and Structural Problems in Planted-Tree Detection

Definitions and mathematical statement

The supplied record concerns three questions about planted-tree detection. It does not specify the underlying probability model, so the questions below retain unresolved parameters rather than impose a particular model.

For a positive integer size parameter $n\to\infty$, a nonnegative tree-size function $k(n)$ satisfies $k(n)=O(\log n)$ if there exist constants $C>0$ and $n_0$ such that $k(n)\le C\log n$ for every $n\ge n_0$. The record does not specify whether tree size counts vertices or edges. It uses the product $pn$, described in the supplied background as mean degree, without defining the graph model or the parameter $p$. Accordingly, that interpretation cannot be made into an exact model assumption from this record alone.

1. Determine the detection threshold for planted $d$-ary trees, as requested by the curated statement. The original excerpt asks only, "What about d-ary trees?" Neither the tree family nor the threshold parameter is specified. In particular, the record does not say whether $d$ is fixed or depends on $n$, whether trees are rooted, whether every nonleaf has exactly $d$ children or vertices have at most $d$ children, or which tree sizes or heights are considered.
2. Under the stated condition $pn<1.1$, can an unknown random tree of size $O(\log n)$ be detected? The distribution of the tree, the information available to the observer, the planting mechanism, and the required detection success are unspecified. The bound $O(\log n)$ supplies only an upper growth bound; it does not determine the size sequence or a quantifier over such sequences. The record also does not state whether the question concerns every admissible sequence of $p$ satisfying this inequality or some such sequence.
3. Can the method called the hairy-path test in the source be performed in polynomial time? Polynomial time would require a running-time bound polynomial in a specified input length. The supplied excerpt does not define the test, its inputs, its parameter regime, its computational model, or the statistical guarantee that an implementation must retain.

A complete detection statement requires the null and planted probability laws, the observed data, and a success criterion, including its asymptotic quantifiers. None is supplied here. Consequently, these are qualified research questions rather than fully specified mathematical conjectures; no particular detection criterion or probability model is asserted.

Short English statement

The record asks about detection thresholds for planted $d$-ary trees, detecting an unknown random tree of size $O(\log n)$ when $pn<1.1$, and implementing the hairy-path test in polynomial time. The probability model, tree distribution, detection guarantee, and test definition are missing, so a fully quantified formulation requires further source context.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30006396$, titled Algorithmic and Structural Problems in Planted-Tree Detection; source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the registry lists proposed year 2025.
• Supplied source citation: Combinatorics, Probability and Computing (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/42, pp. 2243--2322. https://doi.org/10.4171/owr/2025/42. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Oberwolfach Report 42 2025. https://ems.press/content/serial-article-files/52246.
• Supplied literature source: Planting Trees in Graphs and Finding Them Back. https://arxiv.org/abs/1811.01800. No authors or more specific passage are supplied in the record.
• Literature assessment dated 2026-08-22: the supplied curation labels the three questions open and says they remain open in the current report. This is supplied dated curation, not an independently verified literature assessment. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified, explaining that only formula delimiters, notation, grammar, and typography were repaired and that mathematical content and scope were preserved. This supplied editorial label does not establish mathematical correctness or resolve missing hypotheses.