Abstract
We present a time \(\mathcal {O}(1.7548^{n})\) algorithm finding a minimum feedback vertex set in an undirected graph on n vertices. We also prove that a graph on n vertices can contain at most 1.8638n minimal feedback vertex sets and that there exist graphs having 105n/10≈1.5926n minimal feedback vertex sets.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12, 289–297 (1999)
Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27, 942–959 (1998)
Björklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 575–582. IEEE Computer Society, Los Alamitos (2006)
Brunetta, L., Maffioli, F., Trubian, M.: Solving the feedback vertex set problem on undirected graphs. Discrete Appl. Math. 101, 37–51 (2000)
Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547–556 (2004)
Byskov, J.M., Madsen, B.A., Skjernaa, B.: On the number of maximal bipartite subgraphs of a graph. J. Graph Theory 48, 127–132 (2005)
Cai, M.-C., Deng, X., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27, 361–371 (2002)
Chen, J., Liu, Y., Lu, S.: Directed feedback vertex set problem is FPT. Dagstuhl Seminar Series, Seminar 07281 (2007), available electronically at http://kathrin.dagstuhl.de/files/Materials/07/07281/07281.ChenJianer.Paper.pdf
Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22, 111–118 (1998)
Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Comput. Sci., vol. 3595, pp. 859–869. Springer, Berlin (2005)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math. 13, 255–267 (2000)
Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of Combinatorial Optimization, Supplement vol. A, pp. 209–258. Kluwer Academic, Dordrecht (1999)
Fomin, F.V., Pyatkin, A.V.: Finding minimum feedback vertex set in bipartite graph. Reports in Informatics 291, University of Bergen (2005)
Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination—a case study. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes in Comput. Sci., vol. 3580, pp. 191–203. Springer, Berlin (2005)
Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. EATCS 87, 47–77 (2005)
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.: Bounding the number of minimal dominating sets: a measure and conquer approach. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005). Lecture Notes in Comput. Sci., vol. 3827, pp. 573–582. Springer, Berlin (2005)
Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a minimum feedback vertex set in time O(1.7548n). In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006). Lecture Notes in Comput. Sci., vol. 4169, pp. 184–191. Springer, Berlin (2006)
Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(20.288 n) independent set algorithm. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 18–25. ACM and SIAM, New York (2006)
Funke, M., Reinelt, G.: A polyhedral approach to the feedback vertex set problem. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Comput. Sci., vol. 1084, pp. 445–459. Springer, Berlin (1996)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Proceedings of the 9th International Workshop on Algorithms and Data Structures (WADS 2005). Lecture Notes in Comput. Sci., vol. 3608, pp. 36–48. Springer, Berlin (2005)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
Kleinberg, J., Kumar, A.: Wavelength conversion in optical networks. J. Algorithms 38, 25–50 (2001)
Koivisto, M.: An O(2n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583–590. IEEE Computer Society, Los Alamitos (2006)
Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23–28 (1965)
Pardalos, P.M., Qian, T., Resende, M.G.C.: A greedy randomized adaptive search procedure for the feedback vertex set problem. J. Comb. Optim. 2, 399–412 (1999)
Raman, V., Saurabh, S., Sikdar, S.: Improved exact exponential algorithms for vertex bipartization and other problems. In: Proceedings of the 9th Italian Conference on Theoretical Computer Science (ICTCS 2005). Lecture Notes in Comput. Sci., vol. 3701, pp. 375–389. Springer, Berlin (2005)
Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC 2002). Lecture Notes in Comput. Sci., vol. 2518, pp. 241–248. Springer, Berlin (2002)
Razgon, I.: Exact computation of maximum induced forest. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Comput. Sci., pp. 160–171. Springer, Berlin (2006)
Razgon, I.: Directed feedback vertex set is fixed-parameter tractable. Dagstuhl Seminar Series, Seminar 07281 (2007), available electronically at http://kathrin.dagstuhl.de/files/Submissions/07/07281/07281.RazgonIgor.Paper!.pdf
Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425–440 (1986)
Schwikowski, B., Speckenmeyer, E.: On enumerating all minimal solutions of feedback problems. Discrete Appl. Math. 117, 253–265 (2002)
Woeginger, G.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization—Eureka, You Shrink!. Lecture Notes in Comput. Sci., vol. 2570, pp. 185–207. Springer, Berlin (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Preliminary extended abstracts of this paper appeared in the proceedings of SWAT’06 [29] and IWPEC’06 [18].
Additional support of F.V. Fomin, S. Gaspers and A.V. Pyatkin by the Research Council of Norway.
The work of A.V. Pyatkin was partially supported by grants of the Russian Foundation for Basic Research (project code 05-01-00395), INTAS (project code 04–77–7173).
I. Razgon is supported by Science Foundation Ireland (Grant Number 05/IN/I886).
Rights and permissions
About this article
Cite this article
Fomin, F.V., Gaspers, S., Pyatkin, A.V. et al. On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica 52, 293–307 (2008). https://doi.org/10.1007/s00453-007-9152-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9152-0