CentralNotice From Wikipedia, the free encyclopedia Jump to: navigation , search 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. 1 Definition 2 NP-hardness 3 Exact algorithms 4 Approximation 5 Bounds 6 Applications 7 Notes 8 References 8.1 Research articles 8.2 Textbooks and survey articles Definition [ edit ] The decision problem is as follows: INSTANCE: An (undirected or directed) graph and a positive integer . ...