{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:53Z","timestamp":1750219973282,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014013","name":"UKRI","doi-asserted-by":"crossref","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Royal Society University Research Fellowship"},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.<\/jats:p>\n          <jats:p>Baker\u2019s approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and \u017divn\u00fd\u00a0[SODA\u201921] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general \u201csparsity\u201d condition for which a PTAS is known. We extend these results to general-valued CSPs, which include \u201ccrisp\u201d (or \u201cstrict\u201d) constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element that is at least as feasible as all the others (but possibly less valuable).<\/jats:p>\n          <jats:p>\n            For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all\n            <jats:italic>Baker<\/jats:italic>\n            graph classes\u2014a definition by Dvo\u0159\u00e1k\u00a0[SODA\u201920] that encompasses all classes where Baker\u2019s technique is known to work, except for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to\n            <jats:italic>diagonalisability<\/jats:italic>\n            \u2014a property of relational structures connected to logics, statistical physics, and random CSPs.\n          <\/jats:p>","DOI":"10.1145\/3569956","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T12:22:21Z","timestamp":1670934141000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["PTAS for Sparse General-valued CSPs"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6796-4814","authenticated-orcid":false,"given":"Bal\u00e1zs F.","family":"Mezei","sequence":"first","affiliation":[{"name":"\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":false,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"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, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48523-6_17"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167161"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.10.001"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1935"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/19m1250121"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.4"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90236-8"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.001"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"volume-title":"Personal communication","author":"Dvo\u0159\u00e1k Zden\u011bk","key":"e_1_3_4_15_2","unstructured":"Zden\u011bk Dvo\u0159\u00e1k. Personal communication. 2021. One construction is as follows: start with an arbitrarily large integer m and for i from m down to 1, introduce an independent set of i new vertices and connect them via paths of length i to all previous vertices."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.09.001"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.137"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.37236\/8909"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3282429"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0010-x"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.012"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_51"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/100783856"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0903"},{"key":"e_1_3_4_28_2","article-title":"The complexity of valued constraint satisfaction","volume":"113","author":"Jeavons Peter","year":"2014","unstructured":"Peter Jeavons, Andrei A. Krokhin, and Stanislav \u017divn\u00fd. 2014. The complexity of valued constraint satisfaction. Bull. EATCS 113 (2014). Retrieved from http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/266.","journal-title":"Bull. EATCS"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.022"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/060669231"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_10"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237979"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.121"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.11"},{"key":"e_1_3_4_39_2","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC\u201997)","author":"Marathe Madhav V.","year":"1997","unstructured":"Madhav V. Marathe, Harry B. Hunt III, and Richard E. Stearns. 1997. Level-treewidth property, exact algorithms and approximation schemes. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC\u201997). ACM. Retrieved from https:\/\/www.osti.gov\/biblio\/471394."},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470599"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.91"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-22444-0_4"},{"key":"e_1_3_4_44_2","volume-title":"Treewidth-Pliability and PTAS for Max-CSPs","author":"Romero Miguel","year":"2020","unstructured":"Miguel Romero, Marcin Wrochna, and Stanislav \u017divn\u00fd. 2020. Treewidth-Pliability and PTAS for Max-CSPs. Technical Report. arXiv:1911.03204."},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.29"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2010.2493"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:19Z","timestamp":1750182559000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3569956"],"URL":"https:\/\/doi.org\/10.1145\/3569956","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"assertion":[{"value":"2021-04-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}