# Feedback vertex set

In the mathematical discipline of graph theory, a **feedback vertex set** of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.
The **feedback vertex set problem** is an NP-complete problem in computational complexity theory. It was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

## Contents

## Definition

The decision problem is as follows:

- INSTANCE: An (undirected or directed) graph and a positive integer .
- QUESTION: Is there a subset with such that with the vertices from deleted is cycle-free?

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 feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs).

## NP-hardness

Template:Harvtxt showed that the feedback vertex set problem for 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.^{[1]} Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-hard 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.^{[2]}

Note that the problem of deleting as few *edges* as possible to make the graph cycle-free is equivalent to finding a spanning tree, which can be done in polynomial time. In contrast, the problem of deleting edges from a directed graph to make it acyclic, the feedback arc set problem, is NP-complete.^{[3]}

## Exact algorithms

The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time *O*(1.7347^{n}), where *n* is the number of vertices in the graph.^{[4]} 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^{n}).Template:Sfnp The directed feedback vertex set problem can still be solved in time *O**(1.9977^{n}), where *n* is the number of vertices in the given directed graph.Template:Sfnp The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.Template:Sfnp

## Approximation

The problem is APX-complete, which directly follows from the APX-completeness of the vertex cover problem,^{[5]} and the existence of an approximation preserving L-reduction from the vertex cover problem to it.^{[3]} The best known approximation algorithm on undirected graphs is by a factor of two.^{[6]}

## Bounds

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.Template:Sfnp

## Applications

In operating systems, feedback vertex sets play a prominent role in the study of deadlock recovery. In the wait-for graph of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to abort.Template:Sfnp

Furthermore, the feedback vertex set problem has applications in VLSI chip design.Template:Sfnp

## Notes

- ↑ unpublished results due to Garey and Johnson, cf. Template:Harvtxt: GT7
- ↑ Template:Harvtxt; Template:Harvtxt
- ↑
^{3.0}^{3.1}Template:Harvtxt - ↑ Template:Harvtxt
- ↑ Template:Harvnb
- ↑ Template:Harvtxt. See also Template:Harvtxt for an alternative approximation algorithm with the same approximation ratio.

## References

### Research articles

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }} Template:Refend

### Textbooks and survey articles

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}