Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
From MaRDI portal
Publication:897856
DOI10.1016/J.TCS.2015.06.021zbMATH Open1332.68094arXiv1410.2371OpenAlexW2964101983MaRDI QIDQ897856FDOQ897856
Authors: Leo Van Iersel, Steven Kelk, Nela Lekić, Simone Linz 
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: A ternary permutation constraint satisfaction problem (CSP) is specified by a subset Pi of the symmetric group S_3. An instance of such a problem consists of a set of variables V and a set of constraints C, where each constraint is an ordered triple of distinct elements from V. The goal is to construct a linear order alpha on V such that, for each constraint (a,b,c) in C, the ordering of a,b,c induced by alpha is in Pi. Excluding symmetries and trivial cases there are 11 such problems, and their complexity is well known. Here we consider the variant of the problem, denoted 2-Pi, where we are allowed to construct two linear orders alpha and beta and each constraint needs to be satisfied by at least one of the two. We give a full complexity classification of all 11 2-Pi problems, observing that in the switch from one to two linear orders the complexity landscape changes quite abruptly and that hardness proofs become rather intricate. We then focus on one of the 11 problems in particular, which is closely related to the '2-Caterpillar Compatibility' problem in the phylogenetics literature. We show that this particular CSP remains hard on three linear orders, and also in the biologically relevant case when we swap three linear orders for three phylogenetic trees, yielding the '3-Tree Compatibility' problem. Due to the biological relevance of this problem we also give extremal results concerning the minimum number of trees required, in the worst case, to satisfy a set of rooted triplet constraints on n leaf labels.
Full work available at URL: https://arxiv.org/abs/1410.2371
Recommendations
- The complexity of phylogeny constraint satisfaction problems
- The complexity of phylogeny constraint satisfaction
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Determining the consistency of resolved triplets and fan triplets
Permutations, words, matrices (05A05) Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Total orders (06A05)
Cites Work
- Title not available (Why is that?)
- The complexity of temporal constraint satisfaction problems
- The circular chromatic number of a digraph
- The dichromatic number of a digraph
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Constructing the maximum consensus tree from rooted Triples
- Beating the random ordering is hard: every ordering CSP is approximation resistant
- Kernel and fast algorithm for dense triplet inconsistency
- Optimizing tree and character compatibility across several phylogenetic trees
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- New results on optimizing rooted triplets consistency
- Cyclic ordering is NP-complete
- A Geometric Approach to Betweenness
- Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
- An improved bound on the maximum agreement subtree problem
- The maximum agreement subtree problem
- On the complexity of inferring rooted evolutinary trees
- Domino tatami covering is NP-complete
Uses Software
This page was built for publication: Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897856)
