Testing Full Quartet Consistency: Adaptive Reconstruction, Random Verification, and Constant-Query Testability

Abstract

We study dense property testing for full systems of resolved quartet topologies on $n$ taxa: determining whether a system is induced by a phylogenetic tree or is $\epsilon$-far from every tree-induced system. Our main result is an explicit polynomial-time adaptive one-sided-error tester. It reconstructs a candidate tree through anchored quartet queries and verifies the candidate using uniformly random quartet queries. With error probability $\hat{I}´$, it uses $O\left(n\log n+{\epsilon }^{-1}\log (1/\hat{I}´)\right)$ queries. We also give a non-adaptive cached-anchor variant using $\left(\genfrac{}{}{0ex}{}{n-1}{3}\right)+O\left({\epsilon }^{-1}\log (1/\hat{I}´)\right)$ queries. Both improve the previous explicit $O(n^3/\epsilon )$ query bound. Since the input contains $\left(\genfrac{}{}{0ex}{}{n}{4}\right)=\hat{I}˜(n^4)$ quartet entries, both testers use $o\left(\left(\genfrac{}{}{0ex}{}{n}{4}\right)\right)$ queries for fixed~$\epsilon$ and~$\hat{I}´$. We additionally encode full quartet systems, equivariantly under relabeling, as directed, three-colored $4$-ary structures. Hereditary directed-hypergraph testing then yields an $n$-independent one-sided-error tester, although its dependence on $\epsilon$ is quantitatively impractical. Finally, we prove lower bounds. In ordinary property testing, every adaptive randomized tester, even with two-sided error, requires asymptotically at least $\ln ((1-\hat{I}´)/\hat{I}´)/\ln (1/(1-\epsilon ))$ queries as $n\to \infty$. Every one-sided-error tester requires $\ln (1/\hat{I}´)/\ln (1/(1-\epsilon ))$ queries, matching the random-verification term up to rounding. For the stronger reconstruct-or-reject task, our upper bounds are optimal up to constant factors: the adaptive and non-adaptive complexities are $\hat{I}˜(n\log n+{\epsilon }^{-1}\log (1/\hat{I}´))$ and $\hat{I}˜(n^3+{\epsilon }^{-1}\log (1/\hat{I}´))$, respectively.

Submitted to a journal for publication