Local Quartet Splits of a Binary Tree Infer All Quartet Splits Via One Dyadic Inference Rule

Abstract

A significant problem in phylogeny is to reconstruct a semilabelled binary tree from few valid quartet splits of it. It is well-known that every semilabelled binary tree is determined by its set of all valid quartet splits. Here we strengthen this result by showing that its local (i.e. small diameter) quartet splits infer by a dyadic inference rule all valid quartet splits, and hence determine the tree.  The results of the paper also present a polynomial time algorithm to recover the tree.