Vertex Bisection is Hard, too

Abstract

We settle an open problem mentioned in Diaz, Petit, and Serna: A survey of graph layout problems (ACM Computing Surveys 34:313-356, 2002). Of eight objectives considered in that survey, only the complexity status of minimum vertex bisection is listed as unknown. We show that both minimum and maximum vertex bisection are NP-hard, but polynomially solvable on special graph classes such as hypercubes and trees.