# 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.

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.