An efficient algorithm for set-to-set node-disjoint paths problem in hypercubes

Set-to-set node-disjoint paths problem is that given two sets S={s ₁,...,s_k} and T={t₁,...,t_k} of nodes in a graph, find k node disjoint paths s_i→t_ji, where (j₁,...,jk) is a permutation of (1,...,k). For general undirect graphs G(V,E), this problem is usually solved by applying flow techniques which take Poly(|V|) time. In this paper, we give an algorithm which, given S={s ₁,...,s_k} and T={t₁,...,t_k}, 1⩽k⩽n, in an n-dimensional hypercube H_n which has 2 ⁿ nodes, finds the k disjoint paths s_i→t_ji of length at most n+log k+2 in O(kn log* k) time. This improves the previous results of n+k and O(kn log k), respectively