{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:47Z","timestamp":1772313227427,"version":"3.50.1"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T00:00:00Z","timestamp":1474416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Community's Seventh Framework Programme","award":["257039"],"award-info":[{"award-number":["257039"]}]},{"name":"Royal Society University Research Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,11,8]]},"abstract":"<jats:p>We study the computational complexity of exact minimization of rational-valued discrete functions. Let \u0393 be a set of rational-valued functions on a fixed finite domain; such a set is called a<jats:italic>finite-valued constraint language<\/jats:italic>. The valued constraint satisfaction problem, VCSP(\u0393), is the problem of minimizing a function given as a sum of functions from \u0393. We establish a dichotomy theorem with respect to exact solvability for<jats:italic>all<\/jats:italic>finite-valued constraint languages defined on domains of<jats:italic>arbitrary<\/jats:italic>finite size.<\/jats:p><jats:p>We show that every constraint language \u0393 either admits a binary symmetric fractional polymorphism, in which case the basic linear programming relaxation solves any instance of VCSP(\u0393) exactly, or \u0393 satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(\u0393).<\/jats:p>","DOI":"10.1145\/2974019","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T12:42:46Z","timestamp":1474461766000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["The Complexity of Finite-Valued CSPs"],"prefix":"10.1145","volume":"63","author":[{"given":"Johan","family":"Thapper","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Est Marne-la-Vall\u00e9e, France"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Graduate Texts in Mathematics Series","volume":"248","author":"Abramenko P."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.25"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214061"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04874-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11889205_10"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.04.002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-007-9037-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.02.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.02.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387933.2387943"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Y. Crama and P. L. Hammer. 2011. Boolean Functions - Theory Algorithms and Applications. Cambridge University Press. Y. Crama and P. L. Hammer. 2011. Boolean Functions - Theory Algorithms and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511852008"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2041160.2041181"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_2_1_23_1","volume-title":"Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications Series","volume":"7","author":"Creignou N."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540090"},{"key":"e_1_2_1_25_1","unstructured":"R. Dechter. 2003. Constraint Processing. Morgan Kaufmann. R. Dechter. 2003. Constraint Processing. Morgan Kaufmann."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391290"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29828-8_11"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_30_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_33_1","volume-title":"Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics Series","volume":"2","author":"Gr\u00f6tschel M."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0256-y"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press. P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0824-7"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","author":"Huber A."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/120893549"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444644X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.022"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669231"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP\u201911)","volume":"6876","author":"Jonsson P."},{"key":"e_1_2_1_50_1","unstructured":"J. G. Kemeny and J. L. Snell. 1976. Finite Markov Chains. Undergraduate texts in mathematics. Springer New York. Reprint of the 1960 ed. published by Van Nostrand Princeton N.J. in the University series in undergraduate mathematics. J. G. Kemeny and J. L. Snell. 1976. Finite Markov Chains. Undergraduate texts in mathematics. Springer New York. Reprint of the 1960 ed. published by Van Nostrand Princeton N.J. in the University series in undergraduate mathematics."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.19"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti144"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_53"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450146"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00043-1"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"S. L. Lauritzen. 1996. Graphical Models. Oxford University Press. S. L. Lauritzen. 1996. Graphical Models. Oxford University Press.","DOI":"10.1093\/oso\/9780198522195.001.0001"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90042-6"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_67_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070399"},{"key":"e_1_2_1_70_1","series-title":"City Mathematics Series","volume-title":"An introduction to hyperplane arrangements","author":"Stanley R. P."},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","author":"Takhanov R.","year":"2010"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886811.1886854"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.25"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488697"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_68"},{"key":"e_1_2_1_76_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","volume":"25","author":"Uppman H.","year":"2014"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856938"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_2_1_79_1","volume-title":"The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies","author":"\u017divn\u00fd S."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2974019","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2974019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:43Z","timestamp":1750220623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2974019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,21]]},"references-count":78,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,8]]}},"alternative-id":["10.1145\/2974019"],"URL":"https:\/\/doi.org\/10.1145\/2974019","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,21]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}