Computer Science – Computational Complexity
Scientific paper
2011-10-04
LMCS 7 (4:6) 2011
Computer Science
Computational Complexity
Scientific paper
10.2168/LMCS-7(4:6)2011
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.
Bodirsky Manuel
Mueller Jens K.
No associations
LandOfFree
The Complexity of Rooted Phylogeny Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Rooted Phylogeny Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Rooted Phylogeny Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-268256