{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:12Z","timestamp":1784568312613,"version":"3.55.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T00:00:00Z","timestamp":1471824000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"\u201cNWO Veni grant \u201cFrontiers in Parameterized Preprocessing\u201d","award":["639.021.437"],"award-info":[{"award-number":["639.021.437"]}]},{"name":"\u201cNWO Gravitation grant \u201cNetworks\u201d","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0189-9","type":"journal-article","created":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T11:25:31Z","timestamp":1471865131000},"page":"3-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT"],"prefix":"10.1007","volume":"79","author":[{"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3721-6721","authenticated-orcid":false,"given":"Astrid","family":"Pieterse","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,22]]},"reference":[{"issue":"8","key":"189_CR1","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009). doi:\n                        10.1016\/j.jcss.2009.04.001","journal-title":"J. Comput. Syst. Sci."},{"key":"189_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2012.09.006","volume":"511","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. Theor. Comput. Sci. 511, 117\u2013136 (2013). doi:\n                        10.1016\/j.tcs.2012.09.006","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"189_CR3","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. Discret. Math. 28(1), 277\u2013305 (2014). doi:\n                        10.1137\/120880240","journal-title":"SIAM J. Discret. Math."},{"issue":"35","key":"189_CR4","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). doi:\n                        10.1016\/j.tcs.2011.04.039","journal-title":"Theor. Comput. Sci."},{"key":"189_CR5","doi-asserted-by":"publisher","unstructured":"Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. In: Proceedings of 21st ESA, pp. 361\u2013372 (2013). doi:\n                        10.1007\/978-3-642-40450-4_31","DOI":"10.1007\/978-3-642-40450-4_31"},{"key":"189_CR6","doi-asserted-by":"publisher","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Fernau, H., Prieto, E., Rosamond, F.A.: NONBLOCKER: parameterized algorithmics for minimum dominating set. In: Proceedings of 32nd SOFSEM, pp. 237\u2013245 (2006). doi:\n                        10.1007\/11611257_21","DOI":"10.1007\/11611257_21"},{"key":"189_CR7","doi-asserted-by":"publisher","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of 23rd SODA, pp. 68\u201381 (2012). doi:\n                        10.1137\/1.9781611973099.6","DOI":"10.1137\/1.9781611973099.6"},{"issue":"4","key":"189_CR8","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). doi:\n                        10.1145\/2629620","journal-title":"J. ACM"},{"issue":"2","key":"189_CR9","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014). doi:\n                        10.1145\/2650261","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"189_CR10","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification\u2014a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669\u2013696 (1997). doi:\n                        10.1145\/265910.265914","journal-title":"J. ACM"},{"key":"189_CR11","unstructured":"Estivill-Castro, V., Fellows, M., Langston, M., Rosamond, F.: FPT is P-time extremal structure I. In: Proceedings of 1st ACiD, pp. 1\u201341 (2005)"},{"issue":"4","key":"189_CR12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2635820","volume":"6","author":"MR Fellows","year":"2014","unstructured":"Fellows, M.R., Jansen, B.M.P.: FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders. ACM Trans. Comput. Theory 6(4), 16 (2014). doi:\n                        10.1145\/2635820","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"189_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011). doi:\n                        10.1016\/j.jcss.2010.06.007","journal-title":"J. Comput. Syst. Sci."},{"key":"189_CR14","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman, New York (1979)"},{"key":"189_CR15","doi-asserted-by":"publisher","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of 23rd SODA, pp. 104\u2013113 (2012). doi:\n                        10.1137\/1.9781611973099.9","DOI":"10.1137\/1.9781611973099.9"},{"issue":"4","key":"189_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). doi:\n                        10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"189_CR17","unstructured":"Jansen, B.M., Pieterse, A.: Optimal sparsification for some binary CSPs using low-degree polynomials. In: Proceedings of 41st MFCS (To appear) (2016)"},{"issue":"3","key":"189_CR18","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). doi:\n                        10.1007\/s00453-014-9924-2","journal-title":"Algorithmica"},{"key":"189_CR19","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70\u201388 (2013). doi:\n                        10.1016\/j.ic.2013.08.005","journal-title":"Inf. Comput."},{"key":"189_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"189_CR21","unstructured":"Lov\u00e1sz, L.: Chromatic number of hypergraphs and linear algebra. In: Studia Scientiarum Mathematicarum Hungarica 11, pp. 113\u2013114 (1976). \n                        http:\/\/real-j.mtak.hu\/5461\/"},{"key":"189_CR22","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Jr, L.E.T.: Vertex packings: structural properties and algorithms. Math. Program. 8, 232\u2013248 (1975). doi:\n                        10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"189_CR23","first-page":"461","volume":"5","author":"B Toft","year":"1970","unstructured":"Toft, B.: On the maximal number of edges of critical \n                        $$k$$\n                        \n                            \n                                            \n                                k\n                            \n                        \n                    -chromatic graphs. Studia Scientiarum Mathematicarum Hungarica 5, 461\u2013470 (1970)","journal-title":"Studia Scientiarum Mathematicarum Hungarica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0189-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0189-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0189-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0189-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T12:20:05Z","timestamp":1500380405000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0189-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,22]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["189"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0189-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,22]]}}}