{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:06Z","timestamp":1759638006251,"version":"3.40.3"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_38","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"523-537","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"issue":"7","key":"38_CR1","first-page":"524","volume":"76","author":"F Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.: A kernelization algorithm for $$d$$-HS. JCSS 76(7), 524\u2013531 (2010)","journal-title":"JCSS"},{"key":"38_CR2","first-page":"9","volume":"92","author":"A Agrawal","year":"2018","unstructured":"Agrawal, A., Saurabh, S., Sharma, R., Zehavi, M.: Kernels for deletion to classes of acyclic digraphs. JCSS 92, 9\u201321 (2018)","journal-title":"JCSS"},{"issue":"3","key":"38_CR3","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. SIDMA 12(3), 289\u2013297 (1999)","journal-title":"SIDMA"},{"key":"38_CR4","first-page":"1","volume":"76","author":"J Bang-Jensen","year":"2015","unstructured":"Bang-Jensen, J., Maddaloni, A., Saurabh, S.: Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica 76, 1\u201324 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"38_CR5","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"key":"38_CR6","first-page":"167","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. AI 83, 167\u2013188 (1996)","journal-title":"AI"},{"doi-asserted-by":"crossref","unstructured":"Bergougnoux, B., Eiben, E., Ganian, R., Ordyniak, S., Ramanujan, M.: Towards a polynomial kernel for directed feedback vertex set. In: MFCS, vol. 83 (2017)","key":"38_CR7","DOI":"10.1007\/s00453-020-00777-5"},{"doi-asserted-by":"crossref","unstructured":"Bonamy, M., Kowalik, \u0141., Nederlof, J., Pilipczuk, M., Soca\u0142a, A., Wrochna, M.: On directed feedback vertex set parameterized by treewidth. In: WG, pp. 65\u201378 (2018)","key":"38_CR8","DOI":"10.1007\/978-3-030-00256-5_6"},{"issue":"1","key":"38_CR9","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-014-9904-6","volume":"73","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: new measure and new structures. Algorithmica 73(1), 63\u201386 (2015)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Madan, V.: Constant factor approximation for subset feedback set problems via a new LP relaxation. In: SODA, pp. 808\u2013820 (2016)","key":"38_CR10","DOI":"10.1137\/1.9781611974331.ch58"},{"issue":"7","key":"38_CR11","first-page":"1188","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. JCSS 74(7), 1188\u20131198 (2008)","journal-title":"JCSS"},{"issue":"1","key":"38_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"38_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"38_CR14","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/12086217X","volume":"42","author":"R Chitnis","year":"2013","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42(4), 1674\u20131696 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"38_CR15","first-page":"28","volume":"11","author":"RH Chitnis","year":"2015","unstructured":"Chitnis, R.H., Cygan, M., Hajiaghayi, M.T., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. ACM TALG 11(4), 28 (2015)","journal-title":"ACM TALG"},{"key":"38_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"1","key":"38_CR17","first-page":"73","volume":"54","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. TOCS 54(1), 73\u201382 (2014)","journal-title":"TOCS"},{"doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS, pp. 150\u2013159 (2011)","key":"38_CR18","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"38_CR19","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIDMA 27(1), 290\u2013309 (2013)","journal-title":"SIDMA"},{"issue":"1","key":"38_CR20","first-page":"76","volume":"8","author":"M Dom","year":"2010","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-parameter tractability results for feedback set problems in tournaments. JDA 8(1), 76\u201386 (2010)","journal-title":"JDA"},{"unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: CCC, pp. 36\u201349 (1992)","key":"38_CR21"},{"issue":"4","key":"38_CR22","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"38_CR23","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"38_CR24","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u0151s","year":"1965","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347\u2013352 (1965)","journal-title":"Can. J. Math."},{"issue":"2","key":"38_CR25","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"38_CR26","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: approximation, kernelization and optimal FPT algorithms. In: FOCS, pp. 470\u2013479 (2012). http:\/\/www.ii.uib.no\/~daniello\/papers\/PFDFullV1.pdf","key":"38_CR27","DOI":"10.1109\/FOCS.2012.62"},{"key":"38_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2018)"},{"key":"38_CR29","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1017\/CBO9781139177801.010","volume-title":"Tractability","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Saurabh, S.: Kernelization methods for fixed-parameter tractability. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability, pp. 260\u2013282. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"38_CR30","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 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"unstructured":"Guruswami, V., Lee, E.: Inapproximability of H-transversal\/packing. In: APPROX\/RANDOM. LIPIcs, vol. 40, pp. 284\u2013304 (2015)","key":"38_CR31"},{"doi-asserted-by":"crossref","unstructured":"Kakimura, N., Kawarabayashi, K., Kobayashi, Y.: Erd\u00f6s-P\u00f3sa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In: SODA, pp. 1726\u20131736 (2012)","key":"38_CR32","DOI":"10.1137\/1.9781611973099.137"},{"issue":"5","key":"38_CR33","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.jctb.2011.03.004","volume":"101","author":"N Kakimura","year":"2011","unstructured":"Kakimura, N., ichi Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. JCTB 101(5), 378\u2013381 (2011)","journal-title":"JCTB"},{"key":"38_CR34","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jctb.2011.12.001","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback fet problem and the S-cycle packing problem. JCTB 102, 1020\u20131034 (2012)","journal-title":"JCTB"},{"doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kr\u00e1l, D., Krc\u00e1l, M., Kreutzer, S.: Packing directed cycles through a specified vertex set. In: SODA, pp. 365\u2013377 (2013)","key":"38_CR35","DOI":"10.1137\/1.9781611973105.27"},{"issue":"10","key":"38_CR36","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. IPL 114(10), 556\u2013560 (2014)","journal-title":"IPL"},{"key":"38_CR37","first-page":"58","volume":"113","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S.: Recent developments in kernelization. Bull. EATCS 113, 58\u201397 (2014)","journal-title":"Bull. EATCS"},{"doi-asserted-by":"crossref","unstructured":"Le, T., Lokshtanov, D., Saurabh, S., Thomass\u00e9, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. In: SODA, pp. 331\u2013342 (2018)","key":"38_CR38","DOI":"10.1137\/1.9781611975031.23"},{"key":"38_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-30891-8_10","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"D Lokshtanov","year":"2012","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization \u2013 preprocessing with a guarantee. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 129\u2013161. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_10"},{"doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: When recursion is better than iteration. In: SODA, pp. 1916\u20131933 (2018)","key":"38_CR40","DOI":"10.1137\/1.9781611975031.125"},{"key":"38_CR41","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","volume":"25","author":"M Mnich","year":"2017","unstructured":"Mnich, M., van Leeuwen, E.J.: Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim. 25, 48\u201376 (2017)","journal-title":"Discrete Optim."},{"key":"38_CR42","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":"5","key":"38_CR43","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1016\/j.jctb.2012.05.004","volume":"102","author":"M Pontecorvi","year":"2012","unstructured":"Pontecorvi, M., Wollan, P.: Disjoint cycles intersecting a set of vertices. JCTB 102(5), 1134\u20131141 (2012)","journal-title":"JCTB"},{"issue":"3","key":"38_CR44","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.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM TALG 2(3), 403\u2013415 (2006)","journal-title":"ACM TALG"},{"issue":"4","key":"38_CR45","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"BA Reed","year":"1996","unstructured":"Reed, B.A., Robertson, N., Seymour, P., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535\u2013554 (1996)","journal-title":"Combinatorica"},{"issue":"2","key":"38_CR46","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P Seymour","year":"1995","unstructured":"Seymour, P.: Packing directed circuits fractionally. Combinatorica 15(2), 281\u2013288 (1995)","journal-title":"Combinatorica"},{"issue":"2","key":"38_CR47","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01844848","volume":"16","author":"P Seymour","year":"1996","unstructured":"Seymour, P.: Packing circuits in eulerian digraphs. Combinatorica 16(2), 223\u2013231 (1996)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, LP-branching and FPT algorithms. In: SODA, pp. 1762\u20131781 (2014)","key":"38_CR48","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:55:58Z","timestamp":1710266158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}