{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:16Z","timestamp":1784568316628,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,4,26]],"date-time":"2020-04-26T00:00:00Z","timestamp":1587859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>Unlike polynomial kernelization in general, for which many non-trivial results and methods exist, only few non-trival algorithms are known for polynomial-time sparsification. Furthermore, excepting problems on restricted inputs (such as graph problems on planar graphs), most such results rely upon encoding the instance as a system of bounded-degree polynomial equations. In particular, for satisfiability (SAT) problems with a fixed constraint language \u0393, every previously known result is captured by this approach; for several such problems, this is known to be tight. In this work, we investigate the limits of this approach\u2014in particular, does it really cover all cases of non-trivial polynomial-time sparsification?<\/jats:p>\n          <jats:p>\n            We generalize the method using tools from the algebraic approach to constraint satisfaction problems (CSP). Every constraint that can be modelled via a system of linear equations, over some finite field F, also admits a finite domain extension to a tractable CSP with a Maltsev polymorphism; using known algorithms for Maltsev languages, we can show that every problem of the latter type admits a \u201cbasis\u201d of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) constraints, which implies a linear sparsification for the original problem. This generalization appears to be strict; other special cases include constraints modelled via group equations over some finite group\n            <jats:italic>G<\/jats:italic>\n            . For sparsifications of polynomial but super-linear size, we consider two extensions of this. Most directly, we can capture systems of bounded-degree polynomial equations in a \u201clift-and-project\u201d manner, by finding Maltsev extensions for constraints over\n            <jats:italic>c<\/jats:italic>\n            -tuples of variables, for a basis with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>c<\/jats:sup>\n            <\/jats:italic>\n            ) constraints. Additionally, we may use extensions with\n            <jats:italic>k<\/jats:italic>\n            -edge polymorphisms instead of requiring a Maltsev polymorphism.\n          <\/jats:p>\n          <jats:p>\n            We also investigate characterizations of when such extensions exist. We give an infinite sequence of partial polymorphisms \u03c6\n            <jats:sub>1<\/jats:sub>\n            , \u03c6\n            <jats:sub>2<\/jats:sub>\n            , \u2026which characterizes whether a language \u0393 has a Maltsev extension (of possibly infinite domain). In the complementary direction of proving lower bounds on kernelizability, we prove that for any language not preserved by \u03c6\n            <jats:sub>1<\/jats:sub>\n            , the corresponding SAT problem does not admit a kernel of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\u2212\u03b5<\/jats:sup>\n            ) for any \u03b5 &gt; 0 unless the polynomial hierarchy collapses.\n          <\/jats:p>","DOI":"10.1145\/3389411","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T14:53:21Z","timestamp":1588604001000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Sparsification of SAT and CSP Problems via Tractable Extensions"],"prefix":"10.1145","volume":"12","author":[{"given":"Victor","family":"Lagerkvist","sequence":"first","affiliation":[{"name":"Link\u00f6ping University, Link\u00f6ping, \u00d6sterg\u00f6tland, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham Hill, Egham, Great Britain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2677161.2677165"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04874-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01267873"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1113115.1710990"},{"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\/050628957"},{"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.1137\/120882160"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"S. Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Springer-Verlag Berlin Germany.  S. Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC-2018)","volume":"115","author":"Chen H."},{"key":"e_1_2_1_12_1","volume-title":"Lecture Notes in Computer Science","volume":"5250","author":"Creignou N."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"M. Cygan F. V. Fomin L. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer New York NY.  M. Cygan F. V. Fomin L. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer New York NY.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00342-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_18_1","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"Fomin F. V.","year":"2019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2100-2"},{"key":"e_1_2_1_21_1","volume-title":"A Shorter Model Theory","author":"Hodges W."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016)","volume":"58","author":"Jansen B. M. P."},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Optimal data reduction for graph coloring using low-degree polynomials. In IPEC (LIPIcs), Vol. 89. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Oktavie-Allee, 66687 Wadern","volume":"22","author":"Jansen B. M. P.","year":"2017","journal-title":"Germany"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0189-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 1st International Conference in Principles and Practice of Constraint Programming (CP-1995)","author":"Jeavons P."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.07.008"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858787"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 7th International Colloquium on Automata, Languages and Programming (ICALP-2010)","volume":"6198","author":"Kratsch S."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151182"},{"key":"e_1_2_1_33_1","first-page":"1465","article-title":"The power of primitive positive definitions with polynomially many variables","volume":"27","author":"Lagerkvist V.","year":"2017","journal-title":"J. Logic Comput."},{"key":"e_1_2_1_34_1","unstructured":"V. Lagerkvist and M. Wahlstr\u00f6m. 2018. Which NP-Hard SAT and CSP problems admit exponentially improved algorithms? CoRR abs\/1801.09488 (2018). arxiv:1801.09488 http:\/\/arxiv.org\/abs\/1801.09488.  V. Lagerkvist and M. Wahlstr\u00f6m. 2018. Which NP-Hard SAT and CSP problems admit exponentially improved algorithms? CoRR abs\/1801.09488 (2018). arxiv:1801.09488 http:\/\/arxiv.org\/abs\/1801.09488."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015)","author":"Lagerkvist V."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01069627"},{"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":"Automation of Reasoning: 2: Classical Papers on Computational Logic 1967--1970","author":"Tseitin G. S."},{"key":"e_1_2_1_41_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\/3389411","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3389411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:31Z","timestamp":1750200091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,26]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3389411"],"URL":"https:\/\/doi.org\/10.1145\/3389411","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,26]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}