Feedback Vertex Set (FVS)

The Feedback Vertex Set (FVS) problem is a computational problem in computer science and graph theory that involves finding the smallest possible subset of vertices in an undirected graph such that removing those vertices results in a graph that is acyclic, i.e., a forest. The goal of the FVS problem is to minimize the size of the feedback vertex set, and is considered NP-hard, meaning that finding the optimal solution is computationally difficult. For directed graphs, a feedback vertex set is instead a subset of vertices whose removal results in directed acyclic graph (DAG), not necessarily a forest. This task can refer to either looking for a set of provably minimal size (in as little time as possible), or a heuristic algorithm that produces small solutions quickly (but which may have even smaller sets).