2025/03/13 by James M. Shook, Shook, James M., Isabel Beichl +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2503.10780
openalex publication_date 2025/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a digraph G, a set F⊆ 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|log(|V|)|V|2) time. Our technique is empirically shown to produce smaller feedback vertex sets than other known heuristics and in a shorter amount of time.