On locating minimum feedback vertex sets

摘要

In this paper we study the problem of locating minimum feedback vertex sets in directed graphs. First, we introduce three new transformation-based classes of graphs for which minimum feedback vertex sets can be computed in polynomial time. Second, we delineate an inclusion hierarchy among all of the classes of graphs for which polynomial time feedback vertex set algorithms presently exist. Among the classes of graphs included in the hierarchy are: the reducible flow graphs, the cyclically reducible graphs, the three transformation-based classes that we introduce, and an infinite sequence of classes based on an algorithm of Smith and Walford for finding minimum feedback vertex sets in arbitrary graphs. It follows from our results that one of our new classes, as well as each “Smith/Walford” class, properly includes both the reducible flow graphs and the cyclically reducible graphs. The results presented here serve to unify and focus the work on locating minimum feedback vertex sets in polynomial time.