Technical Report 215-1989
- Title
- Graph Separation is NP-hard even for Graphs with Bounded Degree
- Authors
- Dorothea Wagner and Frank Wagner
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
One of the basic problems in VLSI-layout is the construction of a minimal decomposition of a graph, i.e. a partition or cut of the vertex-set into two pieces of not too different size which cuts the least possible number of edges. Not too different means that the size of each of the parts is at least a constant fraction of the total number of the graph vertices. We show that (the decision version of) this problem is cal NP-hard. The result holds even if the graphs to be separated have maximal degree four, a typical restriction in the theory of VLSI layout.