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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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
    Commented Jan 31, 2013 at 11:53

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.