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:
“Hunger makes you restless. You dream about food—not just any food, but perfect food, the best food, magical meals, famous and awe-inspiring, the one piece of meat, the exact taste of buttery corn, tomatoes so ripe they split and sweeten the air, beans so crisp they snap between the teeth, gravy like mother’s milk singing to your bloodstream.”
—Dorothy Allison (b. 1953)