{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:24:04Z","timestamp":1787390644885,"version":"build-2736575974"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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, Cohen et al. [SIAM J. Comput., 42 (2013), pp. 915--1939] 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 Creed and \u017divn\u00fd from [Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, 2011, pp. 210--224] 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.<\/jats:p>","DOI":"10.1137\/140990346","type":"journal-article","created":{"date-parts":[[2015,12,3]],"date-time":"2015-12-03T21:50:41Z","timestamp":1449179441000},"page":"2361-2384","source":"Crossref","is-referenced-by-count":7,"title":["Necessary Conditions for Tractability of Valued CSPs"],"prefix":"10.1137","volume":"29","author":[{"given":"Johan","family":"Thapper","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,12,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"K. Apt,\n                      Principles of Constraint Programming\n                      , Cambridge University Press, Cambridge, 2003.","DOI":"10.1017\/CBO9780511615320"},{"key":"atypb2","first-page":"61","author":"Barto L.","year":"2014","journal-title":"J. ACM"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.050"},{"key":"atypb5","first-page":"448","author":"Bulatov A.","year":"2004","journal-title":"IEEE Computer Society"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"atypb8","first-page":"12","author":"Bulatov A. A.","year":"2011","journal-title":"ACM Trans. Comput. Log."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov, A. A. Krokhin, and P. G. Jeavons,\n                      The complexity of maximal constraint languages\n                      , in Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC'01), 2001, pp. 667-674.","DOI":"10.1145\/380752.380868"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"D. A. Cohen, M. C. Cooper, P. Jeavons, and S. Z\u030civny\u0301,\n                      Dualisation via binarisation for valued constraints\n                      , in Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), AAAI Press, Palo Alto, CA, 2015.","DOI":"10.1609\/aaai.v29i1.9749"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.04.002"},{"key":"atypb13","first-page":"210","author":"Creed P.","year":"2011","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity Classification of Boolean Constraint Satisfaction Problems\n                      , SIAM Monogr. Discrete Math. Appl. 7, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-005-1924-2"},{"key":"atypb16","unstructured":"R. Dechter,\n                      Constraint Processing\n                      , Morgan Kaufmann, Burlington, MA, 2003."},{"key":"atypb17","unstructured":"K. Denecke and S. L. Wismath,\n                      Universal Algebra and Applications in Theoretical Computer Science\n                      , Chapman and Hall\/CRC Press, Boca Raton, FL, 2002."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb19","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W.H. Freeman, San Francisco, 1979."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"D. Hobby and R. N. McKenzie,\n                      The Structure of Finite Algebras\n                      , Contemp. Math. 76, AMS, Providence, RI, 1988.","DOI":"10.1090\/conm\/076"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/120893549"},{"key":"atypb24","first-page":"21","volume":"113","author":"Jeavons P.","year":"2014","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/060669231"},{"key":"atypb28","first-page":"255","author":"Jonsson P.","year":"2008","journal-title":"New York"},{"key":"atypb29","first-page":"228","author":"Jonsson P.","year":"2007","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"atypb31","first-page":"625","author":"Kolmogorov V.","year":"2013","journal-title":"New York"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"V. Kolmogorov, A. A. Krokhin, and M. Roli\u0301nek,\n                      The Complexity of General-Valued CSPs\n                      , Technical report, 2015, arXiv:1502.07327.","DOI":"10.1109\/FOCS.2015.80"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"atypb34","first-page":"60","author":"Kolmogorov V.","year":"2013","journal-title":"J. ACM"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"M. Kozik and J. Ochremiak,\n                      Algebraic properties of valued constraint satisfaction problem\n                      , in Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15), Lecture Notes in Comput. Sci. 9134, Springer, Berlin, 2015.","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"atypb36","unstructured":"R. N. McKenzie, G. F. McNulty, and W. F. Taylor,\n                      Algebras, Lattices and Varieties\n                      , Vol. I, Wadsworth and Brooks, Monterey, CA, 1987."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser and L. A. Wolsey,\n                      Integer and Combinatorial Optimization\n                      , John Wiley & Sons, New York, 1988.","DOI":"10.1002\/9781118627372"},{"key":"atypb38","unstructured":"J. K. Pearson and P. G. Jeavons,\n                      A Survey of Tractable Constraint Satisfaction Problems\n                      , Technical report CSD-TR-97-15, Royal Holloway, University of London, Surrey, UK, 1997."},{"key":"atypb39","unstructured":"R. Powell and A. A. Krokhin,\n                      A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs\n                      , Technical report, arXiv:1507.01776, 2015."},{"key":"atypb40","first-page":"216","author":"Schaefer T. J.","year":"1978","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-1-93-104"},{"key":"atypb42","unstructured":"A. Szendrei,\n                      Clones in Universal Algebra\n                      , Sem. Math. Super., University of Montreal, Montreal, 1986."},{"key":"atypb43","unstructured":"R. Takhanov,\n                      A dichotomy theorem for the general minimum cost homomorphism problem\n                      , in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'10), 2010, pp. 657-668."},{"key":"atypb44","first-page":"328","author":"Takhanov R.","year":"2010","journal-title":"New York"},{"key":"atypb45","first-page":"669","author":"Thapper J.","year":"2012","journal-title":"New York"},{"key":"atypb46","first-page":"695","author":"Thapper J.","year":"2013","journal-title":"New York"},{"key":"atypb47","first-page":"1058","author":"Thapper J.","year":"2015","journal-title":"New York"},{"key":"atypb48","first-page":"804","author":"Uppman H.","year":"2013","journal-title":"New York"},{"key":"atypb49","unstructured":"H. Uppman,\n                      Computational complexity of the extended minimum cost homomorphism problem on three-element domains\n                      , in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS'14), Vol. 25, 2014, pp. 651-662."},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"S. Z\u030civny\u0301,\n                      The Complexity of Valued Constraint Satisfaction Problems\n                      , Cogn. Technol., Springer, New York, 2012.","DOI":"10.1007\/978-3-642-33974-5"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140990346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:48:00Z","timestamp":1787320080000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140990346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140990346"],"URL":"https:\/\/doi.org\/10.1137\/140990346","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}