Constant-factor hardness of directed feedback vertex setResearch Paper
A directed feedback vertex set of a finite digraph is a set of vertices meeting every directed cycle, equivalently one whose removal leaves acyclic; is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of cert…