×

Necessary conditions for tractability of valued CSPs. (English) Zbl 1347.08009

Summary: The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, D. A. Cohen et al. [SIAM J. Comput. 42, No. 5, 1915–1939 (2013; Zbl 1305.08007)] have characterized a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of P. Creed and S. Živný from [“On minimal weighted clones”, Lect. Notes Comput. Sci. 6876, 210–224 (2011; doi:10.1007/978-3-642-23786-7_18)] on types of weightings necessarily contained in every nontrivial weighted clone. This result has immediate computational complexity consequences as it provides necessary conditions for tractability of weighted clones and thus valued constraint languages. We demonstrate that some of the necessary conditions are also sufficient for tractability, while others are provably not.

MSC:

08A70 Applications of universal algebra in computer science
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1305.08007
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] K. Apt, {\it Principles of Constraint Programming}, Cambridge University Press, Cambridge, 2003. · Zbl 1187.68132
[2] L. Barto and M. Kozik, {\it Constraint satisfaction problems solvable by local consistency methods}, J. ACM, 61 (2014). · Zbl 1295.68126
[3] L. Barto, M. Kozik, and T. Niven, {\it The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell)}, SIAM J. Comput., 38 (2009), pp. 1782-1802. · Zbl 1191.68460
[4] M. Bodirsky, H. Chen, J. Kára, and T. von Oertzen, {\it Maximal infinite-valued constraint languages}, Theoret. Comput. Sci., 410 (2009), pp. 1684-1693. · Zbl 1172.68052
[5] A. Bulatov, {\it A graph of a relational structure and constraint satisfaction problems}, in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS’04), IEEE Computer Society, 2004, pp. 448-457.
[6] A. Bulatov, {\it A dichotomy theorem for constraint satisfaction problems on a 3-element set}, J. ACM, 53 (2006), pp. 66-120. · Zbl 1316.68057
[7] A. Bulatov, A. Krokhin, and P. Jeavons, {\it Classifying the complexity of constraints using finite algebras}, SIAM J. Comput., 34 (2005), pp. 720-742. · Zbl 1071.08002
[8] A. A. Bulatov, {\it Complexity of conservative constraint satisfaction problems}, ACM Trans. Comput. Log., 12 (2011). · Zbl 1351.68113
[9] A. A. Bulatov, A. A. Krokhin, and P. G. Jeavons, {\it The complexity of maximal constraint languages}, in Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC’01), 2001, pp. 667-674. · Zbl 1323.68294
[10] D. A. Cohen, M. C. Cooper, P. Creed, P. Jeavons, and S. Živný, {\it An algebraic theory of complexity for discrete optimisation}, SIAM J. Comput., 42 (2013), pp. 915-1939. · Zbl 1305.08007
[11] D. A. Cohen, M. C. Cooper, P. Jeavons, and S. Živný, {\it Dualisation via binarisation for valued constraints}, in Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15), AAAI Press, Palo Alto, CA, 2015.
[12] D. A. Cohen, M. C. Cooper, P. G. Jeavons, and A. A. Krokhin, {\it The complexity of soft constraint satisfaction}, Artificial Intelligence, 170 (2006), pp. 983-1016. · Zbl 1131.68520
[13] P. Creed and S. Živný, {\it On minimal weighted clones}, in Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP’11), Lecture Notes in Comput. Sci. 6876, Springer, New York, 2011, pp. 210-224.
[14] N. Creignou, S. Khanna, and M. Sudan, {\it Complexity Classification of Boolean Constraint Satisfaction Problems}, SIAM Monogr. Discrete Math. Appl. 7, SIAM, Philadelphia, 2001. · Zbl 0981.68058
[15] B. Csákány, {\it Minimal clones–a minicourse}, Algebra Universalis, 54 (2005), pp. 73-89. · Zbl 1088.08002
[16] R. Dechter, {\it Constraint Processing}, Morgan Kaufmann, Burlington, MA, 2003. · Zbl 1057.68114
[17] K. Denecke and S. L. Wismath, {\it Universal Algebra and Applications in Theoretical Computer Science}, Chapman and Hall/CRC Press, Boca Raton, FL, 2002. · Zbl 0993.08001
[18] T. Feder and M. Y. Vardi, {\it The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory}, SIAM J. Comput., 28 (1998), pp. 57-104. · Zbl 0914.68075
[19] M. R. Garey and D. S. Johnson, {\it Computers and Intractability: A Guide to the Theory of NP-Completeness}, W.H. Freeman, San Francisco, 1979. · Zbl 0411.68039
[20] P. Hell and J. Nešetřil, {\it On the Complexity of \({H}\)-coloring}, J. Combin. Theory Ser. B, 48 (1990), pp. 92-110. · Zbl 0639.05023
[21] P. Hell and J. Nešetřil, {\it Colouring, constraint satisfaction, and complexity}, Comput. Sci. Rev., 2 (2008), pp. 143-163. · Zbl 1302.68251
[22] D. Hobby and R. N. McKenzie, {\it The Structure of Finite Algebras}, Contemp. Math. 76, AMS, Providence, RI, 1988. · Zbl 0721.08001
[23] A. Huber, A. Krokhin, and R. Powell, {\it Skew bisubmodularity and valued CSPs}, SIAM J. Comput., 43 (2014), pp. 1064-1084. · Zbl 1360.68512
[24] P. Jeavons, A. Krokhin, and S. Živný, {\it The complexity of valued constraint satisfaction}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 113 (2014), pp. 21-55. · Zbl 1409.68141
[25] P. G. Jeavons, {\it On the algebraic structure of combinatorial problems}, Theoret. Comput. Sci., 200 (1998), pp. 185-204. · Zbl 0915.68074
[26] P. G. Jeavons, D. A. Cohen, and M. Gyssens, {\it Closure properties of constraints}, J. ACM, 44 (1997), pp. 527-548. · Zbl 0890.68064
[27] P. Jonsson, F. Kuivinen, and G. Nordh, {\it MAX ONES generalized to larger domains}, SIAM J. Comput., 38 (2008), pp. 329-365. · Zbl 1162.68015
[28] P. Jonsson and G. Nordh, {\it Introduction to the maximum solution Problem}, in Complexity of Constraints, Lecture Notes in Comput. Sci. 5250, Springer, New York, 2008, pp. 255-282. · Zbl 1171.68499
[29] P. Jonsson, G. Nordh, and J. Thapper, {\it The maximum solution problem on graphs}, in Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS’07), Lecture Notes in Comput. Sci. 4708, Springer, New York, 2007, pp. 228-239. · Zbl 1147.68532
[30] S. Khanna, M. Sudan, L. Trevisan, and D. Williamson, {\it The approximability of constraint satisfaction problems}, SIAM J. Comput., 30 (2001), pp. 1863-1920. · Zbl 0992.68059
[31] V. Kolmogorov, {\it The power of linear programming for finite-valued CSPs: A constructive characterization}, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP’13), Lecture Notes in Comput. Sci. 7965, Springer, New York, 2013, pp. 625-636. · Zbl 1336.68134
[32] V. Kolmogorov, A. A. Krokhin, and M. Rolínek, {\it The Complexity of General-Valued CSPs}, Technical report, 2015, arXiv:1502.07327. · Zbl 1371.68117
[33] V. Kolmogorov, J. Thapper, and S. Živný, {\it The power of linear programming for general-valued CSPs}, SIAM J. Comput., 44 (2015), pp. 1-36. · Zbl 1456.68059
[34] V. Kolmogorov and S. Živný, {\it The complexity of conservative valued CSPs}, J. ACM, 60 (2013). · Zbl 1281.68134
[35] M. Kozik and J. Ochremiak, {\it Algebraic properties of valued constraint satisfaction problem}, in Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), Lecture Notes in Comput. Sci. 9134, Springer, Berlin, 2015. · Zbl 1441.68098
[36] R. N. McKenzie, G. F. McNulty, and W. F. Taylor, {\it Algebras, Lattices and Varieties}, Vol. I, Wadsworth and Brooks, Monterey, CA, 1987. · Zbl 0611.08001
[37] G. L. Nemhauser and L. A. Wolsey, {\it Integer and Combinatorial Optimization}, John Wiley & Sons, New York, 1988. · Zbl 0652.90067
[38] J. K. Pearson and P. G. Jeavons, {\it A Survey of Tractable Constraint Satisfaction Problems}, Technical report CSD-TR-97-15, Royal Holloway, University of London, Surrey, UK, 1997.
[39] R. Powell and A. A. Krokhin, {\it A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs}, Technical report, arXiv:1507.01776, 2015.
[40] T. J. Schaefer, {\it The complexity of satisfiability problems}, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78), ACM, New York, 1978, pp. 216-226. · Zbl 1282.68143
[41] S. Świerczkowski, {\it Algebras which are independently generated by every n elements}, Fund. Math., 49 (1960), pp. 93-104. · Zbl 0115.01201
[42] A. Szendrei, {\it Clones in Universal Algebra}, Sem. Math. Super., University of Montreal, Montreal, 1986. · Zbl 0603.08004
[43] R. Takhanov, {\it A dichotomy theorem for the general minimum cost homomorphism problem}, in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10), 2010, pp. 657-668. · Zbl 1230.90192
[44] R. Takhanov, {\it Extensions of the minimum cost homomorphism problem}, in Proceedings of the 16th International Computing and Combinatorics Conference (COCOON’10), Lecture Notes in Comput. Sci. 6196, Springer, New York, 2010, pp. 328-337. · Zbl 1286.68245
[45] J. Thapper and S. Živný, {\it The power of linear programming for valued CSPs}, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12), IEEE, New York, 2012, pp. 669-678.
[46] J. Thapper and S. Živný, {\it The complexity of finite-valued CSPs}, in Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC’13), ACM, New York, 2013, pp. 695-704. · Zbl 1294.68094
[47] J. Thapper and S. Živný, {\it Sherali-Adams relaxations for valued CSPs}, in Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), Lecture Notes in Comput. Sci. 9134, Springer, New York, 2015, pp. 1058-1069. · Zbl 1440.68132
[48] H. Uppman, {\it The complexity of three-element min-sol and conservative min-cost-hom}, in Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13), Lecture Notes in Comput. Sci. 7965, Springer, New York, 2013, pp. 804-815. · Zbl 1336.68148
[49] H. Uppman, {\it Computational complexity of the extended minimum cost homomorphism problem on three-element domains}, in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS’14), Vol. 25, 2014, pp. 651-662. · Zbl 1359.68145
[50] S. Živný, {\it The Complexity of Valued Constraint Satisfaction Problems}, Cogn. Technol., Springer, New York, 2012. · Zbl 1283.68024
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.