×

Combining tree partitioning, precedence, and incomparability constraints. (English) Zbl 1162.05321

Summary: The tree constraint partitions a directed graph into node-disjoint trees. In many practical applications that involve such a partition, there exist side constraints specifying requirements on tree count, node degrees, or precedences and incomparabilities within node subsets. We present a generalisation of the \(tree\) constraint that incorporates such side constraints. The key point of our approach is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints, in order to avoid thrashing during search. We describe filtering rules for this extended \(tree\) constraint and evaluate its effectiveness on three applications: the Hamiltonian path problem, the ordered disjoint paths problem, and the phylogenetic supertree problem.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C38 Paths and cycles

Software:

Gecode; CPGraph
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A.; Sagiv, Y.; Szymanski, T.; Ullman, J. D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM Journal of Computing, 10, 3, 405-421 (1981) · Zbl 0462.68086
[2] Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global constraint catalog. Research Report T2005-08, Swedish Institute of Computer Science.
[3] Beldiceanu, N., Flener, P., & Lorca, X. (2005). The tree constraint. In Proceedings of CP-AI-OR’05, LNCS (Vol. 3524, pp. 64-78). Springer. · Zbl 1133.90403
[4] Beldiceanu, N., Flener, P., & Lorca, X. (2006). Combining tree partitioning, precedence, incomparability, and degree constraints, with an application to phylogenetic and ordered-path problems. Technical Report 2006-020, Department of Information Technology, Uppsala University, Sweden. Available at http://www.it.uu.se/research/publications/reports/2006-020/. · Zbl 1162.05321
[5] Beldiceanu, N., Flener, P., & Lorca, X. (2006). Partitionnement de graphes par des arbres sous contraintes de degré. In Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC’06) (pp. 35-42). (in French).
[6] Beldiceanu, N., & Lorca, X. (2007). Necessary condition for path partitioning constraints. In Proceedings of CP-AI-OR’07, LNCS (Vol. 4510, pp. 141-154). Springer. · Zbl 1214.90120
[7] Bininda-Emonds, O.; Gittleman, J.; Steel, M., The (super)tree of life: Procedures, problems, and prospects, Annual Reviews of Ecological Systems, 33, 265-289 (2002)
[8] Bodirsky, M., Duchier, D., Miehle, S., & Niehren, J. (2004). A new algorithm for normal dominance constraints. In Proceedings of SODA’04, (pp. 59-67). · Zbl 1318.05071
[9] Bodirsky, M.; Kutz, M., Determining the consistency of partial tree descriptions, Artificial Intelligence, 171, 185-196 (2007) · Zbl 1168.68546
[10] Bourreau, E. (1999). Traitement de contraintes sur les graphes en programmation par contraintes. Ph.D. thesis, University of Paris 13, France (March). In French.
[11] Cambazard, H., & Bourreau, E. (2004). Conception d’une contrainte globale de chemin. In Proceedings of the Dixièmes Journées Nationales sur la Résolution Pratique de Problèmes NP-Complets (JNPC’04) (pp. 107-120). (in French).
[12] Cayley, A., A theorem on trees, Quarterly Journal of Mathematics, 23, 376-378 (1889) · JFM 21.0687.01
[13] Cooper, K.; Harvey, T.; Kennedy, K., A simple, fast dominance algorithm, Software Practice and Experience, 31, 4, 1-10 (2001)
[14] COSYTEC. (1997). CHIP Reference Manual, release 5.1 edition.
[15] Dooms, G., Deville, Y., & Dupont, P. E. (2005). CP(Graph): Introducing a graph computation domain in constraint programming. In Proceedings of CP’05, LNCS (Vol. 3709, pp. 211-225). · Zbl 1153.68457
[16] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1978), New York: Freeman, New York
[17] Gent, I., Prosser, P., Smith, B., & Wei, W. (2003). Supertree construction with constraint programming. In Proceedings of CP’03, LNCS (Vol. 2833, pp. 837-841).
[18] Katriel, I. (2006). Expected-case analysis for delayed filtering. In Proceedings of CP-AI-OR’06, LNCS (Vol. 3990, pp. 119-125). Springer-Verlag. · Zbl 1177.68190
[19] Kennedy, M.; Page, R. D., Seabird supertrees: Combining partial estimates of procellariiform phylogeny, The Auk, A Quarterly Journal of Ornithology, 119, 88-108 (2002)
[20] Komlós, J.; Szemerédi, E., Limit distribution for the existence of a Hamilton cycle in a random graph, Discrete Mathematics, 43, 55-63 (1983) · Zbl 0521.05055
[21] Lengauer, T.; Tarjan, R. E., A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems, 1, 1, 121-141 (1979) · Zbl 0449.68024
[22] Lorca, X. (2007). Contraintes de Partitionnement de Graphe. Ph.D. thesis, Université de Nantes, École des Mines, Nantes, France (in French). · Zbl 1218.05004
[23] Ng, M.; Wormald, N., Reconstruction of rooted trees from subtrees, Discrete Applied Mathematics, 69, 19-31 (1996) · Zbl 0868.05019
[24] Pape, C. L., Perron, L., Régin, J.-C., & Shaw, P. (2002). Robust and parallel solving of a network design problem. In Proceedings of CP’02, LNCS (Vol. 2470, pp. 633-648). Springer-Verlag.
[25] Pósa, L., Hamiltonian circuits in random graphs, Discrete Mathematics, 14, 359-364 (1976) · Zbl 0322.05127
[26] Quesada, L. (2006). Solving Constrained Graph Problems Using Reachability Constraints Based on Transitive Closure and Dominators. Ph.D. thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium.
[27] Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSP. In Proceedings of AAAI’94 (pp. 362-367).
[28] Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of AAAI’96 (pp. 209-215).
[29] Richaud, G., Lorca, X., & Jussien, N. (2007). A portable and efficient implementation of global constraints: The tree constraint case. In Abreu, S. & Costa, V. S. (eds.), Proceedings of CICLOPS’07, Porto, Portugal (September).
[30] Schulte, C., Lagerkvist, M., & Tack, G. (2006). Gecode. Available at http://www.gecode.org/.
[31] Steel, M., The complexity of reconstructing trees from qualitative characters and subtrees, Journal of Classification, 9, 91-116 (1992) · Zbl 0766.92002
[32] Tutte, W. T., On Hamiltonian circuits, Journal of the London Mathematical Society, 21, 98-101 (1946) · Zbl 0061.41306
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.