In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest FVS. Whether there exists a feedback vertex set of size at most k is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.
The FVS decision problem is as follows:
The graph that remains after removing from is an induced forest (resp. an induced directed acyclic graph in the case of directed graphs). Thus, finding a minimum FVS in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs).
showed that finding a feedback vertex set of size in directed graphs is NP-complete. The problem remains NP-complete on directed graphs with maximum in-degree and out-degree two, and on directed planar graphs with maximum in-degree and out-degree three.
Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-complete on graphs of maximum degree four. The feedback vertex set problem can be solved in polynomial time on graphs of maximum degree at most three, using an algorithm based on the matroid parity problem.
The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347<sup>n</sup>), 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.8638<sup>n</sup>). The directed feedback vertex set problem can still be solved in time O*(1.9977<sup>n</sup>), 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.
In undirected graphs of maximum degree three, the feedback vertex set problem can be solved in polynomial time, by transforming it into an instance of the matroid parity problem for linear matroids.
The special case of finding all feedback vertices in a directed graph (vertices that lie on every directed cycle) can be solved in linear time using a DFS-based algorithm by Garey and Tarjan.
The undirected problem is APX-complete. This follows from the following facts.
The best known approximation algorithm on undirected graphs is by a factor of two.
By contrast, the directed version of the problem appears to be much harder to approximate. Under the unique games conjecture, an unproven but commonly used computational hardness assumption, it is NP-hard to approximate the problem to within any constant factor in polynomial time. The same hardness result was originally proven for the closely related feedback arc set problem, but since the feedback arc set problem and feedback vertex set problem in directed graphs are reducible to one another while preserving solution sizes, it also holds for the latter.
According to the Erdà ÂsâÂÂPósa theorem, the size of a minimum feedback vertex set is within a logarithmic factor of the maximum number of vertex-disjoint cycles in the given graph.