A feedback vertex set of a graph, also known as a decylcling 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 et number of a graph.
In 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 
.
