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.

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, \ldots, 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|improve this question
add comment

1 Answer

up vote 10 down vote accepted

Indeed, it can be solved in polynomial time. This is a result by Frank (1985).

share|improve this answer
3  
(split every edge $(u_i,u_{(i+1)\bmod n})$ of the circle in 2K edges $(u_i,z_{(i,j)})$ $(z_{(i,j)},u_{(i+1)\bmod n})$ j=1..K to convert the problem to the equivalent $k$ edge-disjoint paths on a planar graph problem) –  Marzio De Biasi Jan 31 '13 at 11:53
    
Wow, thanks guys! –  Kuhndog Feb 1 '13 at 2:15
add comment

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.