Nonpolyhedral Relaxations of Graph-Bisection Problems

We study the problem of finding the minimum bisection of a graph into two parts of prescribed sizes. We formulate two lower bounds on the problem by relaxing node- and edge- incidence vectors of cuts. We prove that both relaxations provide the same bound. The main fact we prove is that the duality between the relaxed edge- and node- vectors preserves very natural cardinality constraints on cuts. We present an analogous result also for the max-cut problem, and show a relation between the edge relaxation and some other optimality criteria studied before. Finally, we briefly mention possible applications for a practical computational approach.