Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem

James M. Shook, Isabel Beichl

For a digraph $G$, a set $F\subseteq V(G)$ is said to be a feedback vertex set (FVS) if $G-F$ is acyclic. The problem of finding a smallest FVS is NP-hard. We present a matrix scal…