×

Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees. (English) Zbl 1332.68094

Summary: 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 \(\mathcal{C}\), where each constraint is an ordered triple of distinct elements from \(V\). The goal is to construct a linear ordering \(\alpha\) on \(V\) such that, for each constraint \((a, b, c) \in \mathcal{C}\), the ordering of \(a\), \(b\), \(c\) induced by \(\alpha\) is in \(\Pi\). Excluding symmetries and trivial cases there are eleven 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 eleven 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. To establish the proofs, we use several computer-aided searches. Each such search returns a small instance with a unique solution for a given problem. We then focus on one of the eleven 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. Lastly, we 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.

MSC:

68Q25 Analysis of algorithms and problem complexity
05A05 Permutations, words, matrices
06A05 Total orders
92D15 Problems related to evolution

Software:

MiniZinc
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aho, A. V.; Sagiv, Y.; Szymanski, T. G.; Ullman, J. D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM J. Comput., 10, 3, 405-421 (1981) · Zbl 0462.68086
[2] Bodirsky, M.; Kára, J., The complexity of temporal constraint satisfaction problems, J. ACM, 57, 2, 9 (2010) · Zbl 1327.68125
[3] Bokal, D.; Fijavz, G.; Juvan, M.; Kayll, P. M.; Mohar, B., The circular chromatic number of a digraph, J. Graph Theory, 46, 3, 227-240 (2004) · Zbl 1041.05026
[4] Bryant, D., Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis (1997), University of Canterbury: University of Canterbury Christchurch, New Zealand, PhD thesis
[5] Byrka, J.; Gawrychowski, P.; Huber, K. T.; Kelk, S. M., Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, J. Discrete Algorithms, 8, 1, 65-75 (2010) · Zbl 1181.90270
[6] Byrka, J.; Guillemot, S.; Jansson, J., New results on optimizing rooted triplets consistency, Discrete Appl. Math., 158, 11, 1136-1147 (June 2010)
[7] Chor, B.; Sudan, M., A geometric approach to betweenness, SIAM J. Discrete Math., 11, 4, 511-523 (1998) · Zbl 0912.68058
[8] Erickson, A.; Ruskey, F., Domino tatami covering is NP-complete, (Combinatorial Algorithms (2013), Springer), 140-149 · Zbl 1408.05031
[9] Galil, Z.; Megiddo, N., Cyclic ordering is NP-complete, Theoret. Comput. Sci., 5, 2, 179-182 (1977) · Zbl 0383.68045
[10] Guillemot, S.; Mnich, M., Kernel and fast algorithm for dense triplet inconsistency, Theoret. Comput. Sci., 494, 134-143 (2013) · Zbl 1294.68091
[11] Guruswami, V.; Håstad, J.; Manokaran, R.; Raghavendra, P.; Charikar, M., Beating the random ordering is hard: Every ordering CSP is approximation resistant, SIAM J. Comput., 40, 3, 878-914 (2011) · Zbl 1235.68075
[12] Gutin, G.; van Iersel, L. J.J.; Mnich, M.; Yeo, A., Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, J. Comput. System Sci., 78, 1, 151-163 (2012) · Zbl 1242.68122
[13] Guttmann, W.; Maucher, M., Variations on an ordering theme with constraints, (Fourth IFIP International Conference on Theoretical Computer Science. Fourth IFIP International Conference on Theoretical Computer Science, TCS 2006 (2006), Springer), 77-90
[14] Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications (2011), Cambridge University Press: Cambridge University Press UK
[15] Jansson, Jesper, On the complexity of inferring rooted evolutionary trees, (Brazilian Symposium on Graphs, Algorithms and Combinatorics. Brazilian Symposium on Graphs, Algorithms and Combinatorics, Electronic Notes in Discrete Mathematics, vol. 7 (2001)), 4 · Zbl 1106.92306
[16] Linz, S.; St John, K.; Semple, C., Optimizing tree and character compatibility across several phylogenetic trees, Theoret. Comput. Sci., 513, 129-136 (2013) · Zbl 1358.68140
[17] Martin, D. M.; Thatte, B. D., The maximum agreement subtree problem, Discrete Appl. Math., 161, 13, 1805-1817 (2013) · Zbl 1286.05029
[18] Morrison, D. A., Introduction to Phylogenetic Networks (2011), RJR Productions: RJR Productions Uppsala
[19] Nakhleh, L., Computational approaches to species phylogeny inference and gene tree reconciliation, Trends Ecol. Evol., 28, 12, 719-728 (2013)
[20] Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; Tack, G., MiniZinc: towards a standard CP modelling language, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, CP 2007 (2007), Springer), 529-543
[21] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 3, 265-270 (1982) · Zbl 0506.05031
[22] Ruepp, O.; Holzer, M., The computational complexity of the KAKURO puzzle, revisited, (Fun with Algorithms (2010), Springer), 319-330
[23] Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press · Zbl 1043.92026
[24] Steel, M.; Székely, L. A., An improved bound on the maximum agreement subtree problem, Appl. Math. Lett., 22, 11, 1778-1780 (2009) · Zbl 1177.05026
[25] Wu, Bang Ye, Constructing the maximum consensus tree from rooted triples, J. Comb. Optim., 8, 1, 29-39 (2004) · Zbl 1058.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.