Feedback vertex set

Feedback vertex set --- разрывающее множество вершин.

Given a digraph [math]\displaystyle{ G = (V,A) }[/math], a subset [math]\displaystyle{ F \subseteq V }[/math] is called a feedback vertex set if a digraph [math]\displaystyle{ G' }[/math], induced by the vertex set [math]\displaystyle{ V \setminus F }[/math], is DAG. FVS-problem is the problem of looking for a minimum feedback vertex set. It is well known that FAS-problem can be reduced to the FVS-problem and vice versa.