<p>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.</p>

<p>See:</p>

<p>Equipartitions of graphs.
D. Eppstein, J. Feigenbaum, and C.L. Li.
Discrete Mathematics 91(3):239-248, 1991.
<a href="http://dx.doi.org/10.1016/0012-365X%2890%2990233-8" rel="nofollow">http://dx.doi.org/10.1016/0012-365X(90)90233-8</a></p>

CC BY-SA 3.0
2014-05-28T00:02:05.640Z
2014-05-28T00:02:05.640Z
David Eppstein
<p>Editing my answer to give a stronger result:</p>

<p>The problem is NP-hard for k=2 and called the <a href="http://www.wisdom.weizmann.ac.il/~robi/papers/FK-bisection2-SIGEST.pdf">Minimum Bisection Problem</a>.</p>

CC BY-SA 3.0
2014-05-28T02:27:34.240Z
Wouldn't all the vertices from the original graph just end up on the same page?
user2357112
CC BY-SA 3.0
2014-05-31T03:35:31.470Z
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
CC BY-SA 3.0
2014-05-27T22:18:41.733Z
2014-05-28T05:28:14.170Z
2014-05-28T05:28:14.170Z
R B
<p>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.</p>

<cc.complexity-theory><graph-algorithms>
Is optimal equal-point graph splitting NP-Complete?
prosfilaes
# Is optimal equal-point graph splitting NP-Complete?

(Asked by: username_0 on 2014-05-27)

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.

**Tags:** cc.complexity-theory, graph-algorithms


---

## 2 answers

### Answer by username_2 on 2014-05-27. Score: 9 | Accepted answer

Editing my answer to give a stronger result:

The problem is NP-hard for k=2 and called the [Minimum Bisection Problem](http://www.wisdom.weizmann.ac.il/~robi/papers/FK-bisection2-SIGEST.pdf).

> **Comments:**
> **username_3**: Wouldn't all the vertices from the original graph just end up on the same page?  
> **username_0**: 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?  

---

### Answer by username_1 on 2014-05-28. Score: 4

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](http://dx.doi.org/10.1016/0012-365X%2890%2990233-8)


---

