Strong Refutation of Ordering, Phylogenetic, and Ordinary CSPs, and New Satisfiability and Refutation Thresholds for Triplet and Quartet Reconstruction

Abstract

We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, $n$ variables are assigned to leaves of a tree, so as to satisfy $m$ constraints, specifying evolutionary relationships. Two canonical $NP$-hard optimization problems are Triplet and Quartet Reconstruction, where the input consists of triplets $xy|z$ or quartets $xy|zw$, and the goal is to find a tree $T^{\ast }$ maximizing agreement with constraints. Our main results are (as density $\lambda =m/n$ increases): 1. We show the existence and precisely locate the sharp threshold ${\lambda }^{\ast }\approx 1.2277$ for Triplets (via closed-form solution). To the best of our knowledge, this is the first sharp threshold for the broad family of Phylogenetic CSPs. Moreover, we give a lower and upper bound for Quartets. 2. We provide strong refutation algorithms that certify that $val(T^{\ast })\le 5/9+\epsilon$, where $val(T^{\ast })$ is the fraction of constraints satisfied by the (unknown) optimal tree. For triplets, our algorithm succeeds w.h.p if $m=\Omega (n)$, and for quartets if $m=\Omega (n^{3/2})$. 3. We obtain strongest possible refutations at slightly larger densities (for triplets $m=O(n^{3/2}{\log }^{3}n)$, for quartets $m=O(n^2)$): we certify that $T^{\ast }$ is no better than a random assignment, i.e., $val(T^{\ast })\le 1/3+\epsilon$. In fact, we obtain strongest possible refutations for finite-alphabet CSPs with or without negations. Our refutations above are instantiations of our general theorem that applies more broadly to Phylogenetic and Ordering CSPs (and all CSPs failing to support $t$-wise independence), and generalizes the current algorithmic frontier on refuting random CSPs~\citep{allen2015refute}. A crucial difference here, unlike Boolean CSPs, is that there are no negated variables, so prior works relying on negations -- a source of randomness -- do not apply.

arXiv commentAbstract shortened for arxiv