{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:21Z","timestamp":1750221021112,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714532"],"award-info":[{"award-number":["714532"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JST CREST","award":["JPMJCR14D2"],"award-info":[{"award-number":["JPMJCR14D2"]}]},{"name":"JSPS KAKENHI","award":["25280004, 26330023, 17K00029, 26280004"],"award-info":[{"award-number":["25280004, 26330023, 17K00029, 26280004"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and \u017divn\u00fd classified the tractability of binary VCSP instances according to the concept of \u201ctriangle,\u201d and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and \u017divn\u00fd made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given.<\/jats:p><jats:p>In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.<\/jats:p>","DOI":"10.1145\/3329862","type":"journal-article","created":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T12:39:01Z","timestamp":1563280741000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Tractable Class of Binary VCSPs via M-Convex Intersection"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4784-5110","authenticated-orcid":false,"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6794-3543","authenticated-orcid":false,"given":"Yuni","family":"Iwamasa","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}]},{"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[{"name":"Tokyo Metropolitan University, Tokyo, Japan;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"U. Bertel\u00e9 and F. Brioschi. 1972. Nonserial Dynamic Programming. Academic Press. U. Bertel\u00e9 and F. Brioschi. 1972. Nonserial Dynamic Programming. Academic Press."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00341-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90216-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.02.003"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387933.2387943"},{"key":"e_1_2_1_7_1","series-title":"Dagstuhl Follow-Ups Series","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","author":"Cooper M. C.","unstructured":"M. C. Cooper and S. \u017divn\u00fd . 2017. Hybrid tractable classes of constraint problems . In The Constraint Satisfaction Problem: Complexity and Approximability , Dagstuhl Follow-Ups Series , Vol. 7 , A. Krokhin and S. \u017divn\u00fd (Eds.), Chap. 4, Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik , 113--135. M. C. Cooper and S. \u017divn\u00fd. 2017. Hybrid tractable classes of constraint problems. In The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups Series, Vol. 7, A. Krokhin and S. \u017divn\u00fd (Eds.), Chap. 4, Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, 113--135."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Y. Crama and P. L. Hammer. 2011. Boolean Functions\u2014Theory Algorithms and Applications. Cambridge University Press Cambridge. Y. Crama and P. L. Hammer. 2011. Boolean Functions\u2014Theory Algorithms and Applications. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511852008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Springer Heidelberg. M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Springer Heidelberg.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(90)90009-Z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(92)90028-J"},{"volume-title":"Submodular functions, matroids, and certain polyhedra","author":"Edmonds J.","key":"e_1_2_1_12_1","unstructured":"J. Edmonds . 1970. Submodular functions, matroids, and certain polyhedra . In Combinatorial Structures and Their Applications, Gordon and Breach (Eds.), New York , 69--87. J. Edmonds. 1970. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, Gordon and Breach (Eds.), New York, 69--87."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116654.3116942"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0824-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.61.71"},{"volume-title":"Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918)","author":"Hirai H.","key":"e_1_2_1_16_1","unstructured":"H. Hirai and Y. Iwamasa . 2018. Reconstructing phylogenetic tree from multipartite quartet system . In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918) . H. Hirai and Y. Iwamasa. 2018. Reconstructing phylogenetic tree from multipartite quartet system. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC\u201918)."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918), Leibniz International Proceedings in Informatics","volume":"96","author":"Hirai H.","year":"2018","unstructured":"H. Hirai , Y. Iwamasa , K. Murota , and S. \u017divn\u00fd . 2018 . Beyond JWP: A tractable class of binary VCSPs via M-convex intersection . In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918), Leibniz International Proceedings in Informatics , Vol. 96 , 39:1--39:14. H. Hirai, Y. Iwamasa, K. Murota, and S. \u017divn\u00fd. 2018. Beyond JWP: A tractable class of binary VCSPs via M-convex intersection. In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS\u201918), Leibniz International Proceedings in Informatics, Vol. 96, 39:1--39:14."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167590"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.004"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2018.01.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_2_1_23_1","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte B.","year":"2010","unstructured":"B. Korte and J. Vygen . 2010 . Combinatorial Optimization: Theory and Algorithms ( 5 th ed.). Springer , Heidelberg . B. Korte and J. Vygen. 2010. Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer, Heidelberg.","edition":"5"},{"key":"e_1_2_1_24_1","unstructured":"A. Krokhin and S. \u017divn\u00fd editors. 2017. The Constraint Satisfaction Problem: Complexity and Approximability Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik Vol. 7. Dagstuhl Follow-Ups Series. A. Krokhin and S. \u017divn\u00fd editors. 2017. The Constraint Satisfaction Problem: Complexity and Approximability Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik Vol. 7. Dagstuhl Follow-Ups Series."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1996.0084"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195279994"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195280009"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02680565"},{"volume-title":"Matrices and Matroids for Systems Analysis","author":"Murota K.","key":"e_1_2_1_29_1","unstructured":"K. Murota . 2000. Matrices and Matroids for Systems Analysis . Springer , Heidelberg . K. Murota. 2000. Matrices and Matroids for Systems Analysis. Springer, Heidelberg."},{"volume-title":"Discrete Convex Analysis","author":"Murota K.","key":"e_1_2_1_30_1","unstructured":"K. Murota . 2003. Discrete Convex Analysis . SIAM , Philadelphia . K. Murota. 2003. Discrete Convex Analysis. SIAM, Philadelphia."},{"volume-title":"Research Trends in Combinatorial Optimization","author":"Murota K.","key":"e_1_2_1_31_1","unstructured":"K. Murota . 2009. Recent developments in discrete convex analysis . In Research Trends in Combinatorial Optimization , W. Cook, L. Lov\u00e1sz, and J. Vygen (Eds.), Chap. 11, Springer , Heidelberg, 219--260. K. Murota. 2009. Recent developments in discrete convex analysis. In Research Trends in Combinatorial Optimization, W. Cook, L. Lov\u00e1sz, and J. Vygen (Eds.), Chap. 11, Springer, Heidelberg, 219--260."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.22574\/jmid.2016.12.005"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2003.11.001"},{"volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","key":"e_1_2_1_34_1","unstructured":"A. Schrijver . 2003. Combinatorial Optimization: Polyhedra and Efficiency . Springer , Heidelberg . A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"C. Semple and M. Steel. 2003. Phylogenetics. Oxford University Press Oxford. C. Semple and M. Steel. 2003. Phylogenetics. Oxford University Press Oxford.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(77)90351-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"},{"volume-title":"The Complexity of Valued Constraint Satisfaction Problems","author":"\u017divn\u00fd S.","key":"e_1_2_1_39_1","unstructured":"S. \u017divn\u00fd . 2012. The Complexity of Valued Constraint Satisfaction Problems . Springer , Heidelberg . S. \u017divn\u00fd. 2012. The Complexity of Valued Constraint Satisfaction Problems. Springer, Heidelberg."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329862","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3329862","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:23Z","timestamp":1750206383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3329862"],"URL":"https:\/\/doi.org\/10.1145\/3329862","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}