Finding good approximate vertex and edge partitions is NP-hard

In this paper we show that for n-vertex graphs with maximum degree 3, and for any fixed ε> 0, it is NP-hard to find α-edge separators and α-vertex separators of size no more than OPT+n ^{1 2 - ε}, where OPT is the size of the optimal solutio n. For general graphs we show that it is NP-hard to find an α-edge separator of size no more than OPT+n^{2 - ε}. We also show that an O(f{hook}(n))-approximation algorithm for finding α-vertex separators of maximum degree 3 graphs can be used to find an O(f{hook}(n⁵))-approximation algorithm for finding α-edge separators of general graphs. Since it is NP-hard to find optimal α-edge separators for general graphs this means that it is NP-hard to find optimal vertex separators even when restricted to maximum degree 3 graphs.