{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313069,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T00:00:00Z","timestamp":1592956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T00:00:00Z","timestamp":1592956800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["714532"],"award-info":[{"award-number":["714532"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00453-020-00735-1","type":"journal-article","created":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T13:03:41Z","timestamp":1593003821000},"page":"3492-3520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs"],"prefix":"10.1007","volume":"82","author":[{"given":"Gregor","family":"Matl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,24]]},"reference":[{"issue":"1","key":"735_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2556646","volume":"61","author":"L Barto","year":"2014","unstructured":"Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. J. ACM 61(1), 1\u201319 (2014) (Article No. 3)","journal-title":"J. ACM"},{"issue":"12","key":"735_CR2","doi-asserted-by":"crossref","first-page":"1680","DOI":"10.1016\/j.dam.2012.03.029","volume":"160","author":"M Bodirsky","year":"2012","unstructured":"Bodirsky, M., K\u00e1ra, J., Martin, B.: The complexity of surjective homomorphism problems\u2014a survey. Discrete Appl. Math. 160(12), 1680\u20131690 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"735_CR3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"issue":"3","key":"735_CR4","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"735_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201917), pp. 319\u2013330 (2017)","DOI":"10.1109\/FOCS.2017.37"},{"issue":"4","key":"735_CR6","doi-asserted-by":"crossref","first-page":"419","DOI":"10.2168\/LMCS-6(4:4)2010","volume":"6","author":"AA Bulatov","year":"2010","unstructured":"Bulatov, A.A., Marx, D.: The complexity of global cardinality constraints. Log. Methods Comput. Sci. 6(4), 419\u2013428 (2010)","journal-title":"Log. Methods Comput. Sci."},{"issue":"11","key":"735_CR7","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"DA Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The complexity of soft constraint satisfaction. Artif. Intell. 170(11), 983\u20131016 (2006)","journal-title":"Artif. Intell."},{"key":"735_CR8","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N Creignou","year":"1997","unstructured":"Creignou, N., H\u00e9brard, J.-J.: On generating all solutions of generalized satisfiability problems. Inf. Th\u00e9or. Appl. 31, 499\u2013511 (1997)","journal-title":"Inf. Th\u00e9or. Appl."},{"issue":"4","key":"735_CR9","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"735_CR10","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Pearson, J.: Set functions and width 1 problems. In: Proceedings of the 5th International Conference on Constraint Programming (CP\u201999), Volume 1713 of Lecture Notes in Computer Science, pp. 159\u2013173. Springer, Berlin (1999)","DOI":"10.1007\/978-3-540-48085-3_12"},{"issue":"1","key":"735_CR11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic snp and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"735_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3282429","volume":"11","author":"P Fulla","year":"2018","unstructured":"Fulla, P., Uppman, H., \u017divn\u00fd, S.: The complexity of Boolean surjective general-valued CSPs. ACM Trans. Comput. Theory 11(1), 1\u201331 (2018) (Article No. 4)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"735_CR13","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"735_CR14","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Comb. Theory Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"735_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.cosrev.2008.10.003","volume":"2","author":"P Hell","year":"2008","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Colouring, constraint satisfaction, and complexity. Comput. Sci. Rev. 2(3), 143\u2013163 (2008)","journal-title":"Comput. Sci. Rev."},{"key":"735_CR16","doi-asserted-by":"crossref","unstructured":"Huber, A., Kolmogorov, V.: Towards minimizing $$k$$-submodular functions. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO\u201912), Volume 7422 of Lecture Notes in Computer Science, pp. 451\u2013462. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32147-4_40"},{"issue":"4","key":"735_CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"key":"735_CR18","unstructured":"Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-out algorithm. In: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993), pp. 21\u201330 (1993)"},{"issue":"3","key":"735_CR19","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1137\/16M1091836","volume":"46","author":"V Kolmogorov","year":"2017","unstructured":"Kolmogorov, V., Krokhin, A., Rol\u00ednek, M.: The complexity of general-valued CSPs. SIAM J. Comput. 46(3), 1087\u20131110 (2017)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"735_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V., Thapper, J., \u017divn\u00fd, S.: The power of linear programming for general-valued CSPs. SIAM J. Comput. 44(1), 1\u201336 (2015)","journal-title":"SIAM J. Comput."},{"key":"735_CR21","doi-asserted-by":"crossref","unstructured":"Kozik, M., Ochremiak, J.: Algebraic properties of valued constraint satisfaction problem. In: Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP\u201915), Volume 9134 of Lecture Notes in Computer Science, pp. 846\u2013858. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"735_CR22","unstructured":"Matl, G., \u017divn\u00fd, S.: Beyond Boolean surjective VCSPs. In: Proceedings of the 36th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201919), pp. 48:1\u201348:15 (2019)"},{"volume-title":"The Handbook of Constraint Programming","year":"2006","key":"735_CR23","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.): The Handbook of Constraint Programming. Elsevier, London (2006)"},{"key":"735_CR24","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978), pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"735_CR25","unstructured":"Schiex, T., Fargier, H., Verfaillie, G.: Valued constraint satisfaction problems: hard and easy problems. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI\u201995), pp. 631\u2013637 (1995)"},{"key":"735_CR26","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"issue":"4","key":"735_CR27","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1137\/16M1079245","volume":"46","author":"J Thapper","year":"2017","unstructured":"Thapper, J., \u017divn\u00fd, S.: The power of Sherali\u2013Adams relaxations for general-valued CSPs. SIAM J. Comput. 46(4), 1241\u20131279 (2017)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"735_CR28","doi-asserted-by":"crossref","first-page":"37:1","DOI":"10.1145\/2974019","volume":"63","author":"J Thapper","year":"2016","unstructured":"Thapper, J., \u017d\u017divn\u00fd, S.: The complexity of finite-valued CSPs. J. ACM 63(4), 37:1\u201337:33 (2016)","journal-title":"J. ACM"},{"key":"735_CR29","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201917), pp. 331\u2013342 (2017)","DOI":"10.1109\/FOCS.2017.38"},{"key":"735_CR30","unstructured":"Zhuk, D.: No-rainbow problem is NP-hard. Technical Report (2020)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00735-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00735-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00735-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,24]],"date-time":"2021-06-24T01:09:27Z","timestamp":1624496967000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00735-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,24]]},"references-count":30,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["735"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00735-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,6,24]]},"assertion":[{"value":"11 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}