A feedback vertex set of a graph, also known as a decycling set, is a set of vertices which, when removed from the graph (together with any adjacent edges), produces an acyclic graph. The size of a smallest feedback vertex set is known as the feedback vertex set number of a graph.
It is an NP-complete problem to determine if there exists a feedback vertex set of size 
for directed graphs (Karp
1972). While the feedback vertex set problem can be solved in polynomial time for
undirected graphs with maximum vertex degree 
, it remains NP-complete
for undirected graphs with 
.
