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:
“He who asks fortune-tellers the future unwittingly forfeits an inner intimation of coming events that is a thousand times more exact than anything they may say. He is impelled by inertia, rather than curiosity, and nothing is more unlike the submissive apathy with which he hears his fate revealed than the alert dexterity with which the man of courage lays hands on the future.”
—Walter Benjamin (1892–1940)