{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:14Z","timestamp":1784568314723,"version":"3.55.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T00:00:00Z","timestamp":1739491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            In the\n            <jats:sc>Directed Feedback Vertex Set (DFVS)<\/jats:sc>\n            problem, given a digraph\n            <jats:italic>D<\/jats:italic>\n            and a positive integer\n            <jats:italic>k<\/jats:italic>\n            , the goal is to check if there exists a set of at most\n            <jats:italic>k<\/jats:italic>\n            vertices whose deletion from\n            <jats:italic>D<\/jats:italic>\n            results in a directed acyclic graph. The existence of a polynomial kernel for\n            <jats:sc>DFVS<\/jats:sc>\n            , parameterized by the solution size\n            <jats:italic>k<\/jats:italic>\n            , is a central open problem in kernelization. In this article, we give a polynomial kernel for\n            <jats:sc>DFVS<\/jats:sc>\n            parameterized by\n            <jats:italic>k<\/jats:italic>\n            <jats:italic>plus<\/jats:italic>\n            the size of a treewidth-\u03b7 modulator (of the underlying undirected graph), where \u03b7 is any fixed positive integer. Since the status of the existence of a polynomial kernel for\n            <jats:sc>DFVS<\/jats:sc>\n            (parameterized by the solution size) has been open for a very long time now, and it is known to not admit a polynomial kernel when the parameter is the size of a treewidth-2 modulator, solution size plus the size of the treewidth-\u03b7 modulator makes for an interesting choice of parameter to study. In fact, the polynomial kernelization complexity of\n            <jats:sc>DFVS<\/jats:sc>\n            parameterized by the size of the undirected feedback vertex set (treewidth-1 modulator) in the underlying undirected graph has already been studied in literature. Our choice of parameter strictly encompasses previous positive kernelization results on\n            <jats:sc>DFVS<\/jats:sc>\n            . Our result is based on a novel application of the tool of\n            <jats:italic>important separators<\/jats:italic>\n            embedded in state-of-the-art machinery such as protrusion\u00a0decompositions.\n          <\/jats:p>","DOI":"10.1145\/3711669","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T11:32:56Z","timestamp":1736767976000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for Directed Feedback Vertex Set"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2116-6048","authenticated-orcid":false,"given":"Maadapuzhi-Sridharan","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2212-1359","authenticated-orcid":false,"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany and University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3636-5322","authenticated-orcid":false,"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beersheba, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.07.008"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0038-2"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"e_1_3_2_7_2","first-page":"167","article-title":"Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem","volume":"83","author":"Becker Ann","year":"1996","unstructured":"Ann Becker and Dan Geiger. 1996. Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. AI 83 (1996), 167\u2013188.","journal-title":"AI"},{"key":"e_1_3_2_8_2","unstructured":"Benjamin Bergougnoux Eduard Eiben Robert Ganian Sebastian Ordyniak and M. S. Ramanujan. 2017. Towards a polynomial kernel for directed feedback vertex set. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics Vol. 83. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatic Dagstuhl Germany Article 36 15 pages."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00256-5_6"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Yixin Cao Jianer Chen and Yang Liu. 2010. On feedback vertex set new measure and new structures. In SWAT. Lecture Notes in Computer Science Vol. 6139. Springer 93\u2013104.","DOI":"10.1007\/978-3-642-13731-0_10"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch58"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"issue":"4","key":"e_1_3_2_17_2","first-page":"28","article-title":"Directed subset feedback vertex set is fixed-parameter tractable","volume":"11","author":"Chitnis Rajesh Hemant","year":"2015","unstructured":"Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and D\u00e1niel Marx. 2015. Directed subset feedback vertex set is fixed-parameter tractable. ACM TALG 11, 4 (2015), 28.","journal-title":"ACM TALG"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"1","key":"e_1_3_2_19_2","first-page":"73","article-title":"On the hardness of losing width","volume":"54","author":"Cygan Marek","year":"2014","unstructured":"Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2014. On the hardness of losing width. TOCS 54, 1 (2014), 73\u201382.","journal-title":"TOCS"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"issue":"1","key":"e_1_3_2_22_2","first-page":"76","article-title":"Fixed-parameter tractability results for feedback set problems in tournaments","volume":"8","author":"Dom M.","year":"2010","unstructured":"M. Dom, J. Guo, F. H\u00fcffner, R. Niedermeier, and A. Tru\u00df. 2010. Fixed-parameter tractability results for feedback set problems in tournaments. JDA 8, 1 (2010), 76\u201386.","journal-title":"JDA"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1992.215379"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_3_2_28_2","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139177801.010"},{"issue":"3","key":"e_1_3_2_32_2","first-page":"399","article-title":"Maximal flow through a network","volume":"8","author":"Ford Lester R.","year":"1956","unstructured":"Lester R. Ford and Delbert R. Fulkerson. 1956. Maximal flow through a network. CJM 8, 3 (1956), 399\u2013404.","journal-title":"CJM"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_3_2_34_2","unstructured":"Venkatesan Guruswami and Euiwoong Lee. 2015. Inapproximability of H-Transversal\/Packing. In Proceedings of APPROX\/RANDOM. 284\u2013304."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.137"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.004"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.12.001"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.27"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_3_2_40_2","article-title":"Recent developments in kernelization: A survey","volume":"2","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bull. EATCS 2, 113 (2014).","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.23"},{"key":"e_1_3_2_42_2","unstructured":"William Lochet Daniel Lokshtanov Pranabendu Misra Saket Saurabh Roohani Sharma and Meirav Zehavi. 2020. Fault tolerant subgraphs with applications in kernelization. In Proceedings of ITCS."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"e_1_3_2_44_2","first-page":"1916","volume-title":"Proceedings of SODA","author":"Lokshtanov Daniel","year":"2018","unstructured":"Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. 2018. When recursion is better than iteration. In Proceedings of SODA. 1916\u20131933."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2017.02.002"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.05.004"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271272"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844848"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711669","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:15Z","timestamp":1750295955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,14]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3711669"],"URL":"https:\/\/doi.org\/10.1145\/3711669","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,14]]},"assertion":[{"value":"2023-02-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}