# Is optimal equal-point graph splitting NP-Complete?

The problem is "Given a graph G with kn points, divide it into k pages of n points such that the number of edges between points on different pages is minimal." (I've worked on it with undirected graphs, but I think the basic problem is the same with directed graphs and multigraphs.) I've attacked with branch and bound and linear programming, and it's behaved as an NP-complete program--a 12 point, 4 page problem is solved almost instantly, but a 40 point, 8 page problem took over a day. Then again, those are solutions you use for NP-Complete problems. I see no obvious reduction of 3SAT or Travelling Salesman into it, but it feels like an NP-Complete problem--though that may be because I took a class on solving NP-Complete problems, so hammer and nail.

-

Editing my answer to give a stronger result:

The problem is NP-hard for k=2 and called the Minimum Bisection Problem.

-
Wouldn't all the vertices from the original graph just end up on the same page? – user2357112 May 28 '14 at 2:27
I'll accept, as you said before you edited the answer, that branch-and-bound with linear relaxation will solve certain problems in P in exponential time. But there's no standard way to solve problems in P in polynomial time, is there? – prosfilaes May 31 '14 at 3:35

I have an old and very obscure paper on a very similar problem: Given a graph with $kn$ vertices, divide it into $k$ subsets of $n$ vertices such that the number of pairs of subsets that have at least one edge connecting them is minimal. It also turns out to be NP-complete, and an easy probabilistic argument shows that even for very sparse graphs the number of pairs that must be connected can be high.

See:

Equipartitions of graphs. D. Eppstein, J. Feigenbaum, and C.L. Li. Discrete Mathematics 91(3):239-248, 1991. http://dx.doi.org/10.1016/0012-365X(90)90233-8

-