{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T03:59:47Z","timestamp":1770436787245,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642169250","type":"print"},{"value":"9783642169267","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_19","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"196-207","source":"Crossref","is-referenced-by-count":16,"title":["A Quartic Kernel for Pathwidth-One Vertex Deletion"],"prefix":"10.1007","author":[{"given":"Geevarghese","family":"Philip","sequence":"first","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.endm.2004.03.008","volume":"17","author":"C. \u00c1lvarez","year":"2004","unstructured":"\u00c1lvarez, C., Serna, M.: The Proper Interval Colored Graph problem for caterpillar trees. Electronic Notes in Discrete Mathematics\u00a017, 23\u201328 (2004)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-54487-9_49","volume-title":"Computer Science Logic","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Proskurowski, A., Seese, D.: Monadic Second Order Logic, Tree Automata and Forbidden Minors. In: Sch\u00f6nfeld, W., B\u00f6rger, E., Kleine B\u00fcning, H., Richter, M.M. (eds.) CSL 1990. LNCS, vol.\u00a0533, pp. 1\u201316. Springer, Heidelberg (1991)"},{"issue":"4","key":"19_CR3","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S.F. Assmann","year":"1981","unstructured":"Assmann, S.F., Peck, G.W., Sys\u0142o, M.M., Zak, J.: The bandwidth of caterpillars with hairs of length 1 and 2. SIAM Journal on Algebraic and Discrete Methods\u00a02(4), 387\u2013393 (1981)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"3","key":"19_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set problem. SIAM Journal of Discrete Mathematics\u00a012(3), 289\u2013297 (1999)","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"1","key":"19_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. International Journal of Foundations of Computer Science\u00a05(1), 59\u201368 (1994)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1\u20132","key":"19_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209(1\u20132), 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, Applications, and Computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 1\u201314. Springer, Heidelberg (2006)"},{"key":"19_CR8","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)"},{"issue":"3","key":"19_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial Optimization on Graphs of Bounded Treewidth. The Computer Journal\u00a051(3), 255\u2013269 (2008)","journal-title":"The Computer Journal"},{"issue":"3","key":"19_CR10","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00224-009-9234-2","volume":"46","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory of Computing Systems\u00a046(3), 566\u2013597 (2010)","journal-title":"Theory of Computing Systems"},{"key":"19_CR11","unstructured":"Bryant, R.L., Kinnersley, N.G., Fellows, M.R., Langston, M.A.: On Finding Obstruction Sets and Polynomial-Time Algorithms for Gate Matrix Layout. In: Proceedings of the 25th Allerton Conference on Communication, Control and Computing, pp. 397\u2013398 (1987)"},{"key":"19_CR12","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":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set: New Measure and New Structures. In: Kaplan, H. (ed.) Algorithm Theory - SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: An improved fpt algorithm and quadratic kernel for pathwidth one vertex deletion. Accepted at IPEC 2010 (2010)","DOI":"10.1007\/978-3-642-17493-3_11"},{"issue":"3","key":"19_CR15","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F. Dehne","year":"2007","unstructured":"Dehne, F., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 O(k) n 3) FPT-Algorithm for the Undirected Feedback Vertex Set problem. Theory of Computing Systems\u00a041(3), 479\u2013492 (2007)","journal-title":"Theory of Computing Systems"},{"key":"19_CR16","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"issue":"1","key":"19_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cosrev.2008.02.004","volume":"2","author":"F. Dorn","year":"2008","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Computer Science Review\u00a02(1), 29\u201339 (2008)","journal-title":"Computer Science Review"},{"key":"19_CR18","first-page":"191","volume-title":"Complexity Theory: Current Research","author":"R.G. Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed Parameter Tractability and Completeness. In: Complexity Theory: Current Research, pp. 191\u2013225. Cambridge University Press, Cambridge (1992)"},{"key":"19_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"19_CR20","first-page":"501","volume-title":"Proceedings of STOC 1989","author":"M.R. Fellows","year":"1989","unstructured":"Fellows, M.R., Langston, M.A.: On Search, Decision and the Efficiency of Polynomial-time Algorithms. In: Proceedings of STOC 1989, pp. 501\u2013512. ACM Press, New York (1989)"},{"key":"19_CR21","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"8","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences\u00a072(8), 1386\u20131396 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"19_CR23","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":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-28639-4_21","volume-title":"Parameterized and Exact Computation","author":"I.A. Kanj","year":"2004","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized Algorithms for Feedback Vertex Set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 235\u2013247. Springer, Heidelberg (2004)"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Complexity of Computer Communications, 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2-3","key":"19_CR26","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0166-218X(94)90021-3","volume":"54","author":"N.G. Kinnersley","year":"1994","unstructured":"Kinnersley, N.G., Langston, M.A.: Obstruction Set Isolation for the Gate Matrix Layout problem. Discrete Applied Mathematics\u00a054(2-3), 169\u2013213 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth \u2013 computations and approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth \u2013 computations and approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"3","key":"19_CR28","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.tcs.2006.07.015","volume":"363","author":"M. Lin","year":"2006","unstructured":"Lin, M., Lin, Z., Xu, J.: Graph bandwidth of weighted caterpillars. Theoretical Computer Science\u00a0363(3), 266\u2013277 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"19_CR29","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences\u00a020(2), 219\u2013230 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"3","key":"19_CR31","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: The NP-Completeness of the bandwidth minimization problem. Computing\u00a016(3), 263\u2013270 (1976)","journal-title":"Computing"},{"key":"19_CR32","unstructured":"Philip, G., Raman, V., Villanger, Y.: A quartic kernel for pathwidth-one vertex deletion. A full version of the current paper, http:\/\/www.imsc.res.in\/~gphilip\/publications\/pwone.pdf"},{"issue":"3","key":"19_CR33","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1159892.1159898","volume":"2","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S., Subramanian, C.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms\u00a02(3), 403\u2013415 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"19_CR34","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors I. Excluding a forest. Journal of Combinatorial Theory, Series B\u00a035(1), 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"19_CR35","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. II. Algorithmic Aspects of Tree-Width. Journal of Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"19_CR36","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1137\/1.9781611973068.13","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"St\u00e9phan Thomass\u00e9","year":"2009","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proceedings of SODA 2009, Society for Industrial and Applied Mathematics, pp. 115\u2013119 (2009)"}],"container-title":["Lecture Notes in Computer Science","Graph Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16926-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T01:06:00Z","timestamp":1559783160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}