Feedback vertex set

The feedback vertex set number of a graph is the size of a smallest FVS.

Karp (1972) showed that finding a feedback vertex set of size

[2] 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.

The number of minimal feedback vertex sets in a graph is bounded by O(1.8638n).

[6] 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.

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.

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.

Removing the red vertices and all edges connected to them leaves the graph with no cycles. Thus, the set of vertices is a feedback vertex set (FVS) of the graph. In this case, there is no FVS which has a number of vertices less than the ones shown in the graph, making them a minimum FVS for their respective graph. The FVS number for a graph is this minimum amount as well.