Replica-symmetric solution of the graph-bipartitioning problem

Using techniques of the statistical mechanics of random systems, we present the replica-symmetric solution of the graph-bipartitioning problem. We demonstrate that, in the graph-bipartitioning problem with finite connectivity, it is incorrect to replace the constraint ${\mathcal{J}}_{i=1\mathrm{}}^N$ $S_i$=0 by a soft version of the constraint, namely, exp[-λ(${\mathcal{J}}_{i=1\mathrm{}}^N$ $S_i$ ${)}^2$] with λ≫1, in the calculation of the partition function. It is explicitly shown that the constraint must be strictly enforced in order to find the correct solution.