On The Diameter of Pancake Graphs

Harigovind V R Pramod P Nair

Abstract

The Pancake graph( $P_{n}$ ) represents the group of all permutations on n elements, namely $S_{n}$ , with respect to the generating set containing all prefix reversals. The diameter of a graph is the maximum of all distances on the graph, where the distance between two vertices is the shortest path between them. In the case of the $P_{n}$ , it is the maximum of the shortest generating sequence of each permutation in $S_{n}$ . Here we propose a method to realise better upper bounds to the diameter of $P_{n}$ that has its focus on Graph Theoretical concepts rather than Algebra.
Keywords:Pancake Graph, Diameter, Prefix Reversals, Path Covering Spanning trees.
Subject Classification:05C12, 05C25, 05C85

Introduction

A Permutation $\pi$ represents a bijection from a set $A$ onto itself. It is written as $\pi=[\pi_{1}\pi_{2}...\pi_{n}]$ where $\pi_{i}$ is the image of the $i^{th}$ element. If the set $A=\{1,2,3,...,n\}$ then the group of all such permutations is called the Symmetric group of degree n ( $S_{n}$ ). The Pancake graph $P_{n}$ represents the graph for the group $S_{n}$ with respect to the generating set of all prefix reversals, $S=\{r_{2},...r_{n}\}$ where:

[\pi_{1}\pi_{2}...\pi_{i-1}\pi_{i}...\pi_{n}]r_{i}=[\pi_{i}\pi_{i-1}...\pi_{2}\pi_{1}...\pi_{n}]

(1)

All permutations in $S_{n}$ can be represented as a product of the elements of the generating set $S$ , Hence $P_{n}$ is a connected graph. Furthermore, the degree of each vertex of $P_{n}$ is equal to the cardinality of S. The absence of the identity permutation in set $S$ excludes the possibility of loops in $P_{n}$ . Hence $P_{n}$ is a simple connected graph which is $(n-1)$ regular. Hence in total we see that $P_{n}$ is a simple connected regular graph. A graph $G$ is said to be vertex transitive if for each pair of vertices in $G$ there exists some automorphism taking one vertex to the other. In case of $P_{n}$ we attain this idea through the automorphism group of $S_{n}$ .

Analyzing the structure of $P_{n}$ shows us that, for each $n$ the graph contains $n$ copies of $P_{n-1}$ . This is the hierarchical property of the structure of $P_{n}$ . The property plays an important role in proving the Hamiltonicity of $P_{n}$ for $n>3$ . The graph $P_{3}$ is isomorphic to the graph $C_{6}$ , which is Hamiltonian. Now using induction on $n$ we can easily show that $P_{n}$ is Hamiltonian[9, 10]. It has also been shown that all cycles of lengths ranging between 6 and $n!$ can be embedded on the graph $P_{n}$ [9, 7]. The above results play a major role in the method that we propose.

When the diameter of $P_{n}$ is considered the greatest hindrance in determining a precise value is the complex cyclic structure that these graphs possess. Hence we construct a method that eliminates these cycles and correspondingly calculates the diameter. The diameter calculation for Cayley graphs is an NP-hard problem[4]. Therefore we try to conceive a better bound for the value of the diameter. The absence of cycles is obtained in trees, and the best set of trees connected to a graph is the spanning trees. So we will analyse the spanning trees of $P_{n}$ and hence conceive a bound for its diameter. But as such, considering every possible spanning tree of the graph is again a headache; hence we need a smaller collection of spanning trees to work on. The following ideas were obtained from this train of thought. The next section contains an overview of existing bounds to the solution. In the following section, we discuss the method proposed and observations made.

Literary Review

The first set of bounds to the solution of the Diameter problem were proposed by William H. Gates and Christos H. Papadimitriou in 1979[5]. Here they defined two new terminologies to determine their bounds. They were as follows:

Given a permutation $\pi$ in $\S_{n}$ , if $\lvert\pi(j)-\pi(j+1)\rvert=1$ we call $(j,j+1)$ to be an adjacency, where $1\leq j\leq n$ . An adjacency is also seen if ${\pi(j),\pi(j+1)}={1,n}$ . A consecutive string of adjacencies in a permutation is called a block.

If for some $1\leq j\leq n$ , neither $(j,j+1)$ nor $(j-1,j)$ are adjacencies then we call $\pi(j)$ to be free.

So as to calculate the upperbound for the solution Gates and Papadimitriou created an algorithm. The algorithm, for each permutation, exploits the structural properties given in the above definitions to determine the number of reversals to reach the identity permutation, $I_{n}$ . They calculated the maximum number of prefix reversals required to reach identity given any permutation $\pi$ in $S_{n}$ and came up with the inequality:

f(n)\leq{5n+5}/3

(2)

where f(n) is the diameter of $P_{n}$ for a given $n$ . To calculate the lower bound they considered a string of length 8 and showed that the lower bound $f(n)$ to be:

{17n}/16\leq f(n)

(3)

whenever 16 divides $n$ .

But they had also quoted that a better set of bounds could be calculated if the length of string was seven. Working upon this, a better set of bounds was calculated by Hal Sudborough and Heydari in 1997[6]:

{15n}/14\leq f(n)

(4)

whenever 14 divides $n$ .

An even better set of bounds were proposed by a team from University of Texas, Dallas and Hal Sudborough in 2009[2]:

f(n)\leq{18n}/11

(5)

The precise values for the diameter of Pancake graphs have been calculated up to $n=19$ . Heydari and Sudborough also computed the diameter of the Pancake graph $P_{n}$ up to $n=13$ . The diameter for $n=14$ , $15$ were calculated in 2005 by Yuusuke Kounoike, Keiichi Kaneka, and Yuji Shinano[8]. In one year, in 2006, the same authors and Shogo Asai determined the diameter for $n=16$ , $17$ [1]. In 2011 the diameter for $n=18$ , $19$ was found by Cibulka[3]. The table of the values for the values of $d=diam(P_{n})$ for $2\leq n\leq 19$ is given below:

n	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
d	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19	20	22

Table 1: The Table of Diameters

Observations

In this section, we will look into the method that we propose. The computational complexity of the method has not been discussed, but the theoretical validity has been shown below the proposed method. As mentioned in the final paragraph of the introduction, we look into the following definition before going into the method.

A path covering collection of trees refers to the collection of trees that contain all paths between a given set of vertices. Now that we have a collection to work upon, how do we construct such a collection? The following result gives the answer:

Proposition 1.

Given a Hamiltonian graph G, A path covering collection of trees is obtained by the action of the automorphism group on a Hamiltonian path in G.

Proof.

The proof of the above result is in two parts:

1.

To show that the action results in a tree of G.
2.

To show that the collection so obtained is path covering.

Let $H$ be the required Hamiltonian path, $L(G)$ be the automorphism group for $G$ .

1.

Let the image of $H$ under some automorphism $f$ be not a tree. Then there exists some vertex $v_{k}$ such that the graph has a cycle with respect to $v_{k}$ . This means there exists vertices $h_{k}$ and $h_{s}$ in $H$ such that:

$f(h_{k})=f(h_{s})=v_{k}$ (6)

But $f$ is an automorphism on $G$ hence a bijection. Thus the above statement contradicts the property of $f$ hence our assumption is wrong. Therefore the collection so formed has only trees in it. The fact that they are spanning is also seen by the fact that the elements of $L(G)$ are bijections.
2.

Consider a path $p$ of length $k$ in $G$ , $(v_{1}v_{2}...v_{k+1})$ . Consider any $k$ length segment of $H$ , $(h_{1}h_{2}...h_{k+1})$ . Choose $f_{1}$ such that $f_{1}(v_{1})=h_{1}$ . Now choose $f_{2}$ such that $f_{2}(f_{1}(v_{1}))=h_{1}$ and $f_{2}(v_{2})=h_{2}$ . Inductively continue until the $(k+1)$ th vertex. Since the operation between $f_{i}$ ’s is composition, all the corresponding functions are in $L(G)$ . Therefore we see that the collection obtained is path covering.

∎

Hence we have constructed the required collection $\mathbb{S}$ . The next question in front of us is the comparison of distances. The distance between two vertices in the spanning tree may not be equal to the distance between two vertices in the graph $G$ . The problem is taken care of by the following properties:

Proposition 2.

$\min\limits_{S_{i}\in\mathbb{S}}d_{S_{i}}(u,v)=d_{G}(u,v)$ where $\mathbb{S}$ is a path covering collection of spanning trees for $G$ .

Proof.

Let us assume that the above result is not true then either

1.

$\min\limits_{S\in\mathbb{S}}d_{S}(u,v)<d_{G}(u,v)$
2.

$\min\limits_{S\in\mathbb{S}}d_{S}(u,v)>d_{G}(u,v)$

In the first case, we see that the result shows that we have a path shorter than the shortest path in $G$ in some tree $S$ , which is impossible as $S$ is a spanning tree of $G$ . In the second case, we see that the result shows that some path $p$ in $G$ is not present in any tree $S\in\mathbb{S}$ which is also impossible as the collection $\mathbb{S}$ is path covering as proven above. Therefore we infer that $\min\limits_{S_{i}\in\mathbb{S}}d_{S_{i}}(u,v)=d_{G}(u,v)$ . ∎

Hence we have a way to compare distance in the tree and distance in the graph. The first result can be applied to any graph while the second can be applied to any simple graph. The next set of results are for $P_{n}$ .

Proposition 3.

There exists a permutation $u$ such that $d_{P_{n}}(u,In)=diam(Pn)$ , where $I_{n}$ corresponds to the identity element of $S_{n}$ .

Proof.

By the definition of diameter we see that for any $n$ there exists vertices $u,v\in P_{n}$ such that $d_{P_{n}}(u,v)=diam(P_{n})$ . By the definition of distance on a graph it is easily seen that its a metric and hence is translation invariant. Therefore

u^{-1}(d(u,v))=diam(P_{n})\implies d(I_{n},u^{-1}v)=diam(P_{n})

(7)

That is $u^{-1}v$ is the required permutation. ∎

Hence we have seen that we do not have to consider all distances on the graph but rather only distances from $I_{n}$ to every other vertex of the graph.Finally we have the last result which gives us a lower bound on the value of $diam(P_{n})$ .

Proposition 4.

$diam(P_{n-1})\leq diam(P_{n}).$

Proof.

Let us assume the above result is not true then as per hierarchy and the result stated before $\exists u\in P_{n-1}(i)$ in $P_{n}$ such that $u$ is at a distance greater than $diam(P_{n})$ from $I_{n}$ . This is contradictory to the definition of diameter. ∎

Using the above results we fabricate a method to compute a bound for the diameter of $P_{n}$ , $n>5$ .

Proposed Method

The following are the steps to the proposed new method:

1.

Construct a set $M=\{u\in S_{n}|d_{P_{n}}(I_{n},u)\geq diam(P_{n-1})\}$ (The construction of $M$ is explained in the next section).
2.

Consider the longest connected segment among the elements of $M$ with respect to the graph $P_{n}$ . Let the segment be $T$ .
3.

Construct a family of trees with vertices in $M$ using the Dijkstra’s algorithm with respect to the graph $P_{n}$ .
4.

Calculate using Proposition 2 the distance between the vertices in $M$ in $P_{n}$ .
5.

Determine the maximum of all distances calculated using the above step. Let that value be $d_{n}$
6.

$diam(P_{n})\leq diam(P_{n-1})+d_{n}$ .

Theoretical Validity of the Method

From the method stated above, we see that the method’s efficiency lies in the precision we can attain during the construction of $M$ . Hence we consider the construction of $M$ first.

Construction of $M$

The following are the steps to the construction of set $M$ :

1.

Divide the value $diam(P_{n-1})$ by 5 and determine the quotient $q$ and remainder $r$ .
2.

Construct the set $F$ of all five sequences of elements in the generating set of $P_{n}$ such that no two consecutive elements are the same.
3.

Now consider every path of the form of some element in $F$ starting from $I_{n}$ in $P_{n}$ . Let the set $B_{1}$ contain all intermediate vertices in the paths from $I_{n}$ and let $C_{1}$ be the collection of end vertices in each case.
4.

Let set $S^{1}=S_{n}\setminus B_{1}\cup C_{1}$ .
5.

Now, with respect to the first vertex in $C_{1}$ repeat step 3. That is, in place of $I_{n}$ , consider the first vertex in $C_{1}$ . Construct sets $B_{21}$ and $C_{21}$ accordingly and create set $S^{21}=S_{n}\setminus B_{21}\cup C_{21}$ .
6.

Repeat the step until all vertices in $C_{1}$ are covered.
7.

Define $S^{2}$ to be the intersection of all $S^{2i^{\prime}s}$ and $S^{1}$ .
8.

So on defines until Sq.
9.

Now consider the vertices in the set $C_{qi^{\prime}s}$ .
10.

Construct the set of all $r$ length sequences of elements of the generating set. Let it be $F_{r}$ .
11.

Now repeat step 3 with the vertices of $C_{qi^{\prime}s}$ and with elements from $F_{r}$ .
12.

The vertices that are left after repeating the above steps on $C_{qi^{\prime}s}$ form the set $M$ .

Now that we know the set of $M$ , let us consider the next part of the method. The basic question that arises is what happens when the rest of the vertices are totally disconnected. Then we claim that the $diam(P_{n})=diam(P_{n-1})$ . If not, then we see that $diam(P_{n})<diam(P_{n-1})$ which has already been proven wrong. Therefore we are left with the possibility that $diam(P_{n})=diam(P_{n-1})$ . If the graph left is not totally disconnected, then we consider the longest connected path in the resulting graph to come up with a better bound. From the results in the last section, we see that steps 3 and 4 are valid. All that is left is to consider the final statement. Now we have shown that there exists a path of length $diam(P_{n-1})+d_{n}$ in the graph. Hence by the fact that the defined distance on the graph is a metric, we see that:

diam(P_{n})\leq diam(P_{n-1})+d_{n}

(8)

Conclusion

To conclude, we see that the method provides us with a bound to the diameter of $P_{n}$ . Calculating the diameter depends on the difference between the lower and upper bounds determined. If the number of integer values between these bounds is comparably small, we can calculate the diameter by considering these integral values.

References

[1] Shogo Asai, Yuusuke Kounoike, Yuji Shinano, and Keiichi Kaneko. Computing the diameter of 17-pancake graph using a pc cluster. In European Conference on Parallel Processing, pages 1114–1124. Springer, 2006.
[2] Bhadrachalam Chitturi, William Fahle, Zhaobing Meng, Linda Morales, Charles O Shields, Ivan Hal Sudborough, and Walter Voit. An (18/11) n upper bound for sorting by prefix reversals. Theoretical Computer Science, 410(36):3372–3390, 2009.
[3] Josef Cibulka. On average and highest number of flips in pancake sorting. Theoretical Computer Science, 412(8-10):822–834, 2011.
[4] Shimon Even and Oded Goldreich. The minimum-length generator sequence problem is np-hard. Journal of Algorithms, 2(3):311–313, 1981.
[5] William H Gates and Christos H Papadimitriou. Bounds for sorting by prefix reversal. Discrete mathematics, 27(1):47–57, 1979.
[6] Mohammad H Heydari and I Hal Sudborough. On the diameter of the pancake network. Journal of Algorithms, 25(1):67–94, 1997.
[7] Arkady Kanevsky and Chao Feng. On the embedding of cycles in pancake graphs. Parallel Computing, 21(6):923–936, 1995.
[8] Yuusuke Kounoike, Keiichi Kaneko, and Yuji Shinano. Computing the diameters of 14-and 15-pancake graphs. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), pages 6–pp. IEEE, 2005.
[9] Jyh-Jian Sheu, JJM Tan, LH Hsu, and MY Lin. On the cycle embedding of pancake graphs. In Proceedings of 1999 National Computer Symposium, pages C414–C419, 1999.
[10] Shmuel Zaks. A new algorithm for generation of permutations. BIT Numerical Mathematics, 24(2):196–204, 1984.

On The Diameter of Pancake Graphs

Abstract

Introduction

Literary Review

Observations

Proposition 1.

Proof.

Proposition 2.

Proof.

Proposition 3.

Proof.

Proposition 4.

Proof.

Proposed Method

Theoretical Validity of the Method

Construction of MM

Conclusion

References

Construction of $M$