The Complexity of Rooted Phylogeny Problems

DOI10.2168/LMCS-7(4:6)2011zbMATH Open1237.68095arXiv1110.0693MaRDI QIDQ3224696FDOQ3224696

Authors: Manuel Bodirsky, Jens K. Mueller 

Publication date: 2 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1110.0693

Recommendations

• The computational complexity of inferring rooted phylogenies by parsimony
• On the complexity of inferring rooted evolutinary trees
• The complexity of phylogeny constraint satisfaction
• The complexity of phylogeny constraint satisfaction problems
• Computing phylogenetic roots with bounded degrees and errors is NP-complete
• On the complexity of constructing evolutionary trees
• On the combinatorics of rooted binary phylogenetic trees
• scientific article; zbMATH DE number 1830750
• The complexity of inferring a minimally resolved phylogenetic supertree

zbMATH Keywords

computational complexityconstraint satisfaction problemsphylogenetic reconstructionDatalog\(\omega\)-categorical structures

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25)

Cited In (8)

• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• The complexity of surjective homomorphism problems-a survey
• Algebraic global gadgetry for surjective constraint satisfaction
• The complexity of phylogeny constraint satisfaction
• The complexity of phylogeny constraint satisfaction problems
• Deciding the closure of inconsistent rooted triples is NP-complete
• The lowest common ancestor problem on a tree with an unfixed root
• An initial study of time complexity in infinite-domain constraint satisfaction

This page was built for publication: The Complexity of Rooted Phylogeny Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3224696)