4
$\begingroup$

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.

$\endgroup$

2 Answers 2

9
$\begingroup$

Editing my answer to give a stronger result:

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

$\endgroup$
2
  • $\begingroup$ Wouldn't all the vertices from the original graph just end up on the same page? $\endgroup$ 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$
    – prosfilaes
    May 31, 2014 at 3:35
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.