Intractability of Smast and Smct Sample Clauses

Intractability of Smast and Smct. The algorithm of the previous section cannot be extended to collections of input trees. This stems from the fact that now also hosts leaves belonging to several but not all input trees. There are cases where no , resp. tree can be completed to obtain a , resp. , tree (see Fig. 3 of appendix 4.11 for an example). Indeed, there is an important gap in complexity between the case of input trees, and an arbitrary number of trees as we now show. If not specified, trees in this section are to be considered rooted. Formulating SMAST as the following decision problem: Maximum Agreement Supertree (Smast) instance: A collection of trees on overlapping sets of leaves and an integer . question: Is there an agreement supertree of with at least leaves? we prove, by reduction to the general HITTING SET problem (HS), that SMAST is NP-complete and -hard for the parameter , even for instances consisting only of rooted triples Note that MAST on rooted triples is solved in time and is FPT for parameter in the general case. As MAST is the special case of SMAST where input trees have identical sets of leaves, the NP-hardness result for only three input trees obtained by [1] for MAST also holds for SMAST. Similarly, SMCT in NP-hard for 6 trees from the result of [20]. Definition 7 ([2, 9, 28]) Let be a collection of trees with leaves in , define to be the undirected graph with vertices and with edge set with . Lemma 7 If is connected then there exists no agreement supertree of on . Proof. A direct consequence of theorem 2 of [9]. Definition 8 We recursively define the function associating a tree to an non-empty ordered sequence of trees with non-intersecting leaf sets: – for any tree and – for any sequence of trees of length s.t. . The second item above uses the parenthetical notation for trees. Appendix 4.10 includes a figure illustrating this definition. Definition 9 (Gadget) Let and a set of distinct labels , , . . . , , , , . . . , , we define to be the following collection of rooted triple trees: where we set , et . 2 though, when aiming at a seed tree for the method, we guess it might be better to conserve the topology of the specific subtrees. The following lemma shows that there is no agreement supertree of on , however removing any element leads to the existence of such a tree, thus to the existence of a maximum agreement supertree on leaves . Moreover, the restriction of this tree to leaves is indifferent. Lemma 8 Let .