Stéphan Thomassé
Skip Abstract Section
Abstract
We prove that given an undirected graph G on n vertices and an integer k, one can compute, in polynomial time in n, a graph G′ with at most 4k2 vertices and an integer k′ such that G has a feedback vertex set of size at most k iff G′ has a feedback vertex set of size at most k′. This result improves a previous O(k11) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.
- Becker, A., Bar-Yehuda, R., and Geiger, D. 2000. Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. 12, 219--234. Google Scholar
Cross Ref
- Bodlaender, H. L. 1994. On disjoint cycles. Int. J. Found. Comput. Sci. 5, 59--68.Google ScholarCross Ref
- Bodlaender, H. L. 2007. A cubic kernel for feedback vertex set. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS'07). Lecture Notes in Computer Science, vol. 4393. Springer, 320--331. Google ScholarDigital Library
- Bodlaender, H. L., Cai, L., Chen, J., Fellows, M. R., Telle, J. A., and Marx, D. 2006. Open problems in parameterized and exact computation. In Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC'06).Google Scholar
- Bodlaender, H. L., and Penninkx, E. 2008. A linear kernel for planar feedback vertex set. In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC'08). Lecture Notes in Computer Science, vol. 5018. Springer, 160--171. Google ScholarDigital Library
- Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. 2006. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Lecture Notes in Computer Science, vol. 4169. Springer, 192--202. Google ScholarDigital Library
- Chen, J., Liu, Y., Lu, S., O'Sullivan, B., and Razgon, I. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08). ACM, 177--186. Google ScholarDigital Library
- Dehne, F., Fellows, M., Langston, M. A., Rosamond, F., and Stevens, K. 2005. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON'05). Lecture Notes in Computer Science, vol. 3595. Springer, 859--869.Google Scholar
- Downey, R. G., and Fellows, M. R. 1992. Fixed-parameter tractability and completeness. Congressus Numer. 87, 161--187.Google Scholar
- Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer. Google ScholarDigital Library
- Edmonds, J. 1965. Paths, trees, and flowers. Canad. J. Math. 17, 449--467.Google ScholarCross Ref
- Flum, J., and Grohe, M. 2006. Parameterized Complexity Theory. Springer. Google ScholarDigital Library
- Fomin, F. V., Gaspers, S., and Pyatkin, A. V. 2006. Finding a minimum feedback vertex set in time O(1.7548n). In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC'06). Lecture Notes in Computer Science, vol. 4169. Springer, 184--191. Google ScholarDigital Library
- Gallai, T. 1961. Maximum-Minimum sätze und verallgemeinerte faktoren von graphen. Acta. Math. Acad. Sci. Hungaricae 12, 131--173.Google ScholarCross Ref
- Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., and Wernicke, S. 2005. Improved fixed- parameter algorithms for two feedback set problems. In Proceedings of the 9th International Workshop on Algorithms and Data Structures (WADS'05). Lecture Notes in Computer Science, vol. 3608. Springer, 158--168. Google ScholarDigital Library
- Kanj, I. A., Pelsmajer, M. J., and Schaefer, M. 2004. Parameterized algorithms for feedback vertex set. In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC'04). Lecture Notes in Computer Science, vol. 3162. Springer, 235--247.Google Scholar
- Kriesell, M. 2005. Disjoint A-paths in digraphs. J. Comb. Theory, Ser. B 95, 1, 168--172. Google ScholarDigital Library
- Micali, S., and Vazirani, V. V. 1980. An O(| IV| | E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS'80). IEEE Computer Society, 17--27. Google ScholarDigital Library
- Niedermeier, R. 2006. Invitation to Fixed Parameter Algorithms. Oxford University Press.Google Scholar
- Raman, V., Saurabh, S., and Subramanian, C. R. 2002. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02). Lecture Notes in Computer Science, vol. 2518. Springer, 241--248. Google ScholarDigital Library
- Raman, V., Saurabh, S., and Subramanian, C. R. 2005. Faster algorithms for feedback vertex set. Electron. Not. Discr. Math. 19, 273--279.Google ScholarCross Ref
- Razgon, I. 2006. Exact computation of maximum induced forest. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT'06). Lecture Notes in Computer Science, vol. 4059. Springer, 160--171. Google ScholarDigital Library
- Schrijver, A. 2001. A short proof of Mader's S -paths theorem. J. Combin.Theory, Ser. B 82, 319--321. Google ScholarDigital Library
Index Terms
- A 4k2 kernel for feedback vertex set
Recommendations
A Cubic Kernel for Feedback Vertex Set and Loop Cutset
Special Issue: Theoretical Aspects of Computer ScienceThe Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a ...
Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization
A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the ...
Simultaneous Feedback Vertex Set: A Parameterized Perspective
For a family F of graphs, a graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex ...
Comments