(1985), reducing from a graph problem known as bisection width (see also Monien and Sudborough (1988)).
the authors construct a graph G ′ of maximum degree three and an integer k ′ from an input graph G = (V, E) with an even number n of vertices and an integer k, such that mcw(G ′ ) ≤ k ′ if and only if the bisection width bw(G) of G is not greater than k, where The graph G ′ has vertices of degree two and three only, and it is based on a grid-like gadget R(r, c); see Figure 5.