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 pr oblem by relaxing node- and edge-incidence vectors of cuts. We prove t hat both relaxations provide the same bound. The main fact we prove is that the duality between the relaxed edge- and node- vectors preserve s very natural cardinality constraints on cuts. We present an analogou s result also for the max-cut problem, and show a relation between the edge relaxation and some other optimality criteria studied before. Fi nally, we briefly mention possible applications for a practical comput ational approach.