{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T13:37:51Z","timestamp":1768829871667,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T00:00:00Z","timestamp":1748908800000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007837","name":"Universit\u00e4t Bremen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n We study reduction rules for Directed Feedback Vertex Set (DFVS)<\/jats:sc> on directed graphs without long cycles. A DFVS<\/jats:sc> instance without cycles longer than\u00a0d<\/jats:italic> naturally corresponds to an instance of d<\/jats:italic>\n -Hitting Set<\/jats:sc>, however, enumerating all cycles in an n<\/jats:italic>-vertex graph and then kernelizing the resulting d<\/jats:italic>\n -Hitting Set<\/jats:sc> instance can be too costly, as already enumerating all cycles can take time\u00a0\n \n $$\\Omega (n^d)$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. To the best of our knowledge, the kernelization of DFVS<\/jats:sc> on graphs without long cycles has not been studied in the literature, except for very restricted cases, e.g., for tournaments, in which all induced cycles are of length three. We show that the natural reduction rule to delete all vertices and edges that do not lie on induced cycles cannot be implemented efficiently, that is, it is W<\/jats:italic>[1]-hard (with respect to parameter d<\/jats:italic>) to decide if a vertex or edge lies on an induced cycle of length at most d<\/jats:italic> even on graphs that become acyclic after the deletion of a single vertex or edge. Based on different reduction rules we then show how to compute a kernel with at most \n \n $$2^dk^d$$<\/jats:tex-math>\n \n \n \n 2<\/mml:mn>\n d<\/mml:mi>\n <\/mml:msup>\n \n k<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> vertices and at most \n \n $$d^{3d}k^d$$<\/jats:tex-math>\n \n \n \n d<\/mml:mi>\n \n 3<\/mml:mn>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n k<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> induced cycles of length at most\u00a0d<\/jats:italic> (which however, cannot be enumerated efficiently), where\u00a0k<\/jats:italic> is the size of a minimum directed feedback vertex set. We then study classes of graphs whose underlying undirected graphs have bounded expansion or are nowhere dense. These are very general classes of sparse graphs, containing e.g. classes excluding a minor or a topological minor. We prove that for every class\u00a0\n \n $$\\mathscr {C} $$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> with bounded expansion there is a function \n \n $$f_\\mathscr {C} (d)$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that for graphs \n \n $$G\\in \\mathscr {C} $$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \u2208<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> without induced cycles of length greater than d<\/jats:italic> we can compute a kernel with \n \n $$f_\\mathscr {C} (d)\\cdot k$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> vertices in time \n \n $$f_\\mathscr {C} (d)\\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. For every nowhere dense class \n \n $$\\mathscr {C} $$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> there is a function \n \n $$f_\\mathscr {C} (d,\\varepsilon )$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n ,<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that for graphs \n \n $$G\\in \\mathscr {C} $$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \u2208<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> without induced cycles of length greater than d<\/jats:italic> we can compute a kernel with \n \n $$f_\\mathscr {C} (d,\\varepsilon )\\cdot k^{1+\\varepsilon }$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n ,<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n k<\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> vertices for any \n \n $$\\varepsilon >0$$<\/jats:tex-math>\n \n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> in time \n \n $$f_\\mathscr {C} (d,\\varepsilon )\\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n \n f<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n d<\/mml:mi>\n ,<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. The most restricted classes we consider are strongly connected planar graphs without any (induced or non-induced) long cycles. We show that these classes have treewidth \n \n $$\\mathcal {O}(d)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and hence DFVS<\/jats:sc> on planar graphs without cycles of length greater than d<\/jats:italic> can be solved in time \n \n $$2^{\\mathcal {O}(d)}\\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We finally present a new data reduction rule for general DFVS<\/jats:sc> and prove that the rule together with a few standard rules subsumes all rules applied in the work of Bergougnoux et al. to obtain a polynomial kernel for DFVS[FVS]<\/jats:sc>, i.e., DFVS<\/jats:sc> parameterized by the feedback vertex set number of the underlying (undirected) graph. We conclude by studying the LP-based approximation of DFVS<\/jats:sc>.<\/jats:p>","DOI":"10.1007\/s00236-025-00490-2","type":"journal-article","created":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T20:08:32Z","timestamp":1748981312000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Data reduction for directed feedback vertex set on graphs without long induced cycles"],"prefix":"10.1007","volume":"62","author":[{"given":"Jona","family":"Dirks","sequence":"first","affiliation":[]},{"given":"Enna","family":"Gerhard","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Grobler","sequence":"additional","affiliation":[]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"490_CR1","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"490_CR2","doi-asserted-by":"crossref","unstructured":"Razgon, I.: Computing minimum directed feedback vertex set in $${O}^*(1.9977^n)$$. In: Theoretical Computer Science, pp. 70\u201381. World Scientific, Rome (2007)","DOI":"10.1142\/9789812770998_0010"},{"key":"490_CR3","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 177\u2013186 (2008)","DOI":"10.1145\/1374376.1374404"},{"key":"490_CR4","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: A linear time parameterized algorithm for directed feedback vertex set. arXiv preprint arXiv:1609.04347 (2016)","DOI":"10.1007\/978-3-662-47672-7_76"},{"key":"490_CR5","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: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 65\u201378 (2018). Springer","DOI":"10.1007\/978-3-030-00256-5_6"},{"issue":"35","key":"490_CR6","doi-asserted-by":"publisher","first-page":"4688","DOI":"10.1016\/j.tcs.2011.05.003","volume":"412","author":"S Kreutzer","year":"2011","unstructured":"Kreutzer, S., Ordyniak, S.: Digraph decompositions and monotonicity in digraph searching. Theoretical Computer Science 412(35), 4688\u20134703 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"490_CR7","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1007\/s00453-020-00777-5","volume":"83","author":"B Bergougnoux","year":"2021","unstructured":"Bergougnoux, B., Eiben, E., Ganian, R., Ordyniak, S., Ramanujan, M.: Towards a polynomial kernel for directed feedback vertex set. Algorithmica 83(5), 1201\u20131221 (2021)","journal-title":"Algorithmica"},{"key":"490_CR8","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M., Saurabh, S., Sharma, R., Zehavi, M.: Wannabe bounded treewidth graphs admit a polynomial kernel for dfvs. In: Workshop on Algorithms and Data Structures, pp. 523\u2013537 (2019). Springer","DOI":"10.1007\/978-3-030-24766-9_38"},{"issue":"1","key":"490_CR9","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 of Computing Systems 54(1), 73\u201382 (2014)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"490_CR10","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-015-0038-2","volume":"76","author":"J Bang-Jensen","year":"2016","unstructured":"Bang-Jensen, J., Maddaloni, A., Saurabh, S.: Algorithms and kernels for feedback set problems in generalizations of tournaments. Algorithmica 76(2), 320\u2013343 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"490_CR11","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","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. Journal of Discrete Algorithms 8(1), 76\u201386 (2010)","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"490_CR12","first-page":"1","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Le, T.-N., Lokshtanov, D., Saurabh, S., Thomass\u00e9, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. ACM Transactions on Algorithms (TALG) 15(1), 1\u201344 (2019)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"2","key":"490_CR13","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":"490_CR14","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even, G., Schieber, B., Sudan, M., et al.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"490_CR15","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/090756144","volume":"40","author":"V Guruswami","year":"2011","unstructured":"Guruswami, V., H\u00e5stad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: Every ordering csp is approximation resistant. SIAM Journal on Computing 40(3), 878\u2013914 (2011)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"490_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a006","volume":"12","author":"V Guruswami","year":"2016","unstructured":"Guruswami, V., Lee, E.: Simple proof of hardness of feedback vertex set. Theory of Computing 12(1), 1\u201311 (2016)","journal-title":"Theory of Computing"},{"key":"490_CR17","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Hardness of vertex deletion and project scheduling. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 301\u2013312. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32512-0_26"},{"key":"490_CR18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Ramanujan, M., Saurabh, S., Zehavi, M.: FPT-approximation for FPT problems. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 199\u2013218 (2021). SIAM","DOI":"10.1137\/1.9781611976465.14"},{"key":"490_CR19","unstructured":"Gro\u00dfmann, E., Heuer, T., Schulz, C., Strash, D.: The pace 2022 parameterized algorithms and computational experiments challenge: Directed feedback vertex set. In: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) (2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"490_CR20","unstructured":"Bergenthal, M., Dirks, J., Freese, T., Gahde, J., Gerhard, E., Grobler, M., Siebertz, S.: Pace solver description: Grapa-java. In: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) (2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"3","key":"490_CR21","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"MR Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems. Algorithmica 13(3), 266\u2013282 (1995)","journal-title":"Algorithmica"},{"issue":"7","key":"490_CR22","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences 76(7), 524\u2013531 (2010)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"490_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., Van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM (JACM) 61(4), 1\u201327 (2014)","journal-title":"Journal of the ACM (JACM)"},{"issue":"6","key":"490_CR24","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1016\/j.jcss.2010.10.001","volume":"77","author":"S Bessy","year":"2011","unstructured":"Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences 77(6), 1071\u20131078 (2011)","journal-title":"Journal of Computer and System Sciences"},{"key":"490_CR25","unstructured":"Fomin, F.V., Le, T.-N., Lokshtanov, D., Saurabh, S., Thomasse, S., Zehavi, M.: Lossy kernelization for (implicit) hitting set problems. arXiv preprint arXiv:2308.05974 (2023)"},{"key":"490_CR26","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"key":"490_CR27","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.dam.2016.11.007","volume":"219","author":"J You","year":"2017","unstructured":"You, J., Wang, J., Cao, Y.: Approximate association via dissociation. Discrete Applied Mathematics 219, 202\u2013209 (2017)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"490_CR28","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.tcs.2005.10.021","volume":"351","author":"R Haas","year":"2006","unstructured":"Haas, R., Hoffmann, M.: Chordless paths through three vertices. Theoretical Computer Science 351(3), 360\u2013371 (2006)","journal-title":"Theoretical Computer Science"},{"key":"490_CR29","doi-asserted-by":"crossref","unstructured":"Dreier, J., M\u00e4hlmann, N., Siebertz, S.: First-order model checking on structurally sparse graph classes. In: Saha, B., Servedio, R.A. (eds.) Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 567\u2013580. ACM, Orlando (2023)","DOI":"10.1145\/3564246.3585186"},{"issue":"3","key":"490_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM) 64(3), 1\u201332 (2017)","journal-title":"Journal of the ACM (JACM)"},{"key":"490_CR31","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., De\u00a0Mendez, P.O.: Grad and classes with bounded expansion i. decompositions. European Journal of Combinatorics 29(3), 760\u2013776 (2008)","DOI":"10.1016\/j.ejc.2006.07.013"},{"issue":"4","key":"490_CR32","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Mendez, P.O.: On nowhere dense graphs. Eur. J. Comb. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"key":"490_CR33","unstructured":"Drange, P.G., Dregi, M.S., Fomin, F.V., Kreutzer, S., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Reidl, F., Villaamil, F.S., Saurabh, S., Siebertz, S., Sikdar, S.: Kernelization and sparseness: the case of dominating set. In: Ollinger, N., Vollmer, H. (eds.) 33rd Symposium on Theoretical Aspects of Computer Science, STACS. LIPIcs, vol. 47, pp. 31\u201313114. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Orl\u00e9ans (2016)"},{"key":"490_CR34","unstructured":"Eickmeyer, K., Giannopoulou, A.C., Kreutzer, S., Kwon, O., Pilipczuk, M., Rabinovich, R., Siebertz, S.: Neighborhood complexity and kernelization for nowhere dense classes of graphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP. LIPIcs, vol. 80, pp. 63\u201316314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Warsaw (2017)"},{"key":"490_CR35","unstructured":"Weihe, K.: Covering trains by stations or the power of data reduction. Proceedings of Algorithms and Experiments, ALEX, 1\u20138 (1998)"},{"key":"490_CR36","doi-asserted-by":"crossref","unstructured":"Fleischer, R., Wu, X., Yuan, L.: Experimental study of fpt algorithms for the directed feedback vertex set problem. In: European Symposium on Algorithms, pp. 611\u2013622 (2009). Springer","DOI":"10.1007\/978-3-642-04128-0_55"},{"issue":"1","key":"490_CR37","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"1","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., Rado, R.: Intersection theorems for systems of sets. Journal of the London Mathematical Society 1(1), 85\u201390 (1960)","journal-title":"Journal of the London Mathematical Society"},{"key":"490_CR38","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Kratsch, S.: A shortcut to (sun) flowers: Kernels in logarithmic space or linear time. In: International Symposium on Mathematical Foundations of Computer Science, pp. 299\u2013310 (2015). Springer","DOI":"10.1007\/978-3-662-48054-0_25"},{"issue":"1","key":"490_CR39","first-page":"129","volume":"70","author":"R Van Bevern","year":"2014","unstructured":"Van Bevern, R.: Towards optimal and expressive kernelization for d-hitting set. Algorithmica 70(1), 129\u2013147 (2014)","journal-title":"Algorithmica"},{"key":"490_CR40","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Siebertz, S., Torunczyk, S.: On the number of types in sparse graphs. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS, pp. 799\u2013808. ACM, Oxford (2018)","DOI":"10.1145\/3209108.3209178"},{"issue":"2","key":"490_CR41","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3274652","volume":"15","author":"S Kreutzer","year":"2019","unstructured":"Kreutzer, S., Rabinovich, R., Siebertz, S.: Polynomial kernels and wideness properties of nowhere dense graph classes. ACM Trans. Algorithms 15(2), 24\u201312419 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"490_CR42","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B 62(2), 323\u2013348 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00490-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00490-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00490-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:42:36Z","timestamp":1750160556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00490-2"}},"subtitle":["Three rules to rule them all"],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["490"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00490-2","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"10 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"25"}}