Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been attempting to show that this problem is NP -complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it.

CALLS : Suppose we have nodes $\{0,…,n−1\}$ , with undirected edges between $(i \mod n,i+1 \mod n)$ for all $i$. Furthermore, suppose we have a set C of calls, which are the form $(i \mod n, j \mod n)$ , and an integer $K$ . The problem is to determine whether it is possible to schedule the set of calls (to schedule a call, one decides whether to go clockwise around the circle or counterclockwise) such that the maximum load (i.e. number of calls going through a given edge) is $\le K$ .

I have been able to show that if we assign each call a weight the problem is NP -complete by reducing PARTITION to it. However, I haven't been able to reduce any NP -complete problem to unweighted CALLS .

share|cite|improve this question
Isn't counting the number of calls going through a given edge the same as assigning each call the weight, one? – Gerry Myerson Jan 31 '13 at 0:12
Yes, it should be. – Kuhndog Jan 31 '13 at 23:34
So then doesn't that settle it? – Gerry Myerson Jan 31 '13 at 23:37
Answer was posted here:… . It's more complicated than turning the calls into weights, but can be done in polynomial time. – usul Feb 1 '13 at 14:35

Your Answer


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

Browse other questions tagged or ask your own question.