# Optimal Algorithms for Sorting Permutations with Brooms
## 1 Introduction  
Sorting permutations with various operations has applications in genetics and computer interconnection networks [1, 2, 3, 4] and is an active field of research.Reversals, transpositions, prefix reversals, prefix transpositions have been extensively studied with respect to upper bounds, lower bounds, exact distances for all permutations in \(S_{n}\) etc. Transposition tree is one such operation which has applications in solving puzzles and robot motion planning [5, 6]. Hypercube architecture was a golden standard in 1980s for computer interconnection networks. Later, [PERSON] and [PERSON] [1] proposed a transposition tree called _star_, and showed that the _Cayley graph_ corresponding to star, called _star graph_ can accommodate \(n!\) nodes and has diameter sub-logarithmic in number of vertices. Star graphs surpass the then topology Hypercube, both in scalability and diameter because the later can accommodate only \(2^{n}\) vertices and has diameter logarithmic in number of vertices. Diameter is an important quality of service parameter deciding the latency of interconnection networks [7, 8]. There is a natural trade-off between diameter and the cardinality of the generator set. That is, a larger generator set decreases the diameter and vice-versa. The diameter of a Cayley graph \(\Gamma\), can be trivially reduced to \(1\) if the degree of each node in \(\Gamma\) is one less than the total number of nodes. However, if the number of symbols, i.e., the label length of a vertex is \(n\), then this would require the degree to be \(n!-1\) and this is infeasible. Thus, a good balance is sought. In this regard, the degree of \(\Gamma\) generated using any transposition tree is a relativelysmall value of \(n-1\) and for some trees the diameter can be small as well. For example, for a star graph the diameter is \(3/2n+O(1)\)[1]. Thus, Cayley networks were established as a better topology than hypercubes for interconnection networks. Cayley networks also possess other desirable features such as vertex symmetry and small diameter [1]. These are detailed in [PERSON] [3], [PERSON] et al. [4], and [PERSON] [8]. In this article we study the problem of sorting permutations under the operation specified by specific transposition trees--_single broom_, _double broom_ and _millipede tree_. A transposition tree \(T=(V,E)\) is a spanning tree over \(n\) vertices \(v_{1},v_{2},\ldots,v_{n}\). \(T\) denotes an operation in which each edge is a generator [1]. A value assigned to a vertex is called _token_ or _marker_. The markers on vertices \(u\) and \(v\) can be swapped only if the pair \((u,v)\in E\). This is equivalent to applying the corresponding generator and is referred to as making a _move_. Since swap is symmetric, the edge \((u,v)\) is undirected. The initial configuration consists of a bijection from \(v_{1},v_{2},\ldots v_{n}\) to \((1,2,\cdots,n-1,n)\); i.e., from the set of vertices to the set of markers over the alphabet \(\{1,2,\cdots,n-1,n\}\). That is, one can view each vertex \(v_{i}\) as an index \(i\) in an array where some marker \(j\) resides. Thus, input consists of a permutation. The vertex \(v_{i}\) is the _home_ for the corresponding marker \(i\) and we seek to home all markers with minimum number of moves. Note that if for all \(i\), \(v_{i}=i\) then the permutation is sorted. Thus, the goal is to sort the initial configuration, i.e., an input permutation, by applying the minimum number of generators (or swaps or moves) of \(T\). In the remainder of the article,'sorting' refers to transforming a given permutation into the identity permutation with a minimum number of moves of \(T\). **Example 1**. : _Let \(T\) be a transposition tree with \(V=\{1,2,3,4,5\}\) and \(E=\{(1,2)(2,3)(3,4)\)\((4,5)\}\). The generators are the permutations \(\{(21345),(13245),(12435),(12354)\}\)._  
The computational complexity of sorting permutations with transposition trees is unknown in general.