On computing the minimum feedback vertex set of a directed graph by contraction operations

Finding the minimum feedback vertex set (MFVS) in a graph is an important p roblem for a variety of computer-aided design (CAD) applications and graph reduction plays an important role in solving this intractable problem. This paper is largely concerned with three new and powerful reduction operation s. Each of these operations defines a new class of graphs, strictly larger than the class of contractible graphs [Levy and Low (1988)], in which the M FVS can be found in polynomial-time complexity. Based on these operations, an exact algorithm run on branch and bound manner is developed. This exact algorithm uses a good heuristic to find out an initial solution and a good bounding strategy to prune the solution space. To demonstrate the efficienc y of our algorithms, we have implemented our algorithms and applied them to solving the partial scan problem in ISCAS'89 benchmarks. The experimental results show that if our three new contraction operations are applied, 27 o ut of 31 circuits in ISCAS'89 benchmarks can be fully reduced. Otherwise, o nly 12 out of 31 can be fully reduced. Furthermore, for all ISCAS'89 benchm arks our exact algorithm can fmd the exact cutsets in less than 3 s (CPU ti me) on SUN-UltraII workstation. Therefore, the new contraction operations a nd our algorithms are demonstrated to be very effective in the partial scan application.