On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

摘要

We present a time 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.8638~n minimal feedback vertex sets and that there exist graphs having 105~(n/10) ≈ 1.5926~n minimal feedback vertex sets.