{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:13Z","timestamp":1750221073968,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,21]],"date-time":"2018-11-21T00:00:00Z","timestamp":1542758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["714532"],"award-info":[{"award-number":["714532"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>\n            Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a (Q \u222a {\u221e })-valued objective function given as a sum of fixed-arity functions. In Boolean surjective VCSPs, variables take on labels from\n            <jats:italic>D<\/jats:italic>\n            = {0,1}, and an optimal assignment is required to use both labels from\n            <jats:italic>D<\/jats:italic>\n            . Examples include the classical\n            <jats:italic>global Min-Cut<\/jats:italic>\n            problem in graphs and the\n            <jats:italic>Minimum Distance<\/jats:italic>\n            problem studied in coding theory.\n          <\/jats:p>\n          <jats:p>\n            We establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs with respect to exact solvability. Our work generalises the dichotomy for {0, \u221e}-valued constraint languages (corresponding to surjective decision CSPs) obtained by Creignou and H\u00e9brard. For the maximisation problem of Q\n            <jats:sub>\u22650<\/jats:sub>\n            -valued surjective VCSPs, we also establish a dichotomy theorem with respect to approximability.\n          <\/jats:p>\n          <jats:p>Unlike in the case of Boolean surjective (decision) CSPs, there appears a novel tractable class of languages that is trivial in the non-surjective setting. This newly discovered tractable class has an interesting mathematical structure related to downsets and upsets. Our main contribution is identifying this class and proving that it lies on the borderline of tractability. A crucial part of our proof is a polynomial-time algorithm for enumerating all near-optimal solutions to a generalised Min-Cut problem, which might be of independent interest.<\/jats:p>","DOI":"10.1145\/3282429","type":"journal-article","created":{"date-parts":[[2018,11,26]],"date-time":"2018-11-26T13:07:25Z","timestamp":1543237645000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Boolean Surjective General-Valued CSPs"],"prefix":"10.1145","volume":"11","author":[{"given":"Peter","family":"Fulla","sequence":"first","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hannes","family":"Uppman","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,21]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_3_1","unstructured":"Libor Barto Andrei Krokhin and Ross Willard. 2017. Polymorphisms and how to use them. See Reference Krokhin and \u017divn\u00fd {33} 1--44.  Libor Barto Andrei Krokhin and Ross Willard. 2017. Polymorphisms and how to use them. See Reference Krokhin and \u017divn\u00fd {33} 1--44."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.029"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.09.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-014-0308-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CONS.0000036045.82829.94"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1163940.1644558"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_2_1_14_1","first-page":"499","article-title":"On generating all solutions of generalized satisfiability problems. Info","volume":"31","author":"Creignou Nadia","year":"1997","unstructured":"Nadia Creignou and Jean-Jacques H\u00e9brard . 1997 . On generating all solutions of generalized satisfiability problems. Info . Th\u00e9or. Appl. 31 , 6 (1997), 499 -- 511 . Nadia Creignou and Jean-Jacques H\u00e9brard. 1997. On generating all solutions of generalized satisfiability problems. Info. Th\u00e9or. Appl. 31, 6 (1997), 499--511.","journal-title":"Th\u00e9or. Appl."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/791230.792302"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the AAAI 1992 Workshop on Tractable Reasoning. 35--39","author":"Dechter Rina","year":"1992","unstructured":"Rina Dechter and Alon Itai . 1992 . Finding all solutions if you can find one . In Proceedings of the AAAI 1992 Workshop on Tractable Reasoning. 35--39 . Rina Dechter and Alon Itai. 1992. Finding all solutions if you can find one. In Proceedings of the AAAI 1992 Workshop on Tractable Reasoning. 35--39."},{"key":"e_1_2_1_17_1","volume-title":"On the approximation of submodular functions. (Apr","author":"Devanur Nikhil R.","year":"2013","unstructured":"Nikhil R. Devanur , Shaddin Dughmi , Roy Schwartz , Ankit Sharma , and Mohit Singh . 2013. On the approximation of submodular functions. (Apr . 2013 ). Retrieved from http:\/\/arxiv.org\/abs\/1304.4948. Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz, Ankit Sharma, and Mohit Singh. 2013. On the approximation of submodular functions. (Apr. 2013). Retrieved from http:\/\/arxiv.org\/abs\/1304.4948."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.06.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.029"},{"key":"e_1_2_1_21_1","unstructured":"Andr\u00e1s Frank. 2011. Connections in Combinatorial Optimization. OUP Oxford. Retrieved from https:\/\/books.google.co.uk\/books?id&equals;acQZuWho7m8C.  Andr\u00e1s Frank. 2011. Connections in Combinatorial Optimization. OUP Oxford. Retrieved from https:\/\/books.google.co.uk\/books?id&equals;acQZuWho7m8C."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898438"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)","author":"Fulla Peter","year":"2017","unstructured":"Peter Fulla and Stanislav \u017divn\u00fd . 2017 . The complexity of ooleanBoolean surjective general-valued CSPs . In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917) . Peter Fulla and Stanislav \u017divn\u00fd. 2017. The complexity of ooleanBoolean surjective general-valued CSPs. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-012-0164-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.039"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/120893549"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444644X"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993)","author":"Karger David R.","year":"1993","unstructured":"David R. Karger . 1993 . Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm . In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993) . 21--30. David R. Karger. 1993. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993). 21--30."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.19"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"e_1_2_1_33_1","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups","volume":"7","author":"Andrei","unstructured":"Andrei A. Krokhin and Stanislav \u017divn\u00fd (Eds.). 2017 . The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Andrei A. Krokhin and Stanislav \u017divn\u00fd (Eds.). 2017. The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_34_1","unstructured":"Konstantin Makarychev and Yury Makarychev. 2017. Approximation algorithms for CSPs. See Reference Krokhin and \u017divn\u00fd {33} 287--325.  Konstantin Makarychev and Yury Makarychev. 2017. Approximation algorithms for CSPs. See Reference Krokhin and \u017divn\u00fd {33} 287--325."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.09.002"},{"volume-title":"Algorithmic Aspects of Graph Connectivity","author":"Nagamochi Hiroshi","key":"e_1_2_1_36_1","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki . 2008. Algorithmic Aspects of Graph Connectivity . Vol. 123 . Cambridge University Press , New York . Hiroshi Nagamochi and Toshihide Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity. Vol. 123. Cambridge University Press, New York."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_40_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics , Vol. 24 . Springer . Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Vol. 24. Springer."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2974019"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33558-7_6"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258559"},{"key":"e_1_2_1_46_1","volume-title":"Vazirani and Mihalis Yannakakis","author":"Vijay","year":"1992","unstructured":"Vijay V. Vazirani and Mihalis Yannakakis . 1992 . Suboptimal cuts: Their enumeration, weight and number (extended abstract). In Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP\u201992). Springer-Verlag , 366--377. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;646246.684856. Vijay V. Vazirani and Mihalis Yannakakis. 1992. Suboptimal cuts: Their enumeration, weight and number (extended abstract). In Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP\u201992). Springer-Verlag, 366--377. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;646246.684856."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9720-9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3282429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:29Z","timestamp":1750208249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,21]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3282429"],"URL":"https:\/\/doi.org\/10.1145\/3282429","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,11,21]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}