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:
“For 350 years we have been taught that reading maketh a full man, conference a ready man and writing an exact man. Football’s place is to add a patina of character, a deference to the rules and a respect for authority.”
—Walter Wellesley (Red)