Short reachability networks

Abstract

We investigate the following generalisation of permutation networks. We say a sequence $T=(T_1,\dots ,T_{\ell })$ of transpositions in $S_n$ forms a $t$-reachability network if, for every choice of $t$ distinct points $x_1,\dots ,x_t\in \{1,\dots ,n\}$, there is a subsequence of $T$ whose composition maps $j$ to $x_j$ for every $1\le j\le t$. When $t=n$, any permutation in $S_n$ can be created and $T$ is a permutation network. Waksman [JACM, 1968] showed that the shortest permutation networks have length about $n{\log }_2(n)$. In this paper, we investigate the shortest $t$-reachability networks for other values of $t$. Our main result settles the case of $t=2$: the shortest $2$-reachability network has length $\lceil 3n/2\rceil -2$. For fixed $t\ge 3$, we give a simple randomised construction which shows that there exist $t$-reachability networks with $(2+o_t(1))n$ transpositions. We also study the effect of restricting to star-transpositions, i.e. restricting all transpositions to have the form $(1,\cdot )$.

12 pages, 1 figure