Maximum agreement and compatible supertrees (extended abstract).

*(English)*Zbl 1103.68966
Sahinalp, Suleyman Cenk (ed.) et al., Combinatorial pattern matching. 15th annual symposium, CPM 2004, Istanbul, Turkey, July 5–7, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22341-X/pbk). Lecture Notes in Computer Science 3109, 205-219 (2004).

Summary: Given a collection of trees on \(n\) leaves with identical leaf set, the MAST, resp. MCT, problem consists in finding a largest subset of leaves such that all input trees restricted to these leaves are isomorphic, resp. have a common refinement. For MAST, resp. MCT, on \(k\) rooted trees, we give an \(O(\min \{3^{p} kn,2.27^{p}+ kn^{3}\})\) exact algorithm, where \(p\) is the smallest number of leaves to remove from input trees in order for these trees to be isomorphic, resp. to admit a common refinement. This improves on [R. G. Downey, M. R. Fellows, and U. Stege, “Computational tractability: The view from Mars”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 69, 73–97 (1999; Zbl 0941.68577)] for MAST and proves fixed-parameter tractability for MCT. We also give an approximation algorithm for (the complement of) MAST, similar to the one of [A. Amir and D. Keselman, “Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms”, SIAM J. Comput. 26, No. 6, 1656–1669 (1997; Zbl 0885.68071)], but with a better ratio and running time, and extend it to MCT.

We generalize MAST and MCT to the case of supertrees where input trees can have non-identical leaf sets. For the resulting problems, SMAST and SMCT, we give an \(O(N + n)\) time algorithm for the special case of two input trees \((N\) is the time bound for solving MAST, resp. MCT, on two \(O(n)\)-leaf trees). Last, we show that SMAST and SMCT parameterized in \(p\) are W[2]-hard and cannot be approximated in polynomial time within a constant factor unless \(\text{P} = \text{NP}\), even when the input trees are rooted triples.

We also extend the above results to the case of unrooted input trees.

For the entire collection see [Zbl 1052.68008].

We generalize MAST and MCT to the case of supertrees where input trees can have non-identical leaf sets. For the resulting problems, SMAST and SMCT, we give an \(O(N + n)\) time algorithm for the special case of two input trees \((N\) is the time bound for solving MAST, resp. MCT, on two \(O(n)\)-leaf trees). Last, we show that SMAST and SMCT parameterized in \(p\) are W[2]-hard and cannot be approximated in polynomial time within a constant factor unless \(\text{P} = \text{NP}\), even when the input trees are rooted triples.

We also extend the above results to the case of unrooted input trees.

For the entire collection see [Zbl 1052.68008].