Beneš Conjecture (graph-theoretic form)

Importance: High ✭✭✭
Author(s): Beneš, Václav E.
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Vadim Lioubimov
on: April 17th, 2010

\begin{problem}[$\dag$] Find a sufficient condition for a straight $\ell$-stage graph to be rearrangeable. In particular, what about a straight uniform graph? \end{problem}

\begin{conjecture}[$\diamond$] Let $L$ be a simple regular ordered $2$-stage graph. Suppose that the graph $L^m$ is externally connected, for some $m\ge1$. Then the graph $L^{2m}$ is rearrangeable. \end{conjecture}

Given an integer $\ell\ge2$, an \emph{$\ell$-stage graph} is an $\ell$-partite graph $G$ with a list of its parts $V_1,\dots,V_{\ell}$ such that every edge of $G$ has endpoints in both $V_i$ and $V_{i+1}$, for some $i\in[\ell-1]$. A vertex in $V_1$ ($V_\ell$) is a \emph{source} (\emph{target}) of $G$. A path in $G$ is \emph{plain} if it goes from a source to a target through each part of $G$ exactly once. The graph $G$ is \emph{externally connected} if for every source $s$ and target $t$ there exists a plain path from $s$ to $t$. A \emph{mask} for $G$ is a $2$-stage multigraph $M$ whose sources and targets are exactly those of $G$ and such that every vertex of $M$ has the same degree in $G$. The graph $G$ is \emph{rearrangeable} if for every its mask there exists a collection, called \emph{routing}, of corresponding mutually edge-disjoint plain paths in $G$.

The graph $G$ is \emph{ordered} if each of its parts is linearly ordered. The graph $G$ is \emph{uniform} and denoted $B^{\ell-1}$ if there is an ordered 2-stage graph $B$ with equal-sized parts such that $G$ is the proper (i.e., respecting all the orders in $B$) concatenation of $\ell-1$ identical copies of $B$. The graph $G$ is \emph{straight} if for any $2\le i\le\ell-1$ and any $v\in V_i$, the number of edges joining $v$ with $V_{i-1}$ equals that of $V_{i+1}$.

Conjecture ($\diamond$) can be reformulated as $R(L) \le 2F(L)$, where $R(B)$ ($F(B)$) denotes the smallest positive integer $n$, or $\infty$ if none exists, such that the graph $B^n$ is rearrangeable (externally connected).


Consider the simple 2-regular $2$-stage ordered graphs $A, C, D$ shown in Fig.1. It is easy to see that $F(A) = 2$ and $F(C) = F(D) = 3$ (the corresponding externally connected graphs $A^2, C^3, D^3$ are depicted in blue). Therefore, according to Conjecture ($\diamond$), the graphs $A^4, C^6, D^6$ should be rearrangeable, which is indeed the case. The graph $A$ is the \OPrefnum[2-stage Shuffle-exchange graph $\text{SE}(2,3)$]{37089}, and there are several nice \OPrefnum[proofs known for $R(A)=4$]{37167}. Although I am not aware of any theoretical proof for rearrangeability of $C^5$ or $D^6$, I have verified by brute force without difficulty that $R(C)=5$ and $R(D)=6$.

\Image{Garden-Benes 1.gif}

\textbf{Figure 1.} Examples for Conjecture ($\diamond$).

\section{Link to Beneš Conjecture}

Problem ($\dag$) and Conjecture ($\diamond$) are equivalent "graph-theoretic" forms of \OPrefnum[Problem ($\star$) and Beneš conjecture]{37181} [B75], respectively.

The equivalence is based on the natural bijection (up to isomorphism) between the $\ell$-systems of partitions and the straight $\ell$-stage graphs, given any $\ell\ge2$. Here an \emph{$\ell$-system} of partitions is an $\ell$-tuple ${\bf H} :=({\bf h}_1,\dots,{\bf h}_\ell)$ of partitions of some finite set $E$. The image of ${\bf H}$ under this bijection is the straight $\ell$-stage graph denoted $G({\bf H})$ and defined as follows. The edge set of $G({\bf H})$ is $[\ell-1]\times E$, the $i$th vertex part is $U_i:=\{i\}\times {\bf h}_i$, for all $i\in[\ell]$, and the edge-vertex incidence is such that every edge $(j,e)$ has endpoints $(j,a)\in U_j$ and $(j+1,b)\in U_{j+1}$ uniquely determined by $e\in a\cap b$.

The bijection ${\bf H} \mapsto G({\bf H})$ provides a convenient two-way link between the frameworks for Problems \OPrefnum[($\star$)]{37181} and ($\dag$) via numerous easily seen equivalences. Here is some basic ones:

\begin{itemize} \item Simplicity of $G({\bf H})$ is equivalent to the condition ${\bf h}_i\wedge{\bf h}_{i+1}={\bf 0}$, for all $i\in[\ell-1]$. \item Uniformity of $G({\bf H})$ is equivalent to the existence of a permutation $\delta$ of $E$ such that ${\bf h}_{i+1}=\delta ({\bf h}_i)$, for all $i\in[\ell-1]$.

\item $k$-quasi-regularity of $G({\bf H})$ is equivalent to every block of ${\bf h}_i$ being of size $k$, for all $i\in[\ell]$. Here the graph $G$ is \emph{$k$-quasi-regular} if the induced bipartite subgraph on $V_i\cup V_{i+1}$ is $k$-regular, for all $i\in[\ell-1]$. Note that a quasi-regular multistage graph is straight. Also, $k$-quasi-regularity of $B^n$ is equivalent to $k$-regularity of $B$.

\item External connectivity of $G({\bf H})$ is equivalent to transitivity of $S({\bf h}_\ell)\dots S({\bf h}_2)S({\bf h}_1)$.

\item Given a permutation $\xi$ of $E$, the membership $\xi \in S({\bf h}_1)S({\bf h}_2) \dots S({\bf h}_\ell)$ is equivalent to routability of the mask $M(\xi)$ for $G({\bf H})$ defined as follows. The edge set of $M(\xi)$ is $E$ and the edge-vertex incidence is such that every edge $e\in E$ has endpoints $(1,a)\in U_1$ and $(\ell,b)\in U_{\ell}$ uniquely determined by $e\in \xi^{-1}(a)\cap b$. Note that given ${\bf H}$, the map $\xi \mapsto M(\xi)$ is surjective (but generally not injective).

\item Consequently, rearrangeability of $G({\bf H})$ is equivalent to universality of ${\bf H}$. Here ${\bf H}$ is \OPrefnum[\emph{universal}]{37181} if it satisfies $\frak S(E) = S({\bf h}_1)S({\bf h}_2) \dots S({\bf h}_\ell)$.

\item If $G({\bf H})$ is rearrangeable, then any routing algorithm for $G({\bf H})$ easily translates to a \OPrefnum[factorization algorithm]{37181} of the same complexity for the latter identity, and vise versa. Here, given a rearrangeable multistage graph, a \emph{routing algorithm} is one that takes a mask of the graph as input and returns a corresponding routing.

\item Contracting all edges between $U_i$ and $U_{i+1}$ in $G({\bf H})$ is equivalent to replacing the partitions ${\bf h}_i$ and ${\bf h}_{i+1}$ in ${\bf H}$ with their supremum ${\bf h}_i\vee{\bf h}_{i+1}$, given any fixed $i\in[\ell-1]$. In other words, $G_i=G({\bf H}_i)$, where $G_i$ is the contracted graph and ${\bf H}_i:=({\bf h}_1,\dots,{\bf h}_i\vee{\bf h}_{i+1},\dots,{\bf h}_\ell)$. In fact, the procedure ${\bf H} \mapsto {\bf H}_i$ preserves universality of ${\bf H}$, as $S({\bf h}_i)S({\bf h}_{i+1})\subseteq S({\bf h}_i\vee{\bf h}_{i+1})$. Equivalently, the procedure $G({\bf H}) \mapsto G_i$ preserves rearrangeability of $G({\bf H})$.



Although the presented graph-theoretic statement ($\dag$) of \OPrefnum[Problem ($\star$)]{37181} may look more complex, it provides somewhat more intuitive framework to study the problem and, in particular, \OPrefnum[Beneš conjecture]{37181}. To illustrate this, let us now reconsider in terms of this framework and in more detail the 3 counterexamples for some extensions of Beneš conjecture discussed \OPrefnum[here]{37181}.

\textbf{1.} The condition of simplicity of the graph $L$ (essentially missing in the original statement [B75] of Beneš conjecture) is necessary for Conjecture ($\diamond$). To see this, consider the following 2-stage 3-regular non-simple ordered graph $Q$:

\Image{Garden-Benes 2.gif}

Whereas $Q$ is obviously externally connected, the graph $Q^2$ is not rearrageable. This is because it is evidently impossible to connect the two red vertices in $Q^2$ (a source and a target) with 3 mutually edge-disjoint plain paths.

\textbf{ 2.} Conjecture ($\diamond$) is not directly generalizable to non-uniform graphs. More precisely, the condition of uniformity of $X$ is necessary for the following reformulation of ($\diamond$):

\begin{conjecture} Let $X$ be a simple quasi-regular ordered multistage graph. Suppose that $X$ is uniform and externally connected. Then the graph $X^{2}$ is rearrangeable. \end{conjecture}

Here $X^{2}$ denotes the proper concatenation of 2 identical copies of $X$. To see the necessity, consider the following simple 4-stage 2-quasi-regular non-uniform ordered graph $Y$:

\Image{Garden-Benes 3.gif}

Whereas $Y$ is obviously externally connected, the graph $Y^2$ is not rearrangeable. To see this, recall that contracting all edges between two consecutive parts in a straight multistage graph preserves its rearrangeability. Therefore, if $Y^2$ were rearrangeable then so would be the 3-stage graph $W$ obtained from $Y^2$ by contracting all edges in the shadowed areas. However, this is not true as it is evidently impossible to connect the two red vertices in $W$ (a source and a target) with 4 mutually edge-disjoint plain paths.

\textbf{ 3.} The stronger version of Conjecture ($\diamond$) (proposed essentially in the same paper [B75]), claiming that $R(L) = 2F(L)$, is false. The graph $C$ shown in Fig.1 is a counterexample as $R(C) = 2F(C)-1$.

More information on Problem ($\dag$) and Conjecture ($\diamond$) can be found \OPrefnum[here]{37181} (via Problem ($\star$) and Beneš conjecture).


*[B75] V.E. Beneš, \emph {Proving the rearrangeability of connecting networks by group calculation}, Bell Syst. Tech. J. \textbf{54} (1975), 421-434.

* indicates original appearance(s) of problem.