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.