7
$\begingroup$

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$.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ (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) $\endgroup$ – Marzio De Biasi Jan 31 '13 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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