Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

Editing my answer to give a stronger result:

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

share|improve this answer
    
Wouldn't all the vertices from the original graph just end up on the same page? –  user2357112 May 28 at 2:27
    
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 May 31 at 3:35

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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