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.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Editing my answer to give a stronger result:
The problem is NP-hard for k=2 and called the Minimum Bisection Problem.
-
$\begingroup$ Wouldn't all the vertices from the original graph just end up on the same page? $\endgroup$ Commented May 28, 2014 at 2:27
-
$\begingroup$ 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? $\endgroup$ Commented May 31, 2014 at 3:35
$\begingroup$
$\endgroup$
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
answered May 28, 2014 at 0:02