{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:27:57Z","timestamp":1767338877674},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_55","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"653-665","source":"Crossref","is-referenced-by-count":17,"title":["Preprocessing of Min Ones Problems: A Dichotomy"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-73951-7_38","volume-title":"Algorithms and Data Structures","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N.: Kernelization algorithms for d-hitting set problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 434\u2013445. Springer, Heidelberg (2007)"},{"issue":"2","key":"55_CR2","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica\u00a052(2), 226\u2013249 (2008)","journal-title":"Algorithmica"},{"key":"55_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"key":"55_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"55_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"55_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K. Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 192\u2013202. Springer, Heidelberg (2006)"},{"key":"55_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-92800-3_2","volume-title":"Complexity of Constraints","author":"N. Creignou","year":"2008","unstructured":"Creignou, N., Vollmer, H.: Boolean constraint satisfaction problems: When does Post\u2019s lattice help? In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol.\u00a05250, pp. 3\u201337. Springer, Heidelberg (2008)"},{"key":"55_CR8","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC (to appear, 2010)","DOI":"10.1145\/1806689.1806725"},{"key":"55_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"55_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity (Monographs in Computer Science). Springer, Heidelberg (November 1998)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"55_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Rado, R.: Intersection theorems for systems of sets. J. London Math. Soc.\u00a035, 85\u201390 (1960)","journal-title":"J. London Math. Soc."},{"key":"55_CR12","first-page":"133","volume-title":"STOC","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133\u2013142. ACM, New York (2008)"},{"issue":"5","key":"55_CR13","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/060668092","volume":"39","author":"D. Harnik","year":"2010","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM J. Comput.\u00a039(5), 1667\u20131713 (2010)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"55_CR14","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2000)","journal-title":"SIAM J. Comput."},{"key":"55_CR15","series-title":"Dagstuhl Seminar Proceedings","first-page":"601","volume-title":"STACS 2009","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S.: Polynomial kernelizations for MIN F $^+{\\Pi}_1$ and MAX NP. In: STACS 2009. Dagstuhl Seminar Proceedings, vol.\u00a009001, pp. 601\u2013612. Schloss Dagstuhl, Germany (2009)"},{"key":"55_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"IWPEC","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (eds.) IWPEC. LNCS, vol.\u00a05917, pp. 264\u2013275. Springer, Heidelberg (2009)"},{"key":"55_CR17","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Preprocessing of min ones problems: a dichotomy. CoRR, abs\/0910.4518 (2009)","DOI":"10.1007\/978-3-642-14165-2_55"},{"issue":"2","key":"55_CR18","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00037-005-0195-9","volume":"14","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Parameterized complexity of constraint satisfaction problems. Computational Complexity\u00a014(2), 153\u2013183 (2005)","journal-title":"Computational Complexity"},{"key":"55_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-540-95891-8_37","volume-title":"SOFSEM 2009: Theory and Practice of Computer Science","author":"H. Moser","year":"2009","unstructured":"Moser, H.: A problem kernelization for graph packing. In: Nielsen, M., Kucera, A., Miltersen, P.B., Palamidessi, C., Tuma, P., Valencia, F.D. (eds.) SOFSEM 2009. LNCS, vol.\u00a05404, pp. 401\u2013412. Springer, Heidelberg (2009)"},{"key":"55_CR20","first-page":"216","volume-title":"STOC","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226. ACM, New York (1978)"},{"key":"55_CR21","first-page":"115","volume-title":"SODA","author":"S. Thomass\u00e9","year":"2009","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: SODA, pp. 115\u2013119. SIAM, Philadelphia (2009)"},{"key":"55_CR22","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.-K. Yap","year":"1983","unstructured":"Yap, C.-K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci.\u00a026, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T19:30:13Z","timestamp":1635622213000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}