level-$k$ network exists that is consistent with $R$, and if so to construct such a network.

As pointed out in [@simplicityAlgorithmica] it is possible to determine in polynomial time whether a given network is indeed consistent with a set of input triplets. Then, the proof of Lemma \[lem:core\] holds here almost entirely. The only significant difference concerns the adding of leaves to the lowest side: a not yet allocated leaf $x$ belongs on lowest side $s$ if and only if the triplet $s^{-}x|s^{+}$ is in the input.

We shall return to rooted triplets again later in the article.

From theory to practice: the importance of ST-sets {#sec:stsets}
==================================================

The algorithm described in Section \[sec:theory\] is polynomial time but only of theoretical interest because its running time is too high to be useful in practice. In the rest of this article we will focus on practical polynomial-time algorithms. In all these algorithms the ST-set, which can informally be thought of as treelike subsets of ${{\mathcal X}}$, has a central role. We begin by formally defining ST-sets and describing their basic properties. We will expand upon these basic properties in subsequent sections of the article.

Definition and basic properties of ST-sets {#subsec:stdefs}
