3
$\begingroup$

Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$.

The problems starts with $n$ tokens on $s$.

The goal is to move theses tokens to $t$ in a minimum of rounds with these rules :

  • Each token can be moved up to once per round (a movement being when you transfer the token from $v$ the vertex that holds it, to $w \in N_G(v)$).
  • Each vertex $v \in V\backslash \left\{s, t\right\}$ can hold at most one token ($s$ and $t$ are unconstrained).

So far, what I've thought to is :

  • If $N_G(s)=0$ or $N_G(t)=0$, it is not possible.
  • If $N_G(s)=1$ or $N_G(t)=1$, you can just apply a BFS from $s$ to find the shortest path, then transfer every token one by one trough this path.
  • If $N_G(s) \geq 2$ and $N_G(t) \geq 2$ you can apply a maximum flow algorithm on $G$ with $1$ as capacity for every edge. If the maximum flow is $1$ then you can apply a BFS and transfer every token through this path again. However if the maximum flow is $\geq 2$, then I don't really see what to do (having a maximum flow $\geq 2$ doesn't even guarantee there are multiple paths as nodes can hold at most $1$ token, while max flow tests only for edges, and even if there are multiple paths in some cases it can be better to use only the shortest path - e. g. for $2$ tokens if you have to paths but one is at least to edges longer -).

Does this problem have a name? What topic of graph theory does it belongs to? Are there efficient algorithms to solve it?

Improve this question
$\endgroup$
5
  • $\begingroup$ @Raphael : Well I know basics but I'm not so familiar. And I don't see how to modelise this 'round by round' thing with network flows $\endgroup$
    – servabat
    Commented Aug 19, 2015 at 12:14
  • $\begingroup$ First of all, there are flow problems/models with vertex capacities. Another thought is to look at disjoint paths, see e.g. here or here. $\endgroup$
    – Raphael
    Commented Aug 19, 2015 at 12:22
  • $\begingroup$ @Raphael : so after reading the resources you linked my impression is I should : 1. Split each node $v \in V\backslash \left\{s, t\right\}$ into two vertices $v_{\text{in}}$ and $v_{\text{out}}$ linked by a unitary capacity edge (possibly on a "working copy") 2. Apply a min vertex cut (i. e. max flow with vertex capacity) to get $m$, the maximum number of vertex-disjoint paths 3. Apply a min cost flow for each $k\in 1..m$ 4. Route the token trough the found paths (using some modular arithmetic I guess). Is that right? Or is it an unefficient approach ? $\endgroup$
    – servabat
    Commented Aug 22, 2015 at 9:42
  • $\begingroup$ That's seems to be essentially what Yuval proposes, yes. I don't know if it's optimal (as Yuval claims to prove) but it's definitely a reasonable approach. $\endgroup$
    – Raphael
    Commented Aug 22, 2015 at 11:58
  • $\begingroup$ @Raphael : Ok, thanks, I actually didn't understood Yuval answer but I guess I'm just not advanced enough in cs for that. $\endgroup$
    – servabat
    Commented Aug 22, 2015 at 12:00

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Since these paths can have different lengths, I don't see how these "rounds" give a lower bounds on total runtime. We may be able to route faster than send $n/m$ tokens via each path. Also, saying $d(s,t) \in O(1)$ is stretching the meaning of asymptotic notation (too far, imho). Or am I missing something? $\endgroup$
    – Raphael
    Commented Aug 19, 2015 at 21:07
  • $\begingroup$ @Raphael You may be assuming that $n$ is the number of vertices, but this is not mentioned anywhere. The argument shows that as a function of $n$, the number of rounds is asymptotic to $n/m$. Regarding the lower bound, 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$. $\endgroup$
    – Yuval Filmus
    Commented Aug 19, 2015 at 21:13
  • $\begingroup$ What do you mean with "common value"? $\endgroup$
    – servabat
    Commented Aug 22, 2015 at 9:45
  • $\begingroup$ The common value is the maximum number of $s$-$t$ internally vertex-disjoint paths, which equals the minimum size of an $s$-$t$ vertex cut. $\endgroup$
    – Yuval Filmus
    Commented Aug 22, 2015 at 11:30

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.