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:
“The secret of genius is to suffer no fiction to exist for us; to realize all that we know; in the high refinement of modern life, in arts, in sciences, in books, in men, to exact good faith, reality, and a purpose; and first, last, midst, and without end, to honor every truth by use.”
—Ralph Waldo Emerson (1803–1882)