Graph bipartitioning problem

Replica-symmetric solutions of the graph-bipartitioning problem with finite connectivity are presented. With the constraint ${sum}_{\mathrm{i}=1\mathrm{}}^{\mathrm{N}}$ ${\mathrm{S}}_{\mathrm{i}}$=0 strictly enforced, another solution can be obtained, which gives a lower cost function than that given by the spin-glass solution. It is believed that this new solution is currently the best candidate for the true solution of the graph-bipartitioning problem.