Home » Subject » Graph Theory

Beneš Conjecture (graph-theoretic form)

Importance: High ✭✭✭
Author(s): Beneš, Václav E.
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: Vadim Lioubimov
on: April 17th, 2010
Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
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.

Given an integer $ \ell\ge2 $, an $ \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 source (target) of $ G $. A path in $ G $ is plain if it goes from a source to a target through each part of $ G $ exactly once. The graph $ G $ is externally connected if for every source $ s $ and target $ t $ there exists a plain path from $ s $ to $ t $. A 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 rearrangeable if for every its mask there exists a collection, called routing, of corresponding mutually edge-disjoint plain paths in $ G $.

The graph $ G $ is ordered if each of its parts is linearly ordered. The graph $ G $ is 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 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).

Examples

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 2-stage Shuffle-exchange graph $ \text{SE}(2,3) $, and there are several nice proofs known for $ R(A)=4 $. 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 $.

Figure 1. Examples for Conjecture ($ \diamond $).

Link to Beneš Conjecture

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

The equivalence is based on the natural bijection between the $ \ell $-systems of partitions and the straight $ \ell $-stage graphs, given any $ \ell\ge2 $. Here an $ \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 ($ \star $) and ($ \dag $) via numerous easily seen equivalences. Here is some basic ones:

$ \bullet $ 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] $.

$ \bullet $ 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] $.

$ \bullet $ $ 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 $ 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 $.

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

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

$ \bullet $ Consequently, rearrangeability of $ G({\bf H}) $ is equivalent to completeness of $ {\bf H} $. Here $ {\bf H} $ is complete if it satisfies $ \frak S(E) = S({\bf h}_1)S({\bf h}_2) \dots S({\bf h}_\ell) $.

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

$ \bullet $ 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 completeness 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}) $.

Counterexamples

Although the presented graph-theoretic statement ($ \dag $) of Problem ($ \star $) may look more complex, it provides somewhat more intuitive framework to study the problem and, in particular, Beneš conjecture. 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 here.

Counterexample 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 $:

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.

Counterexample 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 $):

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.

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 $:

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.

Counterexample 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 here (via Problem ($ \star $) and Beneš conjecture).

Related problems

Beneš Conjecture
Shuffle-Exchange Conjecture
Shuffle-Exchange Conjecture (graph-theoretic form)

Bibliography

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


* indicates original appearance(s) of problem.
add new comment