Skip to main content
2 of 2
Clarify, and address Raphael's comment.
D.W.
  • 165.6k
  • 21
  • 230
  • 490

Menger's theorem states that the maximum number of $s$-$t$ (internally) vertex-disjoint paths is equal to the minimum size of an $s$-$t$ vertex cut. Let the common value be $m$. Then it can be shown that the asymptotic number of rounds required is $n/m + O(1)$.

Using the vertex disjoint paths, we can route $n$ tokens in $n/m + O(1)$ rounds, where the constant depends on the graph $G$ (but not on $n$). This gives an upper bound.

On the other hand, every token must pass through the vertex cut, and at most $m$ can do so at any given round, so routing $n$ tokens takes at least $n/m$ rounds. (For each token, there must be a first time at which it reaches a vertex in the cut. Each such time can repeat at most $m$ times, since at most $m$ vertices of the cut can be occupied at any given time. So the number of rounds is at least $n/m$.) This gives a matching lower bound.

From these two bounds, we deduce that the asymptotic number of rounds required is $n/m + O(1)$.

Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512