The minimum bisection problem of partitioning a graph into equal (or nearly equal) sized subgraphs by deleting a minimum number of edges has many applications, but is well known to be NP-hard. A variation of the problem, that of partitioning the graph by deleting nodes instead of edges, is also known to be NP-hard. This paper shows that the problem of block folding used to reduce the area in PLA design is equivalent to this vertex separator problem and hence is NP-hard. The authors then consider the  &agr;-vertex  separator problem (where the partitions need only be nearly equal in size) and show that even this easier problem is  NP-complete  (this statement is true even for 3-regular graphs).

The paper is well written and fairly self-contained but theoretical. The emphasis is on proving the NP-hardness of the problems; we do not get any guidelines on how to solve the &agr;-vertex separator problem in general. The equivalence between the block folding and vertex separator problems is particularly interesting.