{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T18:05:57Z","timestamp":1656266757571},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"\n A feedback vertex set (\n 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 n<\/jats:italic>\n vertices with minimum degree at least 3 has a fvs on at most 1\/3\n n<\/jats:italic>\n 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 O<\/jats:italic>\n ((12 log\n k<\/jats:italic>\n \/log log\n k<\/jats:italic>\n + 6)\n k<\/jats:sup>\n n<\/jats:italic>\n \u03c9<\/jats:sup>\n algorithm for testing whether an undirected graph on\n n<\/jats:italic>\n vertices has a fvs of size at most\n k<\/jats:italic>\n . Here\n n<\/jats:italic>\n \u03c9<\/jats:sup>\n is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took\n O<\/jats:italic>\n ((2\n k<\/jats:italic>\n + 1)\n \n k<\/jats:italic>\n <\/jats:sup>\n n<\/jats:italic>\n 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","source":"Crossref","is-referenced-by-count":43,"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"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}]},{"given":"C. R.","family":"Subramanian","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}]}],"member":"320","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."},{"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."},{"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","first-page":"3","article-title":"On the maximal number of disjoint circuits of a graph","volume":"9","author":"Erd\u00f6s P.","year":"1962","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."},{"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."},{"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."},{"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."},{"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":[[2021,2,20]],"date-time":"2021-02-20T10:48:59Z","timestamp":1613818139000},"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":"http:\/\/dx.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":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2006,7]]}}}