Exact Algorithms
The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347n), where n is the number of vertices in the graph. This algorithm actually computes a maximum induced forest, and when such a forest is obtained, its complement is a minimum feedback vertex set. The number of minimal feedback vertex sets in a graph is bounded by O(1.8638n). The directed feedback vertex set problem can still be solved in time O*(1.9977n), where n is the number of vertices in the given directed graph. The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.
Read more about this topic: Feedback Vertex Set
Famous quotes containing the word exact:
“To conclude, The Light of humane minds is Perspicuous Words, but by exact definitions first snuffed, and purged from ambiguity; Reason is the pace; Encrease of Science, the way; and the Benefit of man-kind, the end.”
—Thomas Hobbes (1579–1688)