Vertex Separator

I want to find a small balanced vertex separator. I tried using ndmetis, but this created a very unbalanced partition, one side had almost twice as many nodes as the other side.

Also, I tried some transformations to get an almost equivalent edge partitioning problem. I had to weight the vertices to do this. It caused a wrap-around error originally. shmetis put almost no nodes on one side, and the rest on the other, and the weight of the partition was comparable to the weight of some of the largest nodes. I scaled the weights down to avoid this, but I'm afraid I'm losing too much accuracy. Is there a way to make shmetis or hmetis use larger ints to not cause wraparound errors?

RE: There is an "undocumented"

There is an "undocumented" routine in lib/parmetis.c file called METIS_ComputeVertexSeparator, which does return a separator. The options[] array for it is similar to that for ndmetis.