×

zbMATH — the first resource for mathematics

Parameterized complexity results in symmetry breaking. (English) Zbl 1309.68104
Raman, Venkatesh (ed.) et al., Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17492-6/pbk). Lecture Notes in Computer Science 6478, 4-13 (2010).
Summary: Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is often computationally intractable. This paper argues that recent parameterized complexity results provide insight into that intractability and help identify special cases in which symmetry can be dealt with more tractably.
For the entire collection see [Zbl 1202.68012].

MSC:
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
Software:
CSPLib
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Komorowski, J., Raś, Z.W. (eds.) ISMIS 1993. LNCS, vol. 689, pp. 350–361. Springer, Heidelberg (1993) · doi:10.1007/3-540-56804-2_33
[2] Crawford, J., Ginsberg, M., Luks, G., Roy, A.: Symmetry breaking predicates for search problems. In: Proceedings of the 5th International Conference on Knowledge Representation and Reasoning (KR 1996), pp. 148–159 (1996)
[3] Walsh, T.: Symmetry within and between solutions. In: Zhang, B.-T., Orgun, M.A. (eds.) PRICAI 2010. LNCS, vol. 6230, pp. 11–13. Springer, Heidelberg (2010) · Zbl 05803308 · doi:10.1007/978-3-642-15246-7_4
[4] Katsirelos, G., Walsh, T.: Symmetries of symmetry breaking constraints. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) Proceedings of 19th European Conference on Artificial Intelligence, ECAI 2010. Frontiers in Artificial Intelligence and Applications, vol. 215, pp. 861–866. IOS Press, Amsterdam (2010) · Zbl 1211.68384
[5] Heule, M., Walsh, T.: Symmetry in solutions. In: Fox, M., Poole, D. (eds.) Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010. AAAI Press, Menlo Park (2010)
[6] Walsh, T.: Breaking value symmetry. In: Fox, D., Gomes, C. (eds.) Proceedings of the 23rd National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 1585–1588 (2008)
[7] Walsh, T.: Symmetry breaking. In: Sattar, A., Kang, B.-h. (eds.) AI 2006. LNCS (LNAI), vol. 4304, pp. 7–8. Springer, Heidelberg (2006) · Zbl 05271600 · doi:10.1007/11941439_4
[8] Gent, I., Walsh, T.: CSPLib: a benchmark library for constraints. Technical report, Technical report APES-09-1999, A shorter version appears in the Proceedings of the 5th International Conference on Principles and Practices of Constraint Programming, CP 1999 (1999)
[9] Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006) · Zbl 1175.90011
[10] Pachet, F., Roy, P.: Automatic generation of music programs. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 331–345. Springer, Heidelberg (1999) · doi:10.1007/978-3-540-48085-3_24
[11] Bessiere, C., Hebrard, E., Hnich, B., Walsh, T.: The complexity of global constraints. In: Proceedings of the 19th National Conference on AI, Association for Advancement of Artificial Intelligence (2004) · Zbl 1152.68542
[12] Bessière, C., Hebrard, E., Hnich, B., Walsh, T.: The tractability of global constraints. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 716–720. Springer, Heidelberg (2004) · Zbl 1152.68542 · doi:10.1007/978-3-540-30201-8_53
[13] Bessière, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering algorithms for the NVALUE constraint. Constraints 11(4), 271–293 (2006) · Zbl 1114.68064 · doi:10.1007/s10601-006-9001-9
[14] Bessière, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering algorithms for the NVALUE constraint. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2nd International Conference (CPAIOR 2005) (2005) · Zbl 1133.68427 · doi:10.1007/11493853_8
[15] Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pp. 49–99 (1999) · Zbl 0935.68046 · doi:10.1007/978-1-4612-0515-9
[16] Walsh, T.: General symmetry breaking constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 650–664. Springer, Heidelberg (2006) · Zbl 1160.68571 · doi:10.1007/11889205_46
[17] Katsirelos, G., Narodytska, N., Walsh, T.: Combining symmetry breaking and global constraints. In: Oddi, A., Fages, F., Rossi, F. (eds.) Recent Advances in Constraints. LNCS, vol. 5655, pp. 84–98. Springer, Heidelberg (2009) · Zbl 1248.68457 · doi:10.1007/978-3-642-03251-6_6
[18] Law, Y.C., Lee, J., Walsh, T., Yip, J.: Breaking symmetry of interchangeable variables and values. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 423–437. Springer, Heidelberg (2007) · Zbl 1145.68521 · doi:10.1007/978-3-540-74970-7_31
[19] Hnich, B., Kiziltan, Z., Walsh, T.: Combining symmetry breaking with other constraints: lexicographic ordering with sums. In: Proceedings of the 8th International Symposium on the Artificial Intelligence and Mathematics (2004)
[20] Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global constraints for lexicographic orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 93. Springer, Heidelberg (2002) · Zbl 05876473 · doi:10.1007/3-540-46135-3_7
[21] Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence 170(10), 803–908 (2006) · Zbl 1131.68521 · doi:10.1016/j.artint.2006.03.002
[22] Puget, J.F.: Breaking all value symmetries in surjection problems. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 490–504. Springer, Heidelberg (2005) · Zbl 1153.68478 · doi:10.1007/11564751_37
[23] Walsh, T.: Breaking value symmetry. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 880–887. Springer, Heidelberg (2007) · Zbl 05318867 · doi:10.1007/978-3-540-74970-7_67
[24] Bessière, C., Hebrard, E., Hnich, B., Kiziltan, Z., Quimper, C.G., Walsh, T.: The parameterized complexity of global constraints. In: Fox, D., Gomes, C. (eds.) Proceedings of the 23rd National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 235–240 (2008)
[25] Aloul, F., Ramani, A., Markov, I., Sakallah, K.: Solving difficult SAT instances in the presence of symmetries. In: Proceedings of the Design Automation Conference, pp. 731–736 (2002)
[26] Law, Y., Lee, J.: Global constraints for integer and set value precedence. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 362–376. Springer, Heidelberg (2004) · Zbl 1152.68563 · doi:10.1007/978-3-540-30201-8_28
[27] Walsh, T.: Symmetry breaking using value precedence. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) Proceedings of Including Prestigious Applications of Intelligent Systems (PAIS 2006), Riva del Garda, Italy, August 29-September 1. Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 168–172. IOS Press, Amsterdam (2006)
[28] Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking row and column symmetry in matrix models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 462. Springer, Heidelberg (2002) · Zbl 05876475 · doi:10.1007/3-540-46135-3_31
[29] Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Matrix modelling. Technical Report APES-36-2001, APES group, Presented at Formul, Workshop on Modelling and Problem Formulation, CP 2001 post-conference workshop (2001)
[30] Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Matrix modelling: Exploiting common patterns in constraint programming. In: Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems, held alongside CP 2002 (2002)
[31] Walsh, T.: Constraint patterns. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 53–64. Springer, Heidelberg (2003) · doi:10.1007/978-3-540-45193-8_4
[32] Huczynska, S., McKay, P., Miguel, I., Nightingale, P.: Modelling equidistant frequency permutation arrays: An application of constraints to mathematics. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 50–64. Springer, Heidelberg (2009) · Zbl 05612639 · doi:10.1007/978-3-642-04244-7_7
[33] Katsirelos, G., Narodytska, N., Walsh, T.: On the complexity and completeness of static constraints for breaking row and column symmetry. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 305–320. Springer, Heidelberg (2010) · Zbl 05803736 · doi:10.1007/978-3-642-15396-9_26
[34] Shlyakhter, I.: Generating effective symmetry-breaking predicates for search problems. Electronic Notes in Discrete Mathematics 9, 19–35 (2001) · Zbl 1158.68497 · doi:10.1016/S1571-0653(04)00311-7
[35] Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Symmetry in matrix models. Technical Report APES-30-2001, APES group, Presented at SymCon 2001 (Symmetry in Constraints), CP 2001 post-conference workshop (2001)
[36] Freuder, E.: A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery 29(1), 24–32 (1982) · Zbl 0477.68063 · doi:10.1145/322290.322292
[37] Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence 38, 353–366 (1989) · Zbl 0665.68084 · doi:10.1016/0004-3702(89)90037-4
[38] Cooper, M., Cohen, D., Jeavons, P.: Characterizing tractable constraints. Artificial Intelligence 65, 347–361 (1994) · Zbl 0803.68053 · doi:10.1016/0004-3702(94)90021-3
[39] Bessiere, C., Régin, J.: Arc consistency for general constraint networks: Preliminary results. In: Proceedings of the 15th International Conference on AI, International Joint Conference on Artificial Intelligence, pp. 398–404 (1997)
[40] Régin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on AI, Association for Advancement of Artificial Intelligence, pp. 362–367 (1994)
[41] Samer, M., Szeider, S.: Tractable cases of the extended global cardinality constraint. In: Proceedings of CATS 2008, Computing: The Australasian Theory Symposium (2008) · Zbl 1215.68164
[42] Szeider, S.: The complexity of resolution with generalized symmetry rules. Theory of Computing Systems 38(2), 171–188 (2005) · Zbl 1066.68121 · doi:10.1007/s00224-004-1192-0
[43] Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press, Amsterdam (2009)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.