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

James Shook
Applied and Computational Mathematics Division, NIST

Tuesday, June 10, 2014 15:00-16:00,
Building 225, Room B111
Gaithersburg
Tuesday, June 10, 2014 13:00-14:00,
Room 1-4058
Boulder

Abstract:

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

Contact: B. Cloteaux

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