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

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 scaling technique for finding feedback vertex sets in un-weighted directed graphs that runs in $O(|F|ln(|V|)|V|^{2})$ time. Our technique seems to produce smaller feedback vertex sets than other known heuristics in a shorter amount of time.

Speaker Bio: Dr James Shook obtained a B.S. in Mathematics from the University of Maryland. With the support of a GAANN fellowship he earned a M.S. and Ph.D. in Mathematics from the University of Mississippi. James started in August 2011, as a National Research Council Postdoctoral Research Associate in the Applied and Computational Mathematics Division in the ITL at NIST. Dr. Shook is interested in structural graph theory and the evolution of affiliations in social networks.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.