zbMATH — the first resource for mathematics

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].

68W05 Nonnumerical algorithms
05C05 Trees
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
Full Text: DOI