{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:11Z","timestamp":1784568311933,"version":"3.55.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004955","name":"\u00d6sterreichische Forschungsf\u00f6rderungsgesellschaft","doi-asserted-by":"publisher","award":["(project P31336: NFPC)"],"award-info":[{"award-number":["(project P31336: NFPC)"]}],"id":[{"id":"10.13039\/501100004955","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the<jats:sc>Directed Feedback Vertex Set (DFVS)<\/jats:sc>problem, the input is a directed graph<jats:italic>D<\/jats:italic>and an integer<jats:italic>k<\/jats:italic>. The objective is to determine whether there exists a set of at most<jats:italic>k<\/jats:italic>vertices intersecting every directed cycle of<jats:italic>D<\/jats:italic>. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen et al. (J ACM 55(5):177\u2013186, 2008); since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. Since this problem has remained open in spite of the best efforts of a number of prominent researchers and pioneers in the field, a natural step forward is to study the kernelization complexity of<jats:sc>DFVS<\/jats:sc>parameterized by a natural<jats:italic>larger<\/jats:italic>parameter. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying<jats:italic>undirected graph<\/jats:italic>. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.<\/jats:p>","DOI":"10.1007\/s00453-020-00777-5","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T09:09:22Z","timestamp":1604480962000},"page":"1201-1221","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Towards a Polynomial Kernel for Directed Feedback Vertex Set"],"prefix":"10.1007","volume":"83","author":[{"given":"Benjamin","family":"Bergougnoux","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduard","family":"Eiben","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1935-651X","authenticated-orcid":false,"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"issue":"3","key":"777_CR1","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 J. Discrete Math. 12(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"777_CR2","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."},{"issue":"1","key":"777_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","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. Artif. Intell. 83(1), 167\u2013188 (1996)","journal-title":"Artif. Intell."},{"key":"777_CR4","unstructured":"Bergougnoux, B., Eiben, E., Ganian, R., Ordyniak, S., Ramanujan, M.S.: Towards a polynomial kernel for directed feedback vertex set. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21\u201325, 2017\u2014Aalborg, Denmark, pp. 36:1\u201336:15 (2017)"},{"issue":"5","key":"777_CR5","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM 63(5), 44:1\u201344:69 (2016)","journal-title":"J. ACM"},{"issue":"3","key":"777_CR6","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00224-009-9234-2","volume":"46","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst. 46(3), 566\u2013597 (2010)","journal-title":"Theory Comput. Syst."},{"key":"777_CR7","doi-asserted-by":"crossref","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.), Algorithm Theory\u2014SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21\u201323, 2010. Proceedings, volume 6139 of Lecture Notes in Computer Science, pp. 93\u2013104. Springer (2010)","DOI":"10.1007\/978-3-642-13731-0_10"},{"key":"777_CR8","unstructured":"Chekuri, C., Madan, V.: Constant factor approximation for subset feedback set problems via a new LP relaxation. In: Krauthgamer, R. (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 808\u2013820. SIAM (2016)"},{"issue":"7","key":"777_CR9","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Songjian, L., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"777_CR10","doi-asserted-by":"publisher","first-page":"177","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), 177\u2013186 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"777_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2700209","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 Trans. Algorithms 11(4), 28 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"777_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"1","key":"777_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00224-013-9480-1","volume":"54","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. Theory Comput. Syst. 54(1), 73\u201382 (2014)","journal-title":"Theory Comput. Syst."},{"key":"777_CR14","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)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"777_CR15","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. SIAM J. Discrete Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"777_CR16","volume-title":"Graph Theory, volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, volume 173 of Graduate Texts in Mathematics, 2nd edn. Springer, New York (2000)","edition":"2"},{"key":"777_CR17","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22\u201325, 1992, pp. 36\u201349 (1992)"},{"issue":"4","key":"777_CR18","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":"777_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"Rodney G Downey","year":"2013","unstructured":"Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"777_CR20","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":"777_CR21","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":"777_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jcss.2016.09.002","volume":"84","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P., Obdrz\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219\u2013242 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"777_CR23","volume-title":"Topological Graph Theory","author":"JL Gross","year":"1987","unstructured":"Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley-Interscience, New York (1987)"},{"key":"777_CR24","unstructured":"Guruswami, V., Lee, E.: Inapproximability of h-transversal\/packing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, August 24\u201326, 2015, Princeton, NJ, USA, volume\u00a040 of LIPIcs, pp. 284\u2013304. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"issue":"2","key":"777_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-012-9393-4","volume":"53","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited\u2014upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"key":"777_CR26","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: Rabani, Y. (ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 1726\u20131736. SIAM (2012)"},{"issue":"5","key":"777_CR27","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., Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. J. Comb. Theory Ser. B 101(5), 378\u2013381 (2011)","journal-title":"J. Comb. Theory Ser. B"},{"key":"777_CR28","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"777_CR29","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 set problem and the s-cycle packing problem. J. Comb. Theory Ser. B 102(4), 1020\u20131034 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"key":"777_CR30","unstructured":"Kawarabayashi, K., Kr\u00e1l\u2019, D., Krc\u00e1l, M., Kreutzer, S.: Packing directed cycles through a specified vertex set. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 365\u2013377 (2013)"},{"issue":"10","key":"777_CR31","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. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"key":"777_CR32","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Sharma, R., Zehavi, M.: Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS. In: Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5\u20137, 2019, Proceedings, pp. 523\u2013537 (2019)"},{"issue":"5","key":"777_CR33","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. J. Comb. Theory Ser. B 102(5), 1134\u20131141 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"777_CR34","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 Trans. Algorithms 2(3), 403\u2013415 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"777_CR35","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.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535\u2013554 (1996)","journal-title":"Combinatorica"},{"issue":"2","key":"777_CR36","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"PD Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15(2), 281\u2013288 (1995)","journal-title":"Combinatorica"},{"issue":"2","key":"777_CR37","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01844848","volume":"16","author":"PD Seymour","year":"1996","unstructured":"Seymour, P.D.: Packing circuits in Eulerian digraphs. Combinatorica 16(2), 223\u2013231 (1996)","journal-title":"Combinatorica"},{"issue":"2","key":"777_CR38","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A 4k$${}^{\\text{2 }}$$ kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"777_CR39","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, LP-branching and FPT algorithms. In: Chekuri, C. (ed.), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 1762\u20131781. SIAM (2014)","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00777-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00777-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00777-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,26]],"date-time":"2022-11-26T13:48:19Z","timestamp":1669470499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00777-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["777"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00777-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}