<p>Indeed, it can be solved in polynomial time.  This is a result by <a href="http://dx.doi.org/10.1016/0095-8956%2885%2990046-2">Frank (1985)</a>.</p>

CC BY-SA 3.0
2013-01-31T11:53:49.087Z
(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
CC BY-SA 3.0
2013-01-31T10:28:55.197Z
2013-01-31T10:28:55.197Z
Yoshio Okamoto
<p>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.  </p>

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

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

<cc.complexity-theory><np-hardness><scheduling>
$NP$-hardness of scheduling problem
Kuhndog
# $NP$-hardness of scheduling problem

(Asked by: username_0 on 2013-01-30)

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

**Tags:** cc.complexity-theory, np-hardness, scheduling

---

## 1 answers

### Answer by username_1 on 2013-01-31. Score: 10 | Accepted answer

Indeed, it can be solved in polynomial time. This is a result by [Frank (1985)](http://dx.doi.org/10.1016/0095-8956%2885%2990046-2).

> **Comments:**
> **username_2**: (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)  

---

