{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T19:33:37Z","timestamp":1780342417312,"version":"3.54.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            A feedback vertex set (\n            <jats:italic>fvs<\/jats:italic>\n            ) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on\n            <jats:italic>n<\/jats:italic>\n            vertices with minimum degree at least 3 has a fvs on at most 1\/3\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1 \u2212 \u03f5<\/jats:sup>\n            vertices, then there is a cycle of length at most 6\/\u03f5 (for \u03f5 \u2265 1\/2, we can even improve this to just 6).Using this, we obtain a\n            <jats:italic>O<\/jats:italic>\n            ((12 log\n            <jats:italic>k<\/jats:italic>\n            \/log log\n            <jats:italic>k<\/jats:italic>\n            + 6)\n            <jats:sup>k<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c9<\/jats:sup>\n            algorithm for testing whether an undirected graph on\n            <jats:italic>n<\/jats:italic>\n            vertices has a fvs of size at most\n            <jats:italic>k<\/jats:italic>\n            . Here\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c9<\/jats:sup>\n            is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took\n            <jats:italic>O<\/jats:italic>\n            ((2\n            <jats:italic>k<\/jats:italic>\n            + 1)\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time.We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.\n          <\/jats:p>","DOI":"10.1145\/1159892.1159898","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"403-415","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Faster fixed parameter tractable algorithms for finding feedback vertex sets"],"prefix":"10.1145","volume":"2","author":[{"given":"Venkatesh","family":"Raman","sequence":"first","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. R.","family":"Subramanian","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science","volume":"2186","author":"Alber J.","unstructured":"Alber , J. , Fan , H. , Fellows , M. R. , Fernau , H. , Niedermeier , R. , Rosamond , F. A. , and Stege , U . 2001. Refined search tree technique for dominating set on planar graphs . In Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science , vol. 2186 . Springer-Verlag, New York, 111--122.]] Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F. A., and Stege, U. 2001. Refined search tree technique for dominating set on planar graphs. In Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 2186. Springer-Verlag, New York, 111--122.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622248.1622256"},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms Second Edition. The MIT Press and McGraw-Hill New York.]]   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms Second Edition. The MIT Press and McGraw-Hill New York.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of 11th International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science","volume":"3595","author":"Dehne F. K. H. A.","unstructured":"Dehne , F. K. H. A. , Fellows , M. R. , Langston , M. A. , Rosamond , F. A. , and Stevens , K . 2005. An O(2<sup>O(k)<\/sup>n<sup>3<\/sup>) FPT algorithm for the undirected feedback vertex set problem . In Proceedings of 11th International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science , vol. 3595 . Springer-Verlag, New York, 859--869.]] Dehne, F. K. H. A., Fellows, M. R., Langston, M. A., Rosamond, F. A., and Stevens, K. 2005. An O(2<sup>O(k)<\/sup>n<sup>3<\/sup>) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of 11th International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 3595. Springer-Verlag, New York, 859--869.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer-Verlag New York.]]  Downey R. and Fellows M. 1999. Parameterized Complexity. Springer-Verlag New York.]]","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","article-title":"On the maximal number of disjoint circuits of a graph","volume":"9","author":"Erd\u00f6s P.","year":"1962","unstructured":"Erd\u00f6s , P. , and Posa , L. 1962 . On the maximal number of disjoint circuits of a graph . Publ. Math. Debrecen 9 , 3 -- 12 .]] Erd\u00f6s, P., and Posa, L. 1962. On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen 9, 3--12.]]","journal-title":"Publ. Math. Debrecen"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_18"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Fomin F. V.","unstructured":"Fomin , F. V. , and Thilikos , D. M . 2003. Dominating sets in planar graphs: branch-width and exponential speed-up . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 168--177.]] Fomin, F. V., and Thilikos, D. M. 2003. Dominating sets in planar graphs: branch-width and exponential speed-up. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 168--177.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_15"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science","volume":"3162","author":"Kanj I. A.","unstructured":"Kanj , I. A. , Pelsmajer , M. J. , and Schaefer , M . 2004. Parameterized algorithms for feedback vertex set . In Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science , vol. 3162 . Springer-Verlag, New York, 235--247.]] Kanj, I. A., Pelsmajer, M. J., and Schaefer, M. 2004. Parameterized algorithms for feedback vertex set. In Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 3162. Springer-Verlag, New York, 235--247.]]"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of 27th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science","volume":"2420","author":"Kanj I. A.","unstructured":"Kanj , I. A. , and Perkovic , L . 2002. Improved parameterized algorithms for planar dominating set . In Proceedings of 27th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science , vol. 2420 . Springer-Verlag, New York, 399--410.]] Kanj, I. A., and Perkovic, L. 2002. Improved parameterized algorithms for planar dominating set. In Proceedings of 27th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 2420. Springer-Verlag, New York, 399--410.]]"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science","volume":"2518","author":"Raman V.","unstructured":"Raman , V. , Saurabh , S. , and Subramanian , C. R . 2002. Faster fixed parameter tractable algorithms for undirected feedback vertex set . In Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science , vol. 2518 . Springer-Verlag, New York, 241--248.]] Raman, V., Saurabh, S., and Subramanian, C. R. 2002. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2518. Springer-Verlag, New York, 241--248.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2005.05.037"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1159892.1159898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:42:50Z","timestamp":1672260170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1159892.1159898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1159892.1159898"],"URL":"https:\/\/doi.org\/10.1145\/1159892.1159898","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}