{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T02:48:32Z","timestamp":1767494912762,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T00:00:00Z","timestamp":1578614400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T00:00:00Z","timestamp":1578614400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00453-019-00660-y","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:03:56Z","timestamp":1578650636000},"page":"2200-2242","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Best-Case and Worst-Case Sparsifiability of Boolean CSPs"],"prefix":"10.1007","volume":"82","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[]},{"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3721-6721","authenticated-orcid":false,"given":"Astrid","family":"Pieterse","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,10]]},"reference":[{"issue":"1","key":"660_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014). https:\/\/doi.org\/10.1137\/120880240","journal-title":"SIAM J. Discrete Math."},{"issue":"35","key":"660_CR2","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2011.04.039","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"660_CR3","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/S0097539700376676","journal-title":"SIAM J. Comput."},{"key":"660_CR4","doi-asserted-by":"publisher","DOI":"10.1145\/1189056.1189076","author":"HA Chen","year":"2009","unstructured":"Chen, H.A.: A rendezvous of logic, complexity, and algebra. ACM Comput. Surv. (2009). https:\/\/doi.org\/10.1145\/1189056.1189076","journal-title":"ACM Comput. Surv."},{"key":"660_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"660_CR6","doi-asserted-by":"publisher","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of 23rd SODA, pp. 68\u201381 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.6","DOI":"10.1137\/1.9781611973099.6"},{"issue":"4","key":"660_CR7","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014). https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"key":"660_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlim (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"5","key":"660_CR9","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/130927115","volume":"44","author":"A Drucker","year":"2015","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443\u20131479 (2015). https:\/\/doi.org\/10.1137\/130927115","journal-title":"SIAM J. Comput."},{"key":"660_CR10","volume-title":"Finite-Dimensional Linear Algebra. Discrete Mathematics and Its Applications","author":"M Gockenbach","year":"2011","unstructured":"Gockenbach, M.: Finite-Dimensional Linear Algebra. Discrete Mathematics and Its Applications. Taylor & Francis, Abingdon (2011)"},{"issue":"3","key":"660_CR11","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s00453-014-9924-2","volume":"71","author":"BMP Jansen","year":"2015","unstructured":"Jansen, B.M.P.: On sparsification for computing treewidth. Algorithmica 71(3), 605\u2013635 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9924-2","journal-title":"Algorithmica"},{"key":"660_CR12","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. In: Proceedings of 41st MFCS, pp. 71:1\u201371:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.71","DOI":"10.4230\/LIPIcs.MFCS.2016.71"},{"key":"660_CR13","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Pieterse, A.: Optimal data reduction for graph coloring using low-degree polynomials. In: Proceedings of 12th IPEC, pp. 22:1\u201322:12 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.22","DOI":"10.4230\/LIPIcs.IPEC.2017.22"},{"issue":"1","key":"660_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-016-0189-9","volume":"79","author":"BMP Jansen","year":"2017","unstructured":"Jansen, B.M.P., Pieterse, A.: Sparsification upper and lower bounds for graph problems and not-all-equal SAT. Algorithmica 79(1), 3\u201328 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0189-9","journal-title":"Algorithmica"},{"key":"660_CR15","unstructured":"Jansen, B.M.P., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. CoRR abs\/1606.03233 (2018). arXiv:1606.03233v2"},{"issue":"4","key":"660_CR16","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0208040","volume":"8","author":"R Kannan","year":"1979","unstructured":"Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499\u2013507 (1979). https:\/\/doi.org\/10.1137\/0208040","journal-title":"SIAM J. Comput."},{"issue":"3","key":"660_CR17","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1145\/2832912","volume":"12","author":"S Kratsch","year":"2016","unstructured":"Kratsch, S., Philip, G., Ray, S.: Point line cover: the easy kernel is essentially tight. ACM Trans. Algorithms 12(3), 40:1\u201340:16 (2016). https:\/\/doi.org\/10.1145\/2832912","journal-title":"ACM Trans. Algorithms"},{"issue":"9","key":"660_CR18","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1016\/j.ipl.2014.03.011","volume":"114","author":"V Lagerkvist","year":"2014","unstructured":"Lagerkvist, V.: Weak bases of Boolean co-clones. Inf. Process. Lett. 114(9), 462\u2013468 (2014). https:\/\/doi.org\/10.1016\/j.ipl.2014.03.011","journal-title":"Inf. Process. Lett."},{"key":"660_CR19","doi-asserted-by":"publisher","unstructured":"Lagerkvist, V., Wahlstr\u00f6m, M.: Kernelization of constraint satisfaction problems: a study through universal algebra. In: Proceedings of 23rd CP, pp. 157\u2013171 (2017). https:\/\/doi.org\/10.1007\/978-3-319-66158-2_11","DOI":"10.1007\/978-3-319-66158-2_11"},{"key":"660_CR20","unstructured":"Lagerkvist, V., Wahlstr\u00f6m, M.: Kernelization of constraint satisfaction problems: a study through universal algebra. CoRR abs\/1706.05941 (2017). arXiv:1706.05941"},{"key":"660_CR21","unstructured":"Lagerkvist, V., Wahlstr\u00f6m, M.: Which NP-hard SAT and CSP problems admit exponentially improved algorithms? CoRR abs\/1801.09488 (2018). arXiv:1801.09488v1"},{"key":"660_CR22","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization\u2014preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond, pp. 129\u2013161 (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_10","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"660_CR23","unstructured":"Lov\u00e1sz, L.: Chromatic number of hypergraphs and linear algebra. In: Studia Scientiarum Mathematicarum Hungarica 11, pp. 113\u2013114 (1976). http:\/\/real-j.mtak.hu\/5461\/"},{"key":"660_CR24","doi-asserted-by":"publisher","unstructured":"Nordh, G., Zanuttini, B.: Frozen Boolean partial co-clones. In: Proceedings of 39th International Symposium on Multiple-Valued Logic, pp. 120\u2013125. IEEE Computer Society (2009). https:\/\/doi.org\/10.1109\/ISMVL.2009.10","DOI":"10.1109\/ISMVL.2009.10"},{"key":"660_CR25","doi-asserted-by":"publisher","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of 10th STOC, pp. 216\u2013226 (1978). https:\/\/doi.org\/10.1145\/800133.804350","DOI":"10.1145\/800133.804350"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00660-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00660-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00660-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,9]],"date-time":"2021-01-09T03:54:11Z","timestamp":1610164451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00660-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,10]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["660"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00660-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,10]]},"assertion":[{"value":"1 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}