{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:14Z","timestamp":1725897734522},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_22","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T17:20:21Z","timestamp":1340385621000},"page":"254-265","source":"Crossref","is-referenced-by-count":11,"title":["Clique Cover and Graph Separation: New Incompressibility Results"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Wahlstr\u00f6m, M.: Clique cover and graph separation: New incompressibility results. CoRR abs\/1111.0570 (2011)","DOI":"10.1007\/978-3-642-31594-7_22"},{"issue":"5","key":"22_CR2","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":"1","key":"22_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"8","key":"22_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"22_CR6","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.\u00a077(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"22_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J. Cai","year":"2005","unstructured":"Cai, J., Chakaravarthy, V.T., Hemaspaandra, L.A., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Inf. Comput.\u00a0198(1), 1\u201323 (2005)","journal-title":"Inf. Comput."},{"key":"22_CR8","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."},{"key":"22_CR9","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: STACS 2011, pp. 165\u2013176 (2011)"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC 2010, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: SODA 2012, pp. 68\u201381 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: SODA 2012, pp. 104\u2013113 (2012)","DOI":"10.1137\/1.9781611973099.9"},{"issue":"35","key":"22_CR13","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci.\u00a0412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-16926-7_15","volume-title":"Graph Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 147\u2013158. Springer, Heidelberg (2010)"},{"key":"22_CR15","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":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-22006-7_37","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for Treewidth: A Combinatorial Analysis Through Kernelization. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 437\u2013448. Springer, Heidelberg (2011)"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032, 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"22_CR18","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: STOC 2011, pp. 459\u2013468 (2011)","DOI":"10.1145\/1993636.1993698"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: SODA 2012, pp. 1713\u20131725 (2012)","DOI":"10.1137\/1.9781611973099.136"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC 2011, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: The minimum k-way cut of bounded size is fixed-parameter tractable. In: FOCS 2011, pp. 160\u2013169 (2011)","DOI":"10.1109\/FOCS.2011.53"},{"key":"22_CR23","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"2","key":"22_CR24","first-page":"544","volume":"16","author":"E. Kellerman","year":"1973","unstructured":"Kellerman, E.: Determination of keyword conflict. IBM Technical Disclosure Bulletin\u00a016(2), 544\u2013546 (1973)","journal-title":"IBM Technical Disclosure Bulletin"},{"key":"22_CR25","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF02574385","volume":"12","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Alon, N., Aronov, B., Suri, S.: Can visibility graphs be represented compactly? Discrete & Computational Geometry\u00a012, 347\u2013365 (1994)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"22_CR26","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1016\/j.csda.2006.09.035","volume":"52","author":"J. Gramm","year":"2007","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R., Piepho, H.P., Schmid, R.: Algorithms for compact letter displays: Comparison and evaluation. Computational Statistics & Data Analysis\u00a052(2), 725\u2013736 (2007)","journal-title":"Computational Statistics & Data Analysis"},{"issue":"2","key":"22_CR27","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1198\/1061860043515","volume":"13","author":"H.P. Piepho","year":"2004","unstructured":"Piepho, H.P.: An algorithm for a letter-based representation of all-pairwise comparisons. Journal of Computational and Graphical Statistics\u00a013(2), 456\u2013466 (2004)","journal-title":"Journal of Computational and Graphical Statistics"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Rajagopalan, S., Vachharajani, M., Malik, S.: Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints. In: CASES 2000, pp. 157\u2013164 (2000)","DOI":"10.1145\/354880.354902"},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Data reduction and exact algorithms for clique cover. ACM Journal of Experimental Algorithmics\u00a013 (2008)","DOI":"10.1145\/1412228.1412236"},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In: SODA 2012, pp. 94\u2013103 (2012)","DOI":"10.1137\/1.9781611973099.8"},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: CoRR abs\/1111.2195 (2011)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"5","key":"22_CR32","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0167-6377(97)00043-6","volume":"21","author":"M. Burlet","year":"1997","unstructured":"Burlet, M., Goldschmidt, O.: A new and improved algorithm for the 3-cut problem. Oper. Res. Lett.\u00a021(5), 225\u2013227 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"22_CR33","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res.\u00a019(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"22_CR34","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Minimum k-way cuts via deterministic greedy tree packing. In: STOC 2008, pp. 159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"22_CR35","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"R.G. Downey","year":"2003","unstructured":"Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci.\u00a078, 209\u2013222 (2003)","journal-title":"Electr. Notes 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-31594-7_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:14:53Z","timestamp":1620116093000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}