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:
“If we define a sign as an exact reference, it must include symbol because a symbol is an exact reference too. The difference seems to be that a sign is an exact reference to something definite and a symbol an exact reference to something indefinite.”
—William York Tindall (1903–1981)