{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:35:47Z","timestamp":1787319347808,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received a lot of attention in parameterized complexity. In this paper, we initiate the study of a wide generalization of this problem called the [Formula: see text]-free Strong Connected Component Deletion problem, where [Formula: see text] is a finite family of digraphs. Here, one is given a digraph [Formula: see text] and an integer [Formula: see text], and the objective is to decide whether there is a vertex set of size at most [Formula: see text] whose deletion results in a digraph where every strongly connected component excludes graphs in family [Formula: see text] as (not necessarily induced) subgraphs. When [Formula: see text] comprises only the digraph with a single arc, then this problem is precisely the DFVS problem. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if [Formula: see text] only contains rooted graphs or if [Formula: see text] contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the results of G\u00f6ke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249\u2013261] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above-mentioned problems, whose running times are better and that match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by G\u00f6ke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249\u2013261].<\/jats:p>","DOI":"10.1137\/23m1548591","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T12:12:57Z","timestamp":1734091977000},"page":"3079-3110","source":"Crossref","is-referenced-by-count":0,"title":["On the Parameterized Complexity of Deletion to \\(\\boldsymbol{\\mathcal{H}}\\)-Free Strong Components"],"prefix":"10.1137","volume":"38","author":[{"given":"Rian","family":"Neogi","sequence":"first","affiliation":[{"name":"Combinatorics and Optimization Department, University of Waterloo, Waterloo, ON, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick, Warwick, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Theoretical Computer Science Group, Institute of Mathematical Sciences, HBNI, India, and University of Bergen, Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2212-1359","authenticated-orcid":true,"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"ref1","unstructured":"K. Chandrasekaran and S. Mozaffari, Odd multiway cut in directed acyclic graphs, in Proceedings of the 12th International Symposium on Parameterized and Exact Computation, Springer, 2017, pp. 12:1\u201312:12."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"J. Chen, Y. Liu, S. Lu, B. O\u2019sullivan, and I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 177\u2013186.","DOI":"10.1145\/1374376.1374404"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2700209"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"A. G\u00f6ke, D. Marx, and M. Mnich, Parameterized algorithms for generalizations of directed feedback vertex set, in Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249\u2013261.","DOI":"10.1007\/978-3-030-17402-6_21"},{"key":"ref7","first-page":"59:1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages and Programming\u00a0(ICALP 2020)","author":"G\u00f6ke A.","year":"2020"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/120904202"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"S. Kratsch and M. Wahlstr\u00f6m, Representative sets and irrelevant vertices: New tools for kernelization, in Proceedings of the 53rd Annual Symposium on Foundations of Computer Science, 2012, pp. 450\u2013459.","DOI":"10.1109\/FOCS.2012.46"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, M. Ramanujan, and S. Saurabh, When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 1916\u20131933.","DOI":"10.1137\/1.9781611975031.125"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, M. Ramanujan, S. Saurabh, and M. Zehavi, Parameterized complexity and approximability of directed odd cycle transversal, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2181\u20132200.","DOI":"10.1137\/1.9781611975994.134"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"D. Marx, Important separators and parameterized algorithms, in Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 2011, pp. 5\u201310.","DOI":"10.1007\/978-3-642-25870-1_2"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1548591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:47:52Z","timestamp":1787316472000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1548591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/23M1548591"],"URL":"https:\/\/doi.org\/10.1137\/23m1548591","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,11]]}}}