{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:11Z","timestamp":1787321111168,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Feedback Vertex Set (FVS) is one of the most well-studied problems in the realm of parameterized complexity. In this problem we are given a graph $G$ and a positive integer $k$ and the objective is to test whether there exists $S\\subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. Thus, FVS is about deleting as few vertices as possible to get a forest. The main goal of this paper is to study the following interesting problem: How can we generalize the family of forests such that the nice structural properties of forests and the interesting algorithmic properties of FVS can be extended to problems on this class? Toward this we define a graph class, ${\\cal F}_l$, that contains all graphs where each connected component can be transformed into a forest by deleting at most $l$ edges. A graph in the class ${\\cal F}_1$ is known as pseudoforest in the literature and we call a graph in ${\\cal F}_l$ an $l$-pseudoforest. We study the problem of deleting $k$ vertices to get into ${\\cal F}_l$, l-pseudoforest Deletion, in the realm of parameterized complexity. We show that l-pseudoforest Deletion admits an algorithm with running time $c_l^k n^{\\mathcal{O}(1)}$ and admits a kernel of size $f(l)k^2$. Thus, for every fixed $l$ we have a kernel of size $\\mathcal{O}(k^2)$. That is, we get a uniform polynomial kernel for l-pseudoforest Deletion. Our algorithms and uniform kernels involve the use of the expansion lemma and protrusion machinery.<\/jats:p>","DOI":"10.1137\/16m1100794","type":"journal-article","created":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T13:15:08Z","timestamp":1523970908000},"page":"882-901","source":"Crossref","is-referenced-by-count":7,"title":["Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel"],"prefix":"10.1137","volume":"32","author":[{"given":"Geevarghese","family":"Philip","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,17]]},"reference":[{"key":"atypb1","first-page":"629","author":"Bodlaender H. L.","year":"2009","journal-title":"GA"},{"key":"atypb2","unstructured":"H. L. Bodlaender, H. Ono, and Y. Otachi,\n                      A faster parameterized algorithm for pseudoforest deletion\n                      , in Proceedings of the 11th International Symposium on Parameterized and Exact Computation, Aarhus, Denmark, LIPIcs, 2016."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9234-2"},{"key":"atypb4","first-page":"192","author":"Burrage K.","year":"2006","journal-title":"Switzerland"},{"key":"atypb5","first-page":"150","author":"Cygan M.","year":"2011","journal-title":"Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb8","first-page":"189","author":"Fomin F. V.","year":"2011","journal-title":"Germany"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, N. Misra, M. S. Ramanujan, and S. Saurabh,\n                      \n                        Solving\n                        d-\n                        sat via backdoors to small treewidth\n                      \n                      , in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, 2015, pp. 630-641.","DOI":"10.1137\/1.9781611973730.43"},{"key":"atypb10","first-page":"470","author":"Fomin F. V.","year":"2012","journal-title":"NJ"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066678"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"A. C. Giannopoulou, B. M. P. Jansen, D. Lokshtanov, and S. Saurabh,\n                      Uniform Kernelization Complexity of Hitting Forbidden Minors\n                      , CoRR,arXiv:1502.03965, 2015.","DOI":"10.1007\/978-3-662-47672-7_51"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed Parameter Algorithms\n                      , Oxford Lecture Ser. Math. Appl., Oxford University Press, New York, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb17","first-page":"1","author":"Rai A.","year":"2016","journal-title":"India"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.10.021"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"atypb21","first-page":"6","author":"Thomasse\u0301 S.","year":"2010","journal-title":"ACM Trans. Algorithms"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1100794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:22Z","timestamp":1787317522000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1100794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1100794"],"URL":"https:\/\/doi.org\/10.1137\/16m1100794","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}