- INSTANCE:
A network
where
is a graph,
is the vertex-capacity function, and
is the
edge-capacity function, and a set
*T*of tokens where and*p*is either a path from*u*to*v*or the empty set. - SOLUTION:
A schedule
*S*, i.e., a sequence of configuration functions such that- 1.
- for any token
,
and ,
- 2.
- for any
and for any token
*t*, if and then (a) , (b) , (c) , and (d) .

- MEASURE:
The length of the schedule, i.e.,
*l*.

*Bad News:*Not in APX [117].*Comment:*Reduction from MINIMUM GRAPH COLORING. It remains non-approximable even for layered graphs. The variation in which the vertex-capacity is unbounded and the delay, i.e., the maximum number of times a token is neither in the final destination nor moved, must be minimized is also non-approximable within for any [136].