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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Editing my answer to give a stronger result:
The problem is NP-hard for k=2 and called the Minimum Bisection Problem.
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.
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