Szymanski's conjecture

Routing a permutation of the doubly-directed cube graph

Unsolved problem in mathematics

Can every permutation on the $n$-dimensional doubly directed hypercube graph be routed with edge-disjoint paths?

More unsolved problems in mathematics

In mathematics, Szymanski's conjecture, named after Ted H. Szymanski, states that every permutation on the $n$-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is, if the permutation $\sigma$ matches each vertex $v$ to another vertex $\sigma (v)$, then for each $v$ there exists a path in the hypercube graph from $v$ to $\sigma (v)$ such that no two paths for two different vertices $u$ and $v$ use the same edge in the same direction.

Known results

Through computer experiments it has been verified that the conjecture is true for $n\leq 4$. Although the conjecture remains open for $n\geq 5$, in this case there exist permutations that require the use of paths that are not shortest paths in order to be routed.

Partial results

While the full conjecture remains open, several partial results have been established. Most notably, it has been proven that the hypercube is 2-rearrangeable, meaning that any permutation can be partitioned into two partial permutations, each of which can be routed by edge-disjoint paths. This result has applications in time-sharing approaches and optical networks with multiple wavelengths, where virtual doubling of edges can be achieved without physically adding connections. The 2-rearrangeability result also provides a 2-approximation algorithm for the maximum disjoint paths problem on the hypercube, which has applications in admission control for high-speed networks.

A related result shows that when source and target vertices are separated by at least two levels in the hypercube (in terms of Hamming weight), there exist two edge-disjoint collections of vertex-disjoint paths connecting them. More generally, it has been conjectured that if source and target vertices are separated by $r$ levels, then $r$ such edge-disjoint collections should exist.

2-1 routing requests

The study of 2-1 routing requests (where each vertex can be used at most twice as a source but only once as a target) is important for understanding Szymanski's conjecture. Any counterexample to the conjecture would necessarily produce two non-routable 2-1 routing requests when decomposed using the "cross first strategy". However, the existence of non-routable 2-1 routing requests in a dimension does not immediately provide a counterexample to Szymanski's conjecture for that dimension.

In $H_{3}$, there exist exactly two 2-1 routing requests that cannot be routed and are non-equivalent by automorphism. One of these, denoted $g_{3}$, can be extended to any dimension $n\geq 3$ to produce a non-routable 2-1 routing request $g_{n}$ in $H_{n}$. Computer searches have identified approximately a dozen non-routable 2-1 routing requests in $H_{4}$, though not all can be extended to higher dimensions.

Motivation

The conjecture is closely related to the circuit-switched routing capability of networks, which is used to support simultaneous communications across multiprocessor parallel and telecommunication systems. In circuit-switched routing, a dedicated path is established for each source-destination pair, and data is pipelined through the path. If the hypercube is rearrangeable (meaning Szymanski's conjecture is true), it would guarantee that any permutation routing request can be satisfied with edge-disjoint paths, allowing parallel data transfer between every source-destination pair.

The conjecture also has connections to property testing, particularly in the context of testing monotonicity of Boolean functions over the hypercube domain. Understanding hypercube routing properties has implications for developing efficient algorithms for monotonicity testing and related problems in theoretical computer science.