{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:52Z","timestamp":1777596112181,"version":"3.51.4"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,5,18]],"date-time":"2013-05-18T00:00:00Z","timestamp":1368835200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00224-013-9480-1","type":"journal-article","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T01:32:35Z","timestamp":1368754355000},"page":"73-82","source":"Crossref","is-referenced-by-count":13,"title":["On the Hardness of Losing Width"],"prefix":"10.1007","volume":"54","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","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":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,18]]},"reference":[{"issue":"8","key":"9480_CR1","doi-asserted-by":"crossref","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. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9480_CR2","first-page":"629","volume-title":"FOCS","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS, pp.\u00a0629\u2013638 (2009)"},{"key":"9480_CR3","first-page":"165","volume-title":"STACS","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: STACS, pp. 165\u2013176 (2011)"},{"key":"9480_CR4","first-page":"437","volume-title":"ICALP (1)","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: ICALP (1), pp. 437\u2013448 (2011)"},{"issue":"3","key":"9480_CR5","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., van den Eijkhof, F.: Preprocessing rules for triangulation of probabilistic networks. Comput. Intell. 21(3), 286\u2013305 (2005)","journal-title":"Comput. Intell."},{"key":"9480_CR6","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels. Technical Report UU-CS-2008-030, Institute of Information and Computing Sciences, Utrecht University, The Netherlands (2008)"},{"issue":"35","key":"9480_CR7","doi-asserted-by":"crossref","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. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9480_CR8","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory (2005)"},{"key":"9480_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"ICALP (1)","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and ids. In: ICALP (1). Lecture Notes in Computer Science, vol. 5555, pp. 378\u2013389 (2009)"},{"key":"9480_CR10","first-page":"189","volume-title":"STACS","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: approximation and kernelization. In: STACS, pp. 189\u2013200 (2011)"},{"key":"9480_CR11","first-page":"503","volume-title":"SODA","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510 (2010)"},{"issue":"1","key":"9480_CR12","doi-asserted-by":"crossref","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"9480_CR13","first-page":"177","volume-title":"STACS","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter. In: STACS, pp. 177\u2013188 (2011)"},{"key":"9480_CR14","first-page":"90","volume-title":"FCT","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. In: FCT, pp. 90\u2013101 (2011)"},{"key":"9480_CR15","first-page":"777","volume-title":"SODA","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal. In: SODA, pp. 777\u2013789 (2011)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9480-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9480-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9480-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:25Z","timestamp":1558684465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9480-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,18]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9480"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9480-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,18]]}}}