Computing minimum feedback vertex sets by contraction operations and its applications on CAD

Finding the minimum feedback vertex set (MFVS) in a graph is an important problem for a variety of 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 operations. Each of these operations defines a new class of graphs, strictly larger than the class of contractible graphs, in which the MFVS 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. We have implemented our algorithms and applied them to solving the partial scan problem in ISCAS89 benchmarks. The experimental results show that for all ISCAS89 benchmarks our exact algorithm can find the exact cutsets in less than 3 seconds (CPU time) on SUN-Ultrall workstation.