arXiv:1205.5263v4 [cs.DS] 31 Jul 2014  1  Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms  Jingjin Yu, Daniela Rus  Abstract  We study the problem of planning paths for   p   distinguishable pebbles (robots) residing on the vertices of an   n -vertex connected graph with   p   ≤   n . A pebble may move from a vertex to an adjacent one in a time step provided that it does not collide with other pebbles. When   p   =   n , the only collision free moves are synchronous rotations of pebbles on disjoint cycles of the graph. We show that the feasibility of such problems is intrinsically determined by the diameter of a (unique) permutation group induced by the underlying graph. Roughly speaking, the diameter of a group   G   is the minimum length of the generator product required to reach an arbitrary element of   G   from the identity element. Through bounding the diameter of this associated permutation group, which assumes a maximum value of   O ( n 2 ) , we establish a linear time algorithm for deciding the feasibility of such problems and an   O ( n 3 )   algorithm for planning complete paths.  I. I NTRODUCTION  In Sam Loyd’s 15-puzzle Loyd (1959), a player arranges square blocks labeled 1-15, scrambled on a 4   ×   4 board, to achieve a shuffled row major ordering of the blocks using one empty swap cell (see,   e.g. , Fig. 1). Generalizing the grid-based board to an arbitrary connected graph over   n  vertices, the 15-puzzle becomes the problem of   pebble motion on graphs   (PMG). Here, up to   n − 1 uniquely labeled pebbles on the vertices of the graph must be moved to some desired goal config- uration, using unoccupied (empty) vertices as swap spaces. 1   Since the initial work by Kornhauser  Jingjin Yu and Daniela Rus are the Computer Science and Artificial Intelligence Lab at the Massachusetts Institute of Technology. E-mail:   { jingjin, rus } @csail.mit.edu.  1 We use   pebble   in place of   robot   in this paper to keep the notations consistent with Auletta et al. (1999); Kornhauser et al. (1984), on which the current paper is partially based.
2  et al. Kornhauser et al. (1984), PMG and its optimal variants has received significant attention in robotics Solovey and Halperin (2012); van den Berg et al. (2009); Wagner and Choset (2011) and artificial intelligence Krontiris et al. (2013); Standley and Korf (2011), among others. The connection between PMG   and multi-robot path planning is immediately clear, with poten- tial applications towards micro-fluidics Griffith and Akella (2005), multi-robot path planning Solovey and Halperin (2012), and modular robot reconfiguration Reif and Slee (2006), to name a few. As early as 1879, Story Story (1879) observed that the parity of a 15-puzzle instance decides whether it is solvable. Wilson Wilson (1974) formalized this observation by showing that the reachable configurations of a 15-puzzle form an alternating group on 15 letters. An associated planning algorithm was also provided. Kornhauser et al. Kornhauser et al. (1984) improved the potentially exponential time algorithm from Wilson (1974) by giving an algorithm for PMG that runs in   O ( n 3 )   time for graphs with   n   vertices and up to   n   −   1 pebbles. Auletta et al. Auletta et al. (1999) showed that for trees, deciding whether an instance of the pebble motion problem is feasible can be done in linear time. Recently, the linear feasibility result was extended to general graphs for PMG Goraly and Hassin (2010); Yu (2013). Although not a focus of this paper, we note that computing optimal plans for such problems is generally NP-complete Goldreich (1984); Ratner and Warmuth (1990); Surynek (2010); Yu and LaValle (2013).  1 2 15   3 14 12 13 11 10 8 9 7 6 5 4  1   2 15 3 14 12 13 11 10 8  9  7 6 5 4  (a)   (b)  Fig. 1.   Two 15-puzzle instances. a) An unsolved instance. In the next step, one of the blocks 5, 6, 14 may move to the vacant cell, leaving behind it another vacant cell for the next move. b) The solved instance.  As evident from the techniques used in Kornhauser et al. (1984); Wilson (1974), PMG and related problems are closely related to structures of   permutation groups . Fixing a graph and the number of pebbles, and viewing the pebble moving operations as   generators , all configurations reachable from an initial configuration form a group that is isomorphic to a subgroup of   S n , the symmetric group on   n   letters. Deciding whether a problem instance is feasible is then equivalent to deciding whether the final configuration is reachable from the initial configuration
3  via generator products. Another interesting problem in this domain is the study of the   diameter  of such groups, which is the length of the longest minimal generator product required to reach a group element. Driscoll and Furst Driscoll and Furst (1983, 1987) showed that any group represented by generators that are cycles of bounded degree has a diameter of   O ( n 2 )   and such a generator sequence is efficiently computable. For generators of unbounded size, Babai et al. Babai et al. (2004) proved that if one of the generators fixes at least 67% of the domain, then the resulting group has a polynomial diameter. In contrast, groups with super polynomial diameters exist Driscoll and Furst (1983).  1   6  2  5  4  3  7  10  9  8  11  1   6  2   4  3  5   7  9  8  11  10  (a)   (b)  Fig. 2.   Two configurations that can be turned into each other in a single synchronized move.  Somewhat surprisingly, a natural generalization of PMG   allowing rotations of the pebbles without empty swap vertices has not received much attention, possibly due to its difficulty. As an example, in Fig. 2(a), the pebbles labeled 3 ,   4, and 5 are allowed to rotate clockwise along the (only) triangle to achieve the configuration in Fig. 2(b). We call this generalization the problem of   pebble motion with rotations   (PMR), a formal definition of which will follow shortly. Synchronous rotations are important to have in a multi-robot setting for at least two reasons. First, with communication, robots are able to execute synchronous rotational moves easily. Disabling such moves thus wastes robots’ capabilities. Second, allowing rotational moves could allow more problem instances to be solved and could also significantly reduce the length of plans (note that the length of a plan can never be increased by adding more modes of motion). In this paper, we employ a group theoretic approach to derive a linear time algorithm for testing the feasibility of a given PMR instance. The algorithm also implies a cubic time algorithm for computing full plans when a PMR instance is feasible. Thus, we establish that PMR induces similar algorithmic complexity as PMG   does in the sense that planning and feasibility test take   O ( n 3 )   and linear time, respectively. Nevertheless, the algorithms for solving PMG   and PMR have significant differences due to the introduction of synchronous pebble rotations. By delivering these algorithms for PMR, we also bring forth the contribution of providing a now
4  fairly complete landscape over graph-based multi-robot path planning problems. We formally define PMG and PMR problems in Section II. In Section III, we look at the groups generated by cyclic rotations of labeled pebbles, on graphs fully occupied by pebbles. We show that such groups have   O ( n 2 )   diameters. With this intermediate result, we continue to show, in Section IV, that the feasibility test of the PMR problem can be performed in   O ( | V   |   +   | E | )  time, which implies an   O ( n 3 )   algorithm for computing a feasible solution (the set of movements). We conclude the paper in Section V. 2  II. P EBBLE   M OTION   P ROBLEMS  Let   G   = ( V ,   E )   be a connected undirected graph with   | V   |   =   n . Let there be a set   p   ≤   n   pebbles, numbered 1 , . . .,   p , residing on distinct vertices of   G . A   configuration   of these pebbles is a sequence   S   =   〈 s 1 , . . .,   s p 〉 , in which   s i   denotes the vertex occupied by pebble   i . A configuration can also be viewed as a bijective map   S   :   { 1 , . . . ,   p } →   V   ( S )   in which   V   ( S )   denotes the set of occupied vertices by   S . We allow two types of   moves   of pebbles. In a   simple move , a pebble may move to an adjacent empty vertex. In a   rotation , pebbles occupying all vertices of a cycle can rotate simultaneously (clockwise or counterclockwise) such that each pebble moves to the vertex previously occupied by its (clockwise or counterclockwise) neighbor. Two configurations  S   and   S ′   are   connected   if there exists a sequence of moves that takes   S   to   S ′ . Let   S   and   D   be two pebble configurations on a given graph   G , the problem of   pebble motion on graphs   is defined as follows.  Problem 1 (Pebble Motion on Graphs (PMG))   Given   ( G ,   S ,   D ) , find a sequence of simple moves that take S to D.  When   G   is a tree, PMG is also referred to as   pebble motion on trees   (PMT). In this case, an instance is usually written as   I   = ( T ,   S ,   D )   with   T   being a tree. When both simple moves and rotations are allowed, the resulting variant is the problem of   pebble motion with rotations .  Problem 2 (Pebble Motion with Rotation (PMR))   Given   ( G ,   S ,   D ) , find a sequence of simple moves and rotations that takes S to D.  2 Given the limited space, we focus on establishing the theoretical foundations behind the algorithms instead of the algorithms themselves. We believe such coverage offers more insights into the intrinsic structures of PMR problems.
5  If   G   is a tree, then a PMR is simply a PMT. We note that it may be possible to achieve additional efficiency by allowing multiple simple moves and rotations (along disjoint cycles) to take place concurrently. For example, the configuration in Fig. 2(a) can be taken to the configuration in Fig. 2(b) in a single concurrent move. A full discussion of such moves ( i.e. , the optimality perspective) is beyond the scope of this paper. III. G RAPH   I NDUCED   G ROUP AND THE   U PPER   B OUND ON ITS   D IAMETER  A. Groups Generated by Cyclic Pebble Motions and their Diameters  A particularly important case of PMR is when   p   =   n ; we restrict our discussion to this case in this section. When   p   =   n , only synchronous rotations are possible. Given two configurations  S   and   S ′   that are connected, they induce a permutation of the pebbles, which is computable via  σ S , S ′   ( i ) =   S − 1 ( S ′ ( i ))   for each pebble   i ;  σ S , S   is the identity element. Given an initial configuration  S 0 , let   S   denote the set of all configurations reachable from   S 0 . It can be verified, using basic definitions of groups, that the permutations  σ S 0 , S i   over all   S i   ∈   S   form a subgroup of   S n , the symmetric group on   n   letters. Since this group is determined by the graph   G , we denote it   G .  v  1  v  2  v  3  v  4  v  5 v  6 v  7  v  8  v  9   v  10  Fig. 3.   For the graph above, the collection of sets of cycles are   C   =   {{ v 1 v 2 v 3 v 4 v 5 } ,   { v 6 v 7 v 8 v 9 v 10 } ,   { v 1 v 2 v 3 v 4 v 5 ,   v 6 v 7 v 8 v 9 v 10 }} .  Two cycles of   G   are   disjoint   if their vertex sets have empty intersection. When   p   =   n , each synchronous move corresponds to the rotations of pebbles along a set of of disjoint cycles. Let  C   be the collection of all sets of disjoint cycles in   G ; each   C   ∈   C   is a unique set of disjoint cycles of   G . Since the pebbles may rotate clockwise or counterclockwise along a cycle   c i   ∈   C , each set of disjoint cycles   C   can take a configuration to 2 | C |   new configurations with one move. That is, each   C   yields 2 | C |   generators of   G . Let the set of all generators obtained this way be   G   . As an example, the graph in Fig. 3 has two cycles, with   | C   |   =   3 and   | G   |   =   8 (note that   | G   |   =   2 | C   |  does not hold in general). We make the simple observation that these definitions yield a natural bijection between synchronous moves and elements of   G   . As such, when a configuration   S ′  is reachable from a configuration   S , we say that the permutation  σ S , S ′   ∈   G   is   reachable   (from the identity) using products of generators from   G   corresponding to the synchronous moves. We
6  frequently invoke this bijection between synchronous moves and generators without explicitly stating so. Lastly, any element   x   ∈   G   can be expressed as generator product   g 1 g 2   . . .   g k   in which  g 1 , . . . ,   g k   ∈   G   . Let   k x   be the minimum   k   such that   x   =   g 1 g 2   . . .   g k . The diameter of   G ,   diam ( G ) , is defined as the maximum   k x   over all   x   ∈   G .  B. Upper Bound over Group Diameters  The main result to be established in this section is   diam ( G ) =   O ( n 2 ) . To show this,   G   is divided into classes based on its connectivity. When   G   is connected (1-connected) but none of its subgraphs are 2-connected ( i.e. ,   G   has no cycles), it is a tree. In this case, no pebble can move. Another simple case is when   G   is a cycle, the simplest 2-connected graph. Then, it is clear that all elements of   G   are generated by a single rotation.  Lemma 1 (Trees and Cycles)   If G is a tree, then   G   ∼ =   { 1 } , the trivial group. If G is a cycle, then   G   ∼ =   Z / n, the cyclic group of order n.  a 1  a  2  a  `  b c   r  c  1  c  2  Fig. 4.   Two cycles sharing one common vertex. The graph is   separable   at   b .  When   G   is connected but the removal of some vertex from   G   leaves two or more components, it is   separable . An important case here is when   G   is a set of cycles sharing vertices so that no edge of   G   is on more than one cycle. Such graphs form a subset of 2-edge-connected graphs. Fig. 4 gives an example with two cycles. Following convention,   A n   denotes the   alternating group  on   n   letters. For groups,   G 1   ≥   G 2   or   G 2   ≤   G 1   denotes that   G 2   is a subgroup of   G 1 . For two configurations   S   and   S ′   over the same set of pebbles on the same graph, we say that they are  cycle similar   if the following property holds. For any pebble   a , let the sets of cycles (of the underlying graph   G ) occupied by   a   in configurations   S   and   S ′   be   C S   and   C S ′   , respectively. Then  C S   ∩ C S ′   6   =   ∅ . A key result of this section is the following.  Theorem 2 (Cycles, Separable)   If every edge of a separable graph G is on exactly one cycle, then   G   ≥   A n   and diam ( G ) =   O ( n 2 ) .
7  P ROOF . Given configurations   S   and   D , we claim: 1. In   O ( n 2 )   moves,   D   can be taken to some configuration   D ′   such that   S   and   D ′   are cycle similar. As an example, in Fig. 4, assuming the given configuration is   S , this step ensures that in configuration   D ′ , pebbles   a i ’s are all on the left cycle and pebbles   c i ’s are all on the right cycle. The pebble   b   may appear on either one of the two cycles. 2. In   O ( n 2 )   moves from   D ′ , a configuration   D ′′   can be reached such that either   D ′′   =   S   or   D ′′  and   S   differ by a transposition (group action). We require that the transposition is fixed for a fixed   S   and involves two adjacent pebbles of   S . Let   S ′   be the result of letting this transposition act on   S . These claims are proved in lemmas that follow. By these claims, an arbitrary   D   can reach either   S   or   S ′ . Therefore, all configurations (and consequently elements of   S n ) are partitioned into two equivalence classes based on mutual reachability. Since the only subgroup of   S n   of index 2 is   A n , this implies that   G   ≥   A n . When   G   ∼ =   A n , any element of   G   is a product of generators from   G   with a length of   O ( n 2 ) , proving   diam ( G ) =   O ( n 2 ) . If   G   is not isomorphic to   A n , since the only subgroups of   S n  containing   A n   are   A n   and   S n   itself,   G   ∼ =   S n . This implies that   A n   has at most two cosets in   G ; denote the other coset of   A n   as   A n c , which also have a diameter of   O ( n 2 )   (to see this, note that any configuration   D   is reachable from one of   S ,   S ′   in   O ( n 2 )   moves). From the identity, all elements of   A n   are reachable using generator products of length   O ( n 2 ) . Since elements of  A n c   are now reachable from elements of   A n , an element of   A n c   must be reachable from the identity using a generator product of length   O ( n 2 )   as well. Therefore, when   G   ∼ =   S n , all elements of   G   are reachable using generator products of length   O ( n 2 ) , yielding   diam ( G ) =   O ( n 2 ) .     Before moving to the lemmas, we note that when   G   is separable and every edge of   G   is on exactly one cycle, the edges of   G   can be partitioned into equivalence classes based on the cycles they belong to. Because   G   is separable, every cycle must border one or more cycles and at the same time, two cycles can share at most one vertex. Such a graph is also called a   cactus   graph. Moreover, there exists a cycle that only shares one vertex with other cycles. We call such a cycle a   leaf cycle . An example of a leaf cycle is given in Fig. 5. Given a cycle   C ′   on   G , it is of   cycle distance d c   to   C   if a vertex on   C ′   needs to travel through at least   d c   cycles to reach   C . A neighboring cycle of   C   has distance 0 since they share
8  a 2  a 1  v C 1 1 1 0 2 2 -1  Fig. 5.   The dual tree structure in a separable graph   G   with every edge on exactly one cycle. The numbers represent the cycle distances of the cycles to the leaf cycle   C , which in fact is the root of the tree.  a common vertex. Let   C   have a cycle distance of   − 1 by definition. This induces a (dual) tree structure on the cycles when viewing them as vertices joined by edges to neighbors (see,   e.g. , Fig. 5). Computing such a tree takes time   O ( | V   |   +   | E | )   because obtaining maximal 2-connected components takes linear time Tarjan (1972). The first claim in the proof of Theorem 2 can be stated as follows.  Lemma 3 (Initial Arrangement)   Given a separable G with each edge on exactly one cycle and configurations S and D, in O ( n 2 )   moves, a configuration that is cycle similar to S is reachable from D.  P ROOF . Note that a pebble may reside on multiple cycles; this lemma only ensures that each pebble gets moved to one of the cycles it belongs to in   S . First we show that a single pebble can be relocated to a cycle it belongs to in   S   in   O ( n )   rotations, without affecting pebbles that are previously arranged. When   G   is two cycles joined on a common vertex ( e.g. , Fig. 4), without loss of generality, assume that we need to move   a i   from the left cycle to the right cycle. This implies that some pebble   c   j   (and possibly   b ) does not belong to the right cycle in   S . We note that the group   G   in this case has four generators,   g ℓ   =      a 1   a 2   . . .   a ℓ   b b   a 1   . . .   a ℓ − 1   a ℓ      ,   g r   =      c 1   c 2   . . .   c r   b c 2   c 3   . . .   b   c 1      ,   which correspond to clockwise rotations along the left and right cycles, respectively, and their inverses,   g − 1  ℓ   and   g − 1  r   . One can verify that the generator product  g − i  ℓ   g −   j r   g i  ℓ   exchanges   a i   and   c   j   between the two cycles without affecting the cycle membership of other pebbles (see Fig. 6). For the general case in which a pebble needs to go through some
9  a  i  c   j  a  i  c   j  a  i  c   j  Fig. 6.   Illustration of the vertex arrange algorithm for two adjacent cycles.  k   cycles, denoting the generators as   g 1 , . . . ,   g k , it is easy to verify that a product of the form  g − i 1  1   g − i 2  2   . . .   g i k  k   . . .   g i 2  2   g i 1  1   achieves what we need, with   i 1   +   . . .   +   i k   <   n . There may be more than these 2 k   basic generators, but we do not need the other generators for this proof. Therefore, at most 2 n   moves are needed to move one pebble to the desired cycle. To avoid affecting pebbles that are previously arranged, we may simply fix a leaf cycle   C   and start with cycles based on their cycle distance to   C   in decreasing order. At most 2 n 2   moves are required to arrange all   n  pebbles to the desired cycles.     Lemma 4 (Rearrangement)   The pebbles arranged according to Lemma 3 can be rearranged such that the resulting configuration is the same as S or differ from S by a fixed transposition of two neighboring pebbles in S. Rearrangement requires O ( n 2 )   moves.  P ROOF . For a fixed   G , let   C   be a leaf cycle and let   C   border other cycle(s) via vertex   v . In   S , let   a 1   be the pebble occupying counterclockwise neighboring vertex of   v   on the cycle   C , and let   a 2   be the counterclockwise neighbor of   a 1   on   C   (again, see Fig. 5 for an illustration of this setup). The fixed transposition will be   ( a 1   a 2 ) . We rearrange pebbles to match the configuration   S   starting from cycles with higher cycle distances to the leaf cycle   C , using the neighboring cycle with smaller cycle distance (such a cycle is unique). We show that the pebbles on the more distant cycle can always be rearranged to occupy the vertex specified by   S . Moreover, this can be achieved using moves that only affect the ordering of two pebbles on the neighboring cycle. Without loss of generality, we use the two cycle example from Fig. 4 and let the right cycle be the more distant one. The generators  g ℓ ,   g − 1  ℓ   ,   g r , and   g − 1  r   from previous lemma remain the same. To exchange two pebbles on the right cycle, for example   c i ,   c   j , we may use the following generator product  g − 2  ℓ   g − i r   g ℓ g   j − i r   g − 1  ℓ   g −   j + i r   g ℓ g − i r   g ℓ .   (1)
10  It is straightforward to verify that (1) works. To make it clear, Fig. 7 illustrates the application of (1) for exchanging   c 2   and   c 5   using   a 1 ,   a 2 . Every such exchange requires at most 2 n   moves.  a 1  a 1  a  2  c  5  a 1  a  2  c  2  c  5  a 1  a  2  c  2 c  5  a  2  c  2  c  5   a 1  a  2  c  2  c  5  a 1  a  2  c  2  c  5  a 1  a  2  c  2  c  5  a 1  a  2  c  2  c  5  a 1  a  2  c  2  c  5  c  2  Fig. 7.   Illustration of the rearrangement algorithm (from left to right, then top to bottom).  Performing such exchanges iteratively, within 2 n 2   moves, all pebbles except those on the leaf cycle   C   can be rearranged to occupy vertices specified by   S . Reversing the process, we can arrange all pebbles on   C   to occupy vertices specified by   S , using a neighboring cycle   C ′ , affecting the ordering of at most two pebbles on   C ′ . Repeating this process again with   C ′   using  C   as the neighboring cycle and   a 1 ,   a 2   as the swapping pebbles, all pebbles except possibly   a 1 ,   a 2  occupy the vertices specified by   S .     The above two lemmas complete the proof of Theorem 2. At this point, it is easy to see that when   G   is separable with each edge on a single cycle,   G   ∼ =   S n   if and only if   G   contains an even cycle, corresponding to the composition of an odd number of transpositions. Otherwise,  G   ∼ =   A n . We are left with the case in which   G   is 2-connected but not a (single) cycle.  Theorem 5 (2-connected, General)   If G is 2-connected and not a cycle,   G   ∼ =   S n   with diam ( G ) =  O ( n 2 ) .  P ROOF . Our proof again starts by showing that the locations of two pebbles can be exchanged without affecting the locations of other pebbles. Given a 2-connected graph   G   that is not a
11  cycle, it can always be decomposed into a cycle plus one or more   ears   (an ear is a simple path  P   whose two end points lie on some cycle that does not contain other vertices of   P ). Therefore, any two pebbles on   G   must lie on some common cycle with one attached ear. We may then assume that the two pebbles to be exchanged lie somewhere on two adjacent cycles ( i.e. , they are two arbitrary pebbles in Fig. 8). Restricting to such a graph   G ′   of   G , which has three cycles (left, right, and outer), rotations along these cycles will not affect the rest of the pebbles not on  G ′ . We claim that moving within   G ′   is sufficient to exchange any two pebbles on   G ′   and the operation can be done with   O ( n )   moves.  a 1  a  2  a b  1  b  2  b c c  1   c  2  n 1  n 2  n 3  Fig. 8.   A simple 2-connected graph. There are six moves for this configuration: Rotating clockwise or counterclockwise along one of the three cycles.  Let   G ′   have   n 1   +   n 2   +   n 3   vertices, with   n 1   vertices belonging to the left cycle only,   n 3   vertices belonging to the right cycle only and   n 2   vertices shared by the two cycles. Assuming the initial pebble configuration is as illustrated in Fig. 8, we have the following generators,  g ℓ   =      a 1   a 2   . . .   a n 1   b n 2   . . .   b 1  b 1   a 1   . . .   a n 1 − 1   a n 1   . . .   b 2      ,  g r   =      c 1   c 2   . . .   c n 3   b n 2   . . .   b 1  c 2   c 3   . . .   b n 2   b n 2 − 1   . . .   c 1      ,  g o   =      b 1   c 1   . . .   c n 3   b n 2   a n 1   . . .   a 1  c 1   c 2   . . .   b n 2   a n 1   a n 1 − 1   . . .   b 1      ,  which are clockwise rotations along the left, right, and the outer cycles of   G ′ , and their inverses,  g − 1  ℓ   ,   g − 1  r   , and   g − 1  o   . Note that  g r g ℓ g − 1  o   =      b 1   c 1  c 1   b 1      = ( b 1   c 1 ) .   (2) That is, we may exchange (transpose)   b 1   and   c 1   using a generator product of length 3. Using this length 3 product   g r g ℓ g − 1  o   , it is possible to exchange any two pebbles on   G ′   without affecting other
12  pebbles. We elaborate two such cases, all other cases are similar. In a first case we exchange   a i  and   c   j . To do this, we first move   c   j   to   c 1 ’s location, followed by moving   a i   to   b 1 ’s location. We can then switch   a i   and   c   j   using the primitive   g r g ℓ g − 1  o   . Reversing the earlier steps then switches   a i  and   c   j   without affecting any other pebbles. The complete product sequence is   g − i  ℓ   g   j r   g ℓ g − 1  o   g −   j + 1  r   g i  ℓ , which requires   O ( n )   moves or generator actions. Similarly, if we want to switch some   c i ,   c   j   that are not adjacent, we can move them along the outer cycle until one of them belongs to the left cycle and the other to the right cycle. The case of exchanging   a i ,   c   j   then applies, after which we reverse the earlier moves on the outer cycle to obtain the net effect of switching   c i ,   c   j . The number of moves is again   O ( n ) . This implies   G   ∼ =   S n   and   diam ( G ) =   O ( n 2 ) .     Combining Theorems 2 and 5 concludes the case for 2-edge-connected graphs that are not single cycles; the case of general graph then follows. Since we will mention “2-edge-connected component” fairly frequently, we abbreviate it to “TECC” except in theorem statements. Also, we call each component of   G   after deleting all TECCs a   branch .  Proposition 6 ( 2 -edge-connected)   If G is   2 -edge-connected and not a single cycle,   G   ≥   A n  with diam ( G ) =   O ( n 2 ) .  P ROOF . A 2-edge-connected graph   G   can be separated into 2-connected components via splitting at articulating vertices. A (dual) tree structure, similar to that illustrated in Fig. 5, can be built over these components. The two-step algorithm used in the proof of Theorem 2, in combination with Theorem 5, can be applied to show that   G   ≥   A n   and   diam ( G ) =   O ( n 2 ) .     After gathering all cases, we obtain the following main result for this section.  Theorem 7 (General Graph)   Given an arbitrary connected, undirected, simple graph G, diam ( G ) =  O ( n 2 ) .  P ROOF . Pebbles on vertices of   G   that are not on any cycle are always immobile. Deleting those vertices does not change   G . After all such vertices are removed, we are left with the TECCs of   G . Denoting the associated groups of these components   { G i } ,   G   is the direct product of the  G i ’s. Since all   G i ’s have   O ( n 2 )   diameter, so does   G .   
13  IV. L INEAR   T IME   F EASIBILITY   T EST OF   PMR We now describe a linear time algorithm for testing the feasibility for PMR, using a proof strat- egy similar to that from Auletta et al. (1999) on PMT. We first restate a result form Auletta et al. (1999).  Theorem 8 (Theorem 3 in Auletta et al. (1999))   Given an instance   ( T ,   S ,   D )   of PMT, in O ( n )  steps, an instance   ( T ,   S ′ ,   D )   of PMT can be computed such that S ′ , D contain the same set of vertices and   ( T ,   S ,   S ′ )   is feasible.  The following corollary is also obvious.  Corollary 9   Given an instance   ( T ,   S ,   D )   of PMR, let   ( T ,   S ′ ,   D )   be the new instance obtained according to Theorem 8. Then   ( T ,   S ,   D )   is feasible if and only if   ( T ,   S ′ ,   D )   is feasible.  By Theorem 8 and Corollary 9, reconfiguration can be performed on a PMR instance   I   = ( G ,   S ,   D )   to get an equivalent instance   I ′   = ( G ,   S ′ ,   D )   so that   S ′ ,   D   have the same underlying vertex set ( i.e. ,   V   ( S ′ ) =   V   ( D ) ). To do this, find a spanning tree   T   of   G . The   O ( n )   time algorithm guaranteed by Theorem 8 can then compute a desired instance   ( T ,   S ′ ,   D )   with   S ′ ,   D   having the same set of vertices. Since the moves taking   ( T ,   S ,   S ′ )   is feasible,   ( G ,   S ,   S ′ )   is feasible; therefore,  ( G ,   S ,   D )   is feasible if and only if   ( G ,   S ′ ,   D )   is feasible. Given an instance   I   = ( G ,   S ,   D )   in which  S   and   D   have the same underlying set, we call it the   pebble permutation with rotation   problem or PPR. Given a PPR instance, we say that two pebbles are   equivalent   if they can exchange locations with no net effect on the locations of other pebbles. A set of pebbles are equivalent if every pair of pebbles from the set are equivalent. In testing the feasibility of a PPR instance   I   = ( G ,   S ,   D ) , a simple but special case is when   G  is a cycle. In this case,   S   and   D   induce natural cyclic orderings of the pebbles. The following is then clear.  Lemma 10   Let I   = ( G ,   S ,   D )   be an instance of PPR in which G is a cycle. Then I is feasible if and only if s i   =   d ( i + k )   mod p   for some fixed natural number k.  When   G   is not a cycle, the feasibility test is partitioned into four main cases, depending on the number of pebbles,   p , with respect to the number of vertices of   G . It is assumed that   G  contains at least one TECC since otherwise   G   is a tree and the problem is a PMT problem.
14  A. Feasibility test of PPR when p   =   n  When   p   =   n , all vertices are occupied by pebbles. Clearly, if a pebble is on a vertex that does not belong to any cycle ( i.e. , a branch vertex), the pebble cannot move. Therefore,   I   = ( G ,   S ,   D )  is feasible only if for every branch vertex   v   ∈   V   ( G ) ,   S − 1 ( v ) =   D − 1 ( v ) . Furthermore, given any TECC   C   of   G ,   S − 1 ( C ) =   D − 1 ( C )   must also hold, since pebbles cannot move out a TECC. If these conditions hold, the feasibility of   I   is reduced to feasibilities of   { ( C i ,   S | S − 1 ( C i ) ,   D | D − 1 ( C i ) ) } , in which   C i ’s are the TECCs of   G   and   S | S − 1 ( C i )   denotes   S   restricted to the domain   S − 1 ( C i ) ; same applies to   D | D − 1 ( C i ) . More formally,  Proposition 11   Let I   = ( G ,   S ,   D )   be an instance of PPR   with p   =   n. Let   { C i }   be the set of 2-edge-connected components of G. Then I is feasible if and only if the following holds: 1. for all v   ∈   V   ( G \ ( ∪ i C i )) , S − 1 ( v ) =   D − 1 ( v ) , 2. for each C i , S − 1 ( C i ) =   D − 1 ( C i ) , and 3. for each C i , the PPR instance   ( C i ,   S | S − 1 ( C i ) ,   D | D − 1 ( C i ) )   is feasible. Moreover, the feasibility test can be performed in linear time.  P ROOF . Finding TECCs of   G   can be done in   O ( | V   |   +   | E | )   time Tarjan (1972). Checking whether condition 1 holds takes linear time. For checking condition 2, for each   C i , we first gather   S − 1 ( C i )  and for each pebble in   S − 1 ( C i ) , mark the pebble as belonging to   C i . We can then check whether the pebbles in   D − 1 ( C i )   also belong to   C i   in linear time. For condition 3, deciding the feasibility of  ( C i ,   S | S − 1 ( C i ) ,   D | D − 1 ( C i ) )   can be done using the results from Section III. This check can performed as follows. 1. Check whether   C i   is a cycle, which is true if and only if no vertex of   C i   has degree more than two. If this is the case, apply Observation 10 to test the feasibility on   C i ; 2. Check whether   C i   is a cactus with no even cycle. We can verify whether   C i   is a cactus as follows: Using depth first search (DFS), detecting cycles of   C i . If   C i   is a cactus, then it should assume a “tree” structure shown in Fig. 5; the first cycle that is found must be a leaf cycle. Deleting this cycle (without deleting the vertex that joins this cycle to the rest of   C i ) from   C i  yields another cactus. Repeating the process tells us whether   C i   is a cactus. As we are finding the cycles, we can check whether there is an even cycle. If   C i   is indeed a cactus with no even cycle, the possible configurations have two equivalence classes. The subproblem is only infeasible if  S | S − 1 ( C i ) ,   D | D − 1 ( C i )   fall into different equivalence classes, which can be checked by computing the parity of the permutation  σ S , D , restricted to   C i , in linear time; 3. For all other types of   C i , the subproblem is feasible.   
15  B. Feasibility test of PPR when p   =   n   −   1 When   p   =   n   −   1, nearly all PPR   instances, in which   G   are 2-edge-connected graphs, are feasible.  Lemma 12   Let I   = ( G ,   S ,   D )   be an instance of PPR in which G is 2-edge-connected and not a cycle. If p   <   n, then I is feasible.  P ROOF . By Theorems 2 and 5,   G   ≥   A n . That is, there are at most two equivalence classes of configurations, with configurations from different classes differ by a transposition of neighboring pebbles. Since there is at least one empty vertex, viewing that vertex as a “virtual” pebble that can be exchanged with a neighboring pebble in one move, it is then clear that the two configuration classes collapse into a single class.     Lemma 13   Let I   = ( G ,   S ,   D )   be an instance of PPR in which G, after deleting one (or more) degree   1   vertex (vertices), is a 2-edge-connected graph. If p   <   n, then I is feasible.  P ROOF . Note that by degree 1 vertices, we mean that these vertices have degree 1 in   G . Let  H   be the 2-edge-connected graph after deleting all degree 1 vertices and let   v 1 , . . . ,   v k   be the degree 1 vertices. Let the neighbor of   v i   in   G   be   v ′  i   ∈   V   ( H ) . Since   v   ∈   v 1 , . . . ,   v k   has degree 1, it is attached to   H   via a single edge. Let   H i   be the subgraph of   G   after deleting all vertices in  v 1 , . . .,   v k   except   v i . Assume that   v 1   is empty initially, we show next that all pebbles occupying  H 1   are equivalent. That is, an arbitrary configuration of these pebbles can be achieved.  v ¶  v 1 1  Fig. 9.   With one empty vertex, pebbles on a triangle can be arranged to achieve any desired configuration. This generalizes to an arbitrary TECC.  If   H   is cycle, the subroutine illustrated in Fig 9 shows how an arbitrary configuration of pebbles can be achieved for a triangle   H , which directly generalizes to an arbitrary sized cycle.
16  This shows that all pebbles on   H 1   fall in the same equivalence class. If   H   is not a cycle, we can move an arbitrary pebble   j   from   H   to   v 1 . Lemma 12 implies that all pebbles on   H   are equivalent. Since   j   is arbitrary, all pebbles on   H 1   are equivalent. Having shown that all pebbles on   H 1   are equivalent, we move an arbitrary pebble   j   to   v 1  and empty vertex   v 2   (if there is a   v 2 ). Following the same procedure, all pebbles on   H 2   are equivalent. Since   j   is arbitrary, all pebbles on   H ,   v 1 ,   v 2   are equivalent. Inductively, all pebbles on   G   are equivalent. Therefore, an arbitrary instance   I   is feasible.     When there is a single empty vertex on   G , it is clear that pebbles can be moved so that the empty vertex is an arbitrary vertex of   G . In particular, for any TECC   H   of   G , we can move the pebbles so that a vertex of   H   is empty. By Lemma 13, all pebbles on   H   and its distance one neighboring vertices fall in the same equivalence class. We now show that the feasibility of the case of   p   =   n   −   1 can be decided in linear time.  Proposition 14   Let I   = ( G ,   S ,   D )   be an instance of PPR in which p   =   n   −   1   and G is not a cycle. The feasibility of I can be decided in linear time.  P ROOF . We start with pebble configuration   S   and group the pebbles into equivalence classes. Without loss of generality, assume that   S   leaves a vertex of a TECC, say   H , unoccupied. By Lemma 13, all pebbles on   H   and its distance 1 neighbors belong to the same equivalence class, say   h S , 1 . Now, check whether any pebble in   h S , 1   is on some other TECC   H ′   6   =   H . If that is the case, all pebbles on   H ′   and its distance 1 neighbors are also equivalent and belong to   h S , 1 . When no more pebbles can be added to   h S , 1   this way,   h S , 1   is completely defined. Let   v   be a vertex neighboring a vertex occupied by a pebble from   h S , 1   ( v   itself is not occupied by a pebble in   h S , 1 ), if   v   is not a TECC vertex, the pebble currently on   v   cannot be move to a TECC and therefore is not equivalent to any other pebble. The pebble then gets its own equivalence class, say   h S , 2 . If   v   belongs to a TECC, say   H v , then all pebbles on   H v   and all   H v ’s distance 1 neighbors that are not yet classified belong to   h S , 2 ;   h S , 2   is then expanded similarly to   h S , 1 . At this point, the procedures given so far apply to partition all pebbles into equivalence classes. It is not hard to see the algorithm takes linear time to complete using breadth first or depth first search, treating each TECC as a whole. As the start configuration   S   is being classified, the same is done to   D . In particular, if a set of pebbles of   S   belongs to an equivalence class
17  h S , i , then the pebbles of   D   occupying the same set of vertices get assigned to the class   h D , i . The instance   I   is feasible if and only if   h S , i   =   h D , i   for all   i   (this can be done in linear time as we have shown in checking the second condition in Proposition 11).     Fig. 10 provides an example of applying the above procedure to a given pebble configuration,  v 1  v 2  v 3   v 4  v 5  v 6  v 7  v 8  Fig. 10.   An example of the case   p   =   n   −   1. The pebbles are put into 5 different equivalence classes, distinguished by different colors.  which partitions the pebbles into 5 equivalence classes.  C. Feasibility test of PPR when p   <   N ( T ECCs )  We denote by   N ( T ECCs )   the number of vertices of all TECCs of   G . An instance is almost always feasible when   p   <   N ( T ECCs ) .  Theorem 15   Let I   = ( G ,   S ,   D )   be an instance of PPR   in which G is not a cycle. If p   <  N ( T ECCs ) , then I is feasible.  P ROOF . Since the number of pebbles are not enough to occupy all TECC vertices, we can update configuration   S   to a new one   S ′   such that all pebbles are on TECC vertices. Repeating the same moves over the configuration   D   to get   D ′   ( i.e. , if we move a pebble from   v i   to   v   j   in the initial pebble configuration, we move the corresponding pebble from   v i   to   v   j   in the final pebble configuration). After this process is complete, the updated start and final configurations again occupy the same set of vertices;   ( G ,   S ,   D )   is feasible if and only if the   ( G ,   S ′ ,   D ′ )   is feasible. In the rest of the proof we show that   ( G ,   S ′ ,   D ′ )   is feasible.  v j C  i  C  j  v i  Fig. 11.   A graph with two TECCs.
18  Since not all TECC vertices are occupied in   S ′ , at least one TECC, say   C i , has an empty vertex. By Lamma 13, all pebbles on   C i   are equivalent. Now let   C j   be another TECC joined to  C i   via a single branch (see Fig. 11 for an example). Since any pebble on   C j   can be moved to vertex   v   j   via a proper sequence of rotations, it is then possible to exchange any pair of pebbles  p 1   on   C i   and   p 2   on   C j : move   p 2   to   v   j , empty   v i , move   p 2   to   v i , rotate   p 1   to   v i , and move it to   v   j . Via induction, any pair of pebbles on   G   can be exchanged, without affecting the current configuration of other pebbles. Given this procedure, we can iteratively arrange each pebble   i , starting from pebble 1, by exchanging pebble   i   with some other pebble occupying   i ’s vertex in  D ′ . With up to   p   −   1 exchanges, all pebbles can be arranged to their desired final configurations.    D. Feasibility test of PPR when N ( T ECCs )   ≤   p   <   n   −   1 For this last case, given a PPR instance,   ( G ,   S ,   D ) , we first move pebbles in   S   and   D   so that vertices of all TECCs are occupied. To perform this in linear time, a “fake” goal configuration  D   f   is created with   p   pebbles such that all TECCs are full occupied, in an arbitrary order. This is possible because   N ( T ECCs )   ≤   p   <   n   −   1. Using a spanning tree   T   of   G   and apply Theorem 8 to   ( T ,   S ,   D   f   ) ,   ( T ,   D ,   D   f   ) , we get two new instances   ( T ,   S ′ ,   D   f   ) ,   ( T ,   D ′ ,   D   f   )   with the property that   S ′ ,   D ′ , and   D   f   all occupy the same set of vertices and   ( T ,   S ,   S ′ ) ,   ( T ,   D ,   D ′ )   are both feasible. Thus, we obtain a new PPR instance   ( G ,   S ′ ,   D ′ ) , which is feasible if and only if   ( G ,   S ,   D )   is, with the additional property that vertices of all TECCs are occupied. For convenience, we call an instance   ( G ,   S ,   D )   of PPR   in which all TECC vertices are occupied a   rearranged pebble permutation   problem, or RPP. Note that this implies   p   ≥   N ( T ECCs ) .  v 1  v 2  v 3   v 4  v 5  v 6   v 7  v 8   v 1  v 2  v 3   v 4  v 5  v 6   v 7  v 8  Fig. 12.   The skeleton tree (on the right) after contracting the graph on the left (from Fig. 10); the black dots are the composite vertices.  Next, we contract   G   to get a   skeleton tree ,   T G , by collapsing each TECC into a   composite
19  vertex ; other vertices and edges are left intact. For example, the graph from Fig. 10 have the skeleton tree shown in Fig. 12. This procedure induces a natural map   f T   that takes any subgraph  H   of   G   to   f T   ( H )   as a subgraph of   T G   (via mapping all vertices belonging to the same TECC of   G   to a composite vertex of   T G   and non-composite vertices of   G   to non-composite vertices of  T   ). Given an instance   ( G ,   S ,   D )   of RPP with   p   <   n   −   1 pebbles, all pebbles on the same TECC are equivalent by Lemma 13. This induces a problem instance   ( T G ,   S ′ ,   D ′ )   in which all pebbles (in   S   and   D ) on the same TECC of   G   are combined into a   composite   pebble (in   S ′   and   D ′ ). Given two vertices   u   and   v   in a graph,   u   v   denotes a (shortest) path between   u   and   v . Such a path is unique when the graph is a tree. By all vertices on (resp. in)   u   v , we mean vertices of  u   v   including (resp. excluding)   u   and   v . Lemma 6 from Auletta et al. (1999) can be extended to RPP as follows.  Lemma 16   Let   ( G ,   S ,   D )   be an instance of RPP   in which G is not a cycle and N ( T ECCs )  ≤   p   <   n   −   1 . Let u ,   v, and w be vertices of G such that the path between u and v and the path between v and w are not edge disjoint. Assume u and v are occupied by pebbles and moves exist that take S to a new configuration in which pebble S − 1 ( u )   is moved to v and S − 1 ( v )   is moved to w. Then S can be taken to an configuration S ′   in which S and S ′   are the same except pebbles on u and v are exchanged.  P ROOF . For convenience, let   p 1   : =   S − 1 ( u )   and   p 2   : =   S − 1 ( v ) . Let the overlapping part of   u   v  and   v   w   be   y   v . Let the sequence of moves that take   p 1   to   v   and   p 2   to   w   be represented as   X   =   〈 S   =   S 0 ,   S 1 , . . . ,   D 〉 . If it is possible to move   p 1 ,   p 2   to the same TECC, then clearly the locations of   p 1 ,   p 2   can be exchanged on the TECC without changing any other pebble’s configuration. Reversing earlier moves then exchanges   p 1 ,   p 2   on   u   and   v . For the rest of this proof, we assume that   p 1 ,   p 2   can never occupy vertices from the same TECC. Note that this implies hat   p 1 ,   p 2   can never occupy vertices of the same TECC in different configurations originated from   S ; in particular, no vertex on   y   v   can be on a TECC. To see this, if   p 1 ,   p 2  both reach a TECC   H   in some (possibly different) configurations in   X   , assume without loss of generality that   p 1   reaches   H   first. Since all pebbles on   H   are equivalent and   H   contains at least three vertices,   p 1   can always stay on   H : Suppose   X   at some point wants to move   p 1   outside of  H . If   p 1   is the only pebble on   H ,   p 1   does not hinder any other pebbles from moving through  H   and moving   p 1   out will only crowd the rest of   G , making further pebble movements outside
20  H   harder. If   p 1   is not the only pebble on   H , we may pick any pebble on   H   to leave   H   instead of   p 1 . Then   p 2   will eventually reach   H   with   p 1   still on   H , allowing them to exchange. For the case in which   p 1 ,   p 2   never visits the same TECC of   G , let   W   denote the graph formed by the vertices and edges traveled by   p 1 ,   p 2   as they move along the sequence of configurations in   X   . Let   T W   =   f T   ( W   ) . If   T W   contains composite vertices that are not leaves of   T W   , let   z   be such a composite vertex and   H z   be the TECC corresponding to   z   in   G . Let   G ( H z ,   v )   denote the connected component of   G   containing   v   after deleting   H z   and let   G ( H z ,   v )   denote rest of the components. By assumption, only one of   p 1   or   p 2   may visit   H z . Assume it is   p 1   (the case of  p 2   is similar), then   p 2   can only visit vertices of   G ( H z ,   v ) ; in fact the entire path   v   w   is within  G ( H z ,   v ) . Using the same argument from the previous paragraph,   X   can be modified so that   p 1  does not visit vertices of   G ( H z ,   v ) , unless   u   ∈   G ( H z ,   v ) . In this case, however,   p 1   is equivalent to any pebble that is initially on   H z ; the lemma holds if an only if a pebble initially on   H z   in   S  can move to   v   and   p 2   can move to   w . Via induction, it must be possible for some pebbles   p ′  1 , equivalent to   p 1 , and   p 2   to move from some   u ′   to   v   and   v   to some   w ′ , respectively, where   y   v  is contained within   u ′   v   and   v   w ′ . Further more,   p ′  1 ,   p 2   do not “pass through” any TECC of   G . We may then assume that from the beginning,   T W   has only composite vertices that are leaves. Denote the branch of   G   containing   y   as   T y . Since   p 1 ,   p 2   may still visit some TECCs, let   T   ′  y  denote the tree containing   T y   as well as the vertices of these TECCs (visited by   p 1   or   p 2 ) that are (distance 1) neighbors of   T y . Since the labels of pebbles other than   p 1 ,   p 2   have no effect on moving   p 1 ,   p 2 , we may assume pebbles other than   p 1 ,   p 2   are unlabeled (indistinguishable). It can be shown that unlabeled pebbles outside of   T   ′  y   never need to move to   T   ′  y   : If an unlabeled pebble moves from outside   T   ′  y   and stays on   T   ′  y   it only makes moving   p 1 ,   p 2   less feasible; if an unlabeled pebble moves from one vertex outside   T   ′  y   to another vertex outside   T   ′  y   via   T y , it does not help the feasibility of moving   p 1 ,   p 2   on   T   ′  y   . Thus, unlabeled pebbles may only move away from   T   ′  y   and they should never come back. Therefore, we may first take the unlabeled pebbles that will leave  T   ′  y   and move them outside   T   ′  y   in the beginning. After these steps, the initial problem is reduced to moving   p 1   from   u   to   v   and   p 2   from   v   to   w   on the tree   T   ′  y   ; by Lemma 6 from Auletta et al. (1999),   p 1 ,   p 2   are equivalent. Note that this implies that if   p 1   (resp.   p 2 ) can visit a TECC, then  p 2   (resp.   p 1 ) can visit that TECC as well; it is not possible that a given TECC can only be visited by one of the pebbles from   p 1 ,   p 2 .   
21  Lemma 16 leads to a generalized version of Theorem 4 from Auletta et al. (1999) to RPP, given below. We omit the proof since it is nearly identical (we need extended versions of Corollary 1 and 2 from Auletta et al. (1999), which can be easily proved in the same way Lemma 16 is proved).  Theorem 17   An RPP instance,   ( G ,   S ,   D ) , in which G is not a cycle and N ( T ECCs )   ≤   p   <   n   −   1 , is feasible if and only if the individual exchanges between pebble i and S − 1 ( D ( i )) ,   1   ≤   i   ≤   p, can be performed using moves without affecting the configurations of any other pebble.  By Theorem 17, if an instance of RPP,   I   = ( G ,   S ,   D ) , is feasible, then pebbles   i   and  σ S , D ( i ) =  S − 1 ( D ( i ))   can be exchanged with no net effect on other pebbles. This enables a feasibility test of RPP problems (and therefore, PMR problems): vertices occupied by pebbles are partitioned into equivalence classes such that two pebbles can be exchanged if and only if the vertices occupied by them belong to the same equivalence class. In fact, we apply the   Mark   algorithm from Auletta et al. (1999) on the skeleton tree   T G   without any change at the pseudocode level (see Auletta et al. (1999) for the simple algorithm description); the main difference is how to check whether two adjacent pebbles are equivalent (Lemma 8 from Auletta et al. (1999)). Before stating our version of the lemma, some notations are in order. We work with an arbitrary RPP instance   I   = ( G ,   S ,   D )   in which   G   is not a cycle and   N ( T ECCs )   ≤   p   <   n   −   1. Let  I ′   = ( T G ,   S ′ ,   D ′ )   be the induced instance described earlier in which   T G   is   G ’s skeleton tree. A  fork   vertex of   T G   is a vertex of degree at least 3 that is not a composite vertex.   F ( u )   is the set of connected components of   T G   after deleting the vertex   u .   T   ( u ,   v )   is the tree of   F ( u )   containing the vertex   v ;   T   ( u ,   v )   is the rest of   F ( u ) . For two vertices   u ,   v   ∈   V   ( T G ) ,   d ( u ,   v )   is the length of  u   v . In the lemmas that follow, only start configuration   S ′   is operated on; same procedure can be applied to   D . First we need a version of Corollary 3 from Auletta et al. (1999) to account for composite vertices; we omit the essentially same proof but point out that although both fork and composite vertices can help two pebbles switch locations, a composite vertex can do so with one fewer empty vertex.  Lemma 18   Let p 1   : =   S ′− 1 ( u ) , p 2   : =   S ′− 1 ( v )   for u ,   v   ∈   V   ( T G )   such that u   v contains no other pebbles; all vertices on u   v are of degree 2. Let w be a composite or fork vertex such that u is in w   v. The tree T   ( u ,   w )   has no more than d ( w ,   u )   (resp. d ( w ,   u ) +   1 ) empty vertices when
22  w is a composite (resp. fork) vertex. Let w ′   be the closest composite or fork vertex to v such that v is in w ′   u satisfying similar properties as w. Then u and v are not equivalent.  Lemma 19   Let p 1   : =   S ′− 1 ( u ) , p 2   : =   S ′− 1 ( v )   for some u ,   v   ∈   V   ( T G )   such that u   v contains no other pebbles. Then p 1 ,   p 2   are equivalent with respect to S ′   if and only if at least one of the following conditions holds: 1. There exists a fork vertex w in u   v such that both T   ( w ,   u ) ,   T   ( w ,   v )   are not full or at least one other tree of F ( w )   is not full. 2. Let w be a composite vertex such that u is in w   v and no other fork vertex or composite vertex is in w   u. There exists such a w that T   ( u ,   w )   has d ( w ,   u ) +   1   empty vertices. 3. Symmetric to 2 with u and v switched. 4. Let w be a fork vertex such that u is in w   v and no other fork vertex or composite vertex is in w   u. There exists such a w that T   ( u ,   w )   has d ( w ,   u ) +   2   empty vertices. 5. Symmetric to 4 with u and v switched. 6. Vertex u is a fork vertex. Then at least two trees of F ( u )   has empty vertices or there are at least two empty vertices outside T   ( u ,   v ) . 7. Symmetric to 6 with u and v switched. 8. Vertex u is a composite vertex. Then at least one tree of   T   ( u ,   v )   has an empty vertex. 9. Symmetric to 8 with u and v switched.  P ROOF . The proof is adopted from that of Lemma 8 from Auletta et al. (1999) with some repetitive details omitted. Since the sufficiency of the conditions can be easily checked by constructing plans that exchange   p 1 ,   p 2 , only necessity is shown here via contradiction. Assume that   u   and   v   are exchangeable without configuration   S   satisfying any of the conditions 1-9. First consider the case in which there is no fork vertex in   u   v   and   u   and   v   are not fork or composite vertices; these assumptions forbids conditions 1 and 6-9. If conditions 2-5 do not hold, the condition from Lemma 18 is true, thus   u   and   v   cannot be equivalent. For the case in which no fork vertex exists in   u   v   but   u   or   v   (possibly both) is a fork or composite vertex, the proof from Lemma 8 from Auletta et al. (1999) applies with little change to show that   u   and   v   are not equivalent unless one of conditions 2-9 holds: If conditions 2-5 do not hold, this means that   p 1 ,   p 2   must use   u   or   v   as a “hub” for switching locations; traveling beyond distance 1 from   u   v   will not help   u   and   v   to switch. On the other hand, if conditions
23  6-9 do not hold,   u   or   v   cannot serve as the hub that enables   u   and   v   to switch. Furthermore, if conditions 6-9 do not hold, reconfiguration of pebbles will not make conditions 2-5, previously invalid, become valid. This leaves the case in which conditions 2-9 do not hold, which means that   u   and   v   cannot switch on   T   ( u ,   v )   nor   T   ( v ,   u ) . Since there is no pebble in   u   v , the vertices in   u   v   cannot be composite vertices. The same proof from Lemma 8 from Auletta et al. (1999) then shows that unless condition 1 is met,   u   and   v   cannot be equivalent.     With Lemma 19, all criteria needed for the   Mark   algorithm from Auletta et al. (1999), in particular Observations 1-4, continue to hold on   T G   without change. Since   Mark   is not changed, its running time is linear if deciding whether two adjacent pebbles are equivalent can be performed in (amortized) constant time. For this to hold, for an arbitrary tree   T   ( u ,   w ) , we need to know whether   T   ( u ,   w )   has 0, 1, 2 holes and whether the fork or composite vertex of   T   ( u ,   w )  closest to   u   allows   u   and another vertex   v   in   T   ( u ,   w )   to exchange ( i.e. ,   T   ( u ,   w )   should have enough empty vertices). These data can be precomputed in   O ( | V   |   +   | E | )   time using two depth firth traversals over the tree   T G . At this point, it is not hard to see that this linear decision algorithm easily turns into an algorithm that computes a feasible solution to a PPR instance. Our complexity analysis shows that a feasible solution can be computed in   O ( | E | )   if a high level plan is required (computes a corresponding RPP instance, checks feasibility, and outputs the permutation pairs for exchanges) and   O ( n 3 )   if step by step output is required (each exchange can be done in   O ( n 2 )   moves produced by a fixed formula). We summarize the main result of this section with the following theorem.  Theorem 20   The feasibility of PMR problems can be decided in linear time. Moreover, a plan for a feasible instance can be computed in O ( n 3 )   time.  V. C ONCLUSION  In this paper, we proposed the problem of   pebble motion on graphs with rotations   (PMR), a graph-based multi-robot path planning problem. Our formulation takes into account natural, synchronous rotations of pebbles along fully occupied cycles of the underlying graph. The inclusion of this important case, in conjunction with previous studies of the problem that only allow pebbles to move to unoccupied vertices, paints a fairly complete picture of graph-based
24  multi-robot path planning problems. In our systematic analysis of PMR, we show that, even for the fully constrained case in which the number of pebbles equals the number of vertices, deciding the feasibility of a PMR instance can be completed in linear time with respect to the size of the underlying graph. Moreover, computing a full plan for all moving all pebbles requires  O ( n 3 )   time. R EFERENCES  S. Loyd,   Mathematical Puzzles of Sam Loyd .   New York: Dover, 1959. V. Auletta, A. Monti, M. Parente, and P. Persiano, “A linear-time algorithm for the feasbility of pebble motion on trees,”  Algorithmica , vol. 23, pp. 223–245, 1999. D. Kornhauser, G. Miller, and P. Spirakis, “Coordinating pebble motion on graphs, the diameter of permutation groups, and applications,” in   Proceedings of the 25th Annual Symposium on Foundations of Computer Science , 1984, pp. 241–250. K. Solovey and D. Halperin, “ k -color multi-robot motion planning,” in   The Tenth International Workshop on Algorithmic Foundations of Robotics , 2012. J. van den Berg, J. Snoeyink, M. Lin, and D. Manocha, “Centralized path planning for multiple robots: Optimal decoupling into sequential plans,” in   Proceedings Robotics: Science and Systems , 2009. G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in   Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems , 2011, pp. 3260–3267. A. Krontiris, R. Luna, and K. E. Bekris, “From feasibility tests to path planners for multi-agent pathfinding,” in   Symposium on Combinatorial Search , 2013. T. Standley and R. Korf, “Complete algorithms for cooperative pathfinding problems,” in   Twenty-Second International Joint Conference on Artificial Intelligence , 2011, pp. 668–673. E. J. Griffith and S. Akella, “Coordinating multiple droplets in planar array digital microfluidic systems,”   International Journal of Robotics Research , vol. 24, no. 11, pp. 933–949, 2005. J. H. Reif and S. Slee, “Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots,” in   The Seventh International Workshop on Algorithmic Foundations of Robotics , 2006. E. W. Story, “Note on the ‘15’ puzzle,”   American Journal of Mathematics , vol. 2, pp. 399–404, 1879. R. M. Wilson, “Graph puzzles, homotopy, and the alternating group,”   Journal of Combinatorial Theory (B) , vol. 16, pp. 86–96, 1974. G. Goraly and R. Hassin, “Multi-color pebble motion on graph,”   Algorithmica , vol. 58, pp. 610–636, 2010. J. Yu, “A linear time algorithm for the feasibility of pebble motion on graphs,”   arXiv:1301.2342 , 2013. O. Goldreich, “Finding the shortest move-sequence in the graph-generalized 15-puzzle is np-hard,” 1984, laboratory for Computer Science, Massachusetts Institute of Technology, unpublished manuscript. D. Ratner and M. Warmuth, “The   ( n 2   −   1 ) -puzzle and related relocation problems,”   Journal of Symbolic Computation , vol. 10, pp. 111–137, 1990. P. Surynek, “An optimization variant of multi-robot path planning is intractable,” in   The Twenty-Fourth AAAI Conference on Artificial Intelligence , 2010, pp. 1261–1263. J. Yu and S. M. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs,” in   Proceedings AAAI National Conference on Artificial Intelligence , 2013, pp. 1444–1449.
25  J. R. Driscoll and M. L. Furst, “On the diameter of permutation groups,” in   Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing , 1983, pp. 152–160. ——, “Computing short generator sequences,”   Information and Computation , vol. 72, no. 2, pp. 117–132, Feb. 1987. L. Babai, R. Beals, and A. Seress, “On the Diameter of the Symmetric Group: Polynomial Bounds,” in   Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , 2004, pp. 1108–1112. R. E. Tarjan, “Depth-first search and linear graph algorithms,”   SIAM Journal on Computing , vol. 1, no. 2, pp. 140–160, 1972.