The complexity of phylogeny constraint satisfaction problems

DOI10.1145/3105907MaRDI QIDQ5369246zbMATH OpenOpenAlexWikidataFDO

Authors Manuel Bodirsky, Peter Jonsson, Trung van Pham

Publication date 16 October 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconstraint satisfaction problemsmodel theoryphylogenetic reconstructionRamsey theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Abstract: We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains for example the rooted triple consistency problem, forbidden subtree problems, the quartet consistency problem, and many other problems studied in the bioinformatics literature. The studied problems can be described as emph{constraint satisfaction problems} where the constraints have a first-order definition over the rooted triple relation. We show that every such phylogeny problem can be solved in polynomial time or is NP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithm of Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithm repeatedly solves linear equation systems to construct a solution in polynomial time. We then show that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Our classification establishes a dichotomy for a large class of infinite structures that we believe is of independent interest in universal algebra, model theory, and topology. The proof of our main result combines results and techniques from various research areas: a recent classification of the model-complete cores of the reducts of the homogeneous binary branching C-relation, Leeb's Ramsey theorem for rooted trees, and universal algebra.

Recommendations

• The complexity of phylogeny constraint satisfaction
• The Complexity of Rooted Phylogeny Problems
• Counting consistent phylogenetic trees is \#P-complete
• Algorithms for phylogeny reconstruction in a new mathematical model
• Extension operations on sets of leaf-labelled trees

Cited in

(22)

• Approximation algorithms for the fixed-topology phylogenetic number problem
• Phylogenetic flexibility via Hall-type inequalities and submodularity
• Using model theory to find decidable and tractable description logics with concrete domains
• On a stronger reconstruction notion for monoids and clones
• Unique perfect phylogeny is NP-hard
• The Complexity of Rooted Phylogeny Problems
• The complexity of phylogeny constraint satisfaction
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Deciding the closure of inconsistent rooted triples is NP-complete
• Tractable combinations of temporal CSPs
• \( \omega \)-categorical structures avoiding height 1 identities
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Constraint satisfaction problems for reducts of homogeneous graphs
• Constructing Camin-Sokal Phylogenies Via Answer Set Programming
• Solving infinite-domain CSPs using the patchwork property
• Complexity classification transfer for CSPs via algebraic products
• Homogeneity and homogenizability: hard problems for the logic SNP
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• A complexity dichotomy in spatial reasoning via Ramsey theory
• Three fundamental questions in modern infinite-domain constraint satisfaction
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees

This page was built for publication: The complexity of phylogeny constraint satisfaction problems

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