Bodirsky, Manuel and Mueller, Jens K - The Complexity of Rooted Phylogeny Problems

lmcs:906 - Logical Methods in Computer Science, November 24, 2011, Volume 7, Issue 4
The Complexity of Rooted Phylogeny Problems

Authors: Bodirsky, Manuel and Mueller, Jens K

Several computational problems in phylogenetic reconstruction can be formulated as restrictions of the following general problem: given a formula in conjunctive normal form where the literals are rooted triples, is there a rooted binary tree that satisfies the formula? If the formulas do not contain disjunctions, the problem becomes the famous rooted triple consistency problem, which can be solved in polynomial time by an algorithm of Aho, Sagiv, Szymanski, and Ullman. If the clauses in the formulas are restricted to disjunctions of negated triples, Ng, Steel, and Wormald showed that the problem remains NP-complete. We systematically study the computational complexity of the problem for all such restrictions of the clauses in the input formula. For certain restricted disjunctions of triples we present an algorithm that has sub-quadratic running time and is asymptotically as fast as the fastest known algorithm for the rooted triple consistency problem. We also show that any restriction of the general rooted phylogeny problem that does not fall into our tractable class is NP-complete, using known results about the complexity of Boolean constraint satisfaction problems. Finally, we present a pebble game argument that shows that the rooted triple consistency problem (and also all generalizations studied in this paper) cannot be solved by Datalog.

DOI : 10.2168/LMCS-7(4:6)2011
Volume: Volume 7, Issue 4
Published on: November 24, 2011
Submitted on: November 17, 2010
Keywords: Computer Science - Computational Complexity,Computer Science - Computational Engineering, Finance, and Science,F.4.1


Consultation statistics

This page has been seen 151 times.
This article's PDF has been downloaded 205 times.