You are an expert at summarizing long articles. Proceed to summarize the following text: 
recently , the _ reconfiguration problems _ attract the attention from the viewpoint of theoretical computer science . the problem arises when we wish to find a step - by - step transformation between two feasible solutions of a problem such that all intermediate results are also feasible and each step abides by a fixed reconfiguration rule , that is , an adjacency relation defined on feasible solutions of the original problem . the reconfiguration problems have been studied extensively for several well - known problems , including independent set  @xcite , satisfiability  @xcite , set cover , clique , matching  @xcite , vertex - coloring  @xcite , shortest path  @xcite , and so on . the reconfiguration problem can be seen as a natural `` puzzle '' from the viewpoint of recreational mathematics . the _ 15 puzzle _ is one of the most famous classic puzzles , that had the greatest impact on american and european society of any mechanical puzzle the word has ever known in 1880 ( see @xcite for its rich history ) . it is well known that the 15 puzzle has a parity ; for any two placements , we can decide whether two placements are reconfigurable or not by checking the parity . therefore , we can solve the reconfiguration problem in linear time just by checking whether the parity of one placement coincides with the other or not . moreover , we can say that the distance between any two reconfigurable placements is @xmath4 , that is , we can reconfigure from one to the other in @xmath4 sliding pieces when the size of the board is @xmath5 . however , surprisingly , for these two reconfigurable placements , finding a shortest path is np - complete in general @xcite . namely , although we know that it is @xmath4 , finding a shortest one is np - complete . another interesting property of the 15 puzzle is in another case of generalization . in the 15 puzzle , every peace has the same unit size of @xmath6 . we have the other famous classic puzzles that can be seen as a generalization of this viewpoint . that is , when we allow to have rectangles , we have the other classic puzzles , called `` dad puzzle '' and its variants ( see  [ fig : dad ] ) . gardner said that `` these puzzles are very much in want of a theory '' in 1964 @xcite , and hearn and demaine have gave the theory after 40 years @xcite ; they prove that these puzzles are pspace - complete in general using their nondeterministic constraint logic model @xcite . that is , the reconfiguration of the sliding block puzzle is pspace - complete in general decision problem , and linear time solvable if every block is the unit square . however , finding a shortest reconfiguration for the latter easy case is np - complete . in other words , we can characterize these three complexity classes using the model of sliding block puzzle . from the viewpoint of theoretical computer science , one of the most important problems is the 3sat problem . for this 3sat problem , a similar trichotomy for the complexity of finding a shortest sequence has been shown recently ; that is , for the reconfiguration problem of 3sat , finding a shortest sequence between two satisfiable assignments is in p , np - complete , or pspace - complete in certain conditions @xcite . in general , the reconfiguration problems tend to be pspace - complete , and some polynomial time algorithms are shown in restricted cases . in the reconfiguration problems , finding a shortest sequence can be a new trend in theoretical computer science because it has a great potential to characterize the class np from a new viewpoint .    beside the 3sat problem , one of the most important problems in theoretical computer science is the independent set problem . recall that an _ independent set _ of a graph @xmath3 is a vertex - subset of @xmath3 in which no two vertices are adjacent . ( see  [ fig : example ] which depicts five different independent sets in the same graph . ) for this notion , the natural reconfiguration problem is called the sliding token problem introduced by hearn and demaine  @xcite : suppose that we are given two independent sets @xmath0 and @xmath1 of a graph @xmath7 such that @xmath2 , and imagine that a token ( coin ) is placed on each vertex in @xmath0 . then , the sliding token problem is to determine whether there exists a sequence @xmath8 of independent sets of @xmath3 such that    aaa    @xmath9 , @xmath10 , and @xmath11 for all @xmath12 , @xmath13 ; and    for each @xmath12 , @xmath14 , there is an edge @xmath15 in @xmath3 such that @xmath16 and @xmath17 , that is , @xmath18 can be obtained from @xmath19 by sliding exactly one token on a vertex @xmath20 to its adjacent vertex @xmath21 along @xmath22 . figure  [ fig : example ] illustrates a sequence @xmath23 of independent sets which transforms @xmath24 into @xmath25 . hearn and demaine proved that the sliding token problem is pspace - complete for planar graphs .     of independent sets of the same graph , where the vertices in independent sets are depicted by small black circles ( tokens).,scaledwidth=80.0% ]    ( we note that the reconfiguration problem for independent set have some variants . in  @xcite , the reconfiguration problem for independent set is studied under three reconfiguration rules called `` token sliding , '' `` token jumping , '' and `` token addition and removal . '' in this paper , we only consider token sliding model , and see @xcite for the other models . )    for the sliding token problem , some polynomial time algorithms are investigated as follows : linear time algorithms have been shown for cographs ( also known as @xmath26-free graphs ) @xcite and trees @xcite . polynomial time algorithms are shown for bipartite permutation graphs @xcite , and claw - free graphs @xcite . on the other hand , pspace - completeness is also shown for graphs of bounded tree - width @xcite , and planar graphs @xcite .    in this context , we investigate for finding a shortest sequence of the sliding token problem , which is called the shortest sliding token problem . that is , our problem is formalized as follows :    aaa    a graph @xmath27 and two independent sets @xmath28 with @xmath2 .    a _ shortest _ reconfiguration sequence @xmath29 , @xmath30 , @xmath31 , @xmath10 such that @xmath18 can be obtained from @xmath19 by sliding exactly one token on a vertex @xmath20 to its adjacent vertex @xmath21 along @xmath22 for each @xmath12 , @xmath14 . we note that @xmath32 is not necessarily in polynomial of @xmath33 ; this is an issue how we formalize the problem , and if we do not know that @xmath32 is in polynomial or not . if the length @xmath34 is given as a part of input , we may be able to decide whether @xmath35 in polynomial time even if @xmath32 itself is not in polynomial . however , if we have to output the sequence itself , it can not be solved in polynomial time if @xmath32 is not in polynomial .    in this paper , we will show that the shortest sliding token problem is solvable in polynomial time for the following graph classes :    [ [ proper - interval - graphs ] ] proper interval graphs : + + + + + + + + + + + + + + + + + + + + + + +    we first prove that any two independent sets of a proper interval graph can be transformed into each other . in other words , every proper interval graph with two independent sets @xmath0 and @xmath1 is a yes - instance of the problem if @xmath2 . furthermore , we can find the ordering of tokens to be slid in a minimum - length sequence in @xmath36 time ( implicitly ) , even though there exists an infinite family of independent sets on paths ( and hence on proper interval graphs ) for which any sequence requires @xmath37 length .    [ [ trivially - perfect - graphs ] ] trivially perfect graphs : + + + + + + + + + + + + + + + + + + + + + + + + +    we then give an @xmath36-time algorithm for trivially perfect graphs which actually finds a shortest sequence if such a sequence exists . in contrast to proper interval graphs , any shortest sequence is of length @xmath36 for trivially perfect graphs . note that trivially perfect graphs form a subclass of cographs , and hence its polynomial time solvability has been known  @xcite . [ [ caterpillars ] ] caterpillars : + + + + + + + + + + + + +    we finally give an @xmath38-time algorithm for caterpillars for the shortest sliding token problem . to make self - contained , we first show a linear time algorithm for decision problem that asks whether two independent sets can be transformed into each other . ( we note that this problem can be solved in linear time for a tree @xcite . ) for a yes - instance , we next show an algorithm that finds a shortest sequence of token sliding between two independent sets . we here remark that , since the problem is pspace - complete in general , an instance of the sliding token problem may require the exponential number of independent sets to transform . in such a case , tokens should make detours to avoid violating to be independent ( as shown in  [ fig : example ] ) . as we will see , caterpillars certainly require to make detours to transform . therefore , it is remarkable that any yes - instance on a caterpillar requires a sequence of token - slides of polynomial length . this is still open even for a tree . that is , in a tree , we can determine if two independent sets are reconfigurable in linear time due to @xcite , however , we do not know if the length of the sequence is in polynomial . as far as the authors know , this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours of tokens . in this section , we introduce some basic terms and notations . in the sliding token problem , we may assume without loss of generality that graphs are simple and connected . for a graph @xmath27 , we let @xmath39 and @xmath40 .      for two independent sets @xmath41 and @xmath42 of the same cardinality in a graph @xmath27 , if there exists exactly one edge @xmath15 in @xmath3 such that @xmath43 and @xmath44 , then we say that @xmath45 can be obtained from @xmath18 by _ sliding _ a token on the vertex @xmath46 to its adjacent vertex @xmath21 along the edge @xmath15 , and denote it by @xmath47 . we remark that the tokens are unlabeled , while the vertices in a graph are labeled .    a _ reconfiguration sequence _ between two independent sets @xmath48 and @xmath49 of @xmath3 is a sequence @xmath8 of independent sets of @xmath3 such that @xmath50 for @xmath51 . we denote by @xmath52 if there exists a reconfiguration sequence between @xmath48 and @xmath49 . we note that a reconfiguration sequence is _ reversible _ , that is , we have @xmath52 if and only if @xmath53 . thus we say that two independent sets @xmath48 and @xmath49 are _ reconfigurable _ into each other if @xmath52 . the _ length _ of a reconfiguration sequence @xmath54 is defined as the number of independent sets contained in @xmath54 . for example , the length of the reconfiguration sequence in  [ fig : example ] is @xmath55 . the sliding token problem is to determine whether two given independent sets @xmath0 and @xmath1 of a graph @xmath3 are reconfigurable into each other . we may assume without loss of generality that @xmath56 ; otherwise the answer is clearly `` no . '' note that the sliding token problem is a decision problem asking for the existence of a reconfiguration sequence between @xmath0 and @xmath1 , and hence it does not ask an actual reconfiguration sequence . in this paper , we will consider the shortest sliding token problem that computes a shortest reconfiguration sequence between two independent sets . note that the length of a reconfiguration sequence may not be in polynomial of the size of the graph since the sequence may contain detours of tokens . we always denote by @xmath0 and @xmath1 the initial and target independent sets of @xmath3 , respectively , as an instance of the ( shortest ) sliding token problem ; we wish to slide tokens on the vertices in @xmath0 to the vertices in @xmath1 . we sometimes call the vertices in @xmath0 _ blue _ , and the vertices in @xmath1 _ red _ ; each vertex in @xmath57 is blue _ and _ red . we here give another notation of the sliding token problem , which is useful to explain our algorithm . let @xmath58 be an initial independent set of a graph @xmath3 . for the sake of convenience , we label the tokens on the vertices in @xmath0 ; let @xmath59 be the token placed on @xmath60 for each @xmath12 , @xmath61 . let @xmath54 be a reconfiguration sequence between @xmath0 and an independent set @xmath62 of @xmath3 , and hence @xmath63 . then , for each token @xmath59 , @xmath61 , we denote by @xmath64 the vertex in @xmath62 on which the token @xmath59 is placed via the reconfiguration sequence @xmath54 . notice that @xmath65 . let @xmath1 be a target independent set of @xmath3 , which is not necessarily reconfigurable from @xmath0 . then , we call a mapping @xmath66 a _ target - assignment _ between @xmath0 and @xmath1 . the target - assignment @xmath67 is said to be _ proper _ if there exists a reconfiguration sequence @xmath54 such that @xmath68 for all @xmath12 , @xmath61 . note that there is no proper target - assignment between @xmath0 and @xmath1 if @xmath69 . therefore , the sliding token problem can be seen as the problem of determining whether there exists at least one proper target - assignment between @xmath0 and @xmath1 . the _ neighborhood _ of a vertex @xmath21 in a graph @xmath27 is the set of all vertices adjacent to @xmath21 , and we denote it by @xmath70 . let @xmath71 = n(v)\cup\{v\}$ ] . for any graph @xmath27 , two vertices @xmath72 and @xmath21 are called _ strong twins _ if @xmath73=n[v]$ ] , and _ weak twins _ if @xmath74 . in our problem , strong twins have no meaning : when @xmath72 and @xmath21 are strong twins , only one of them can be used by a token . therefore , in this paper , we only consider the graphs without strong twins . that is , for any pair of vertices @xmath72 and @xmath21 , we have @xmath73\neq n[v]$ ] . ( we have to take care about weak twins ; see section [ sec : caterpillars ] for the details . )    a graph @xmath7 with @xmath75 is an _ interval graph _ if there exists a set @xmath76 of ( closed ) intervals @xmath77 such that @xmath78 if and only if @xmath79 for each @xmath12 and @xmath80 with @xmath81 . denotes an `` independent set , '' an italic @xmath82 denotes an `` interval , '' and calligraphy @xmath76 denotes `` a set of intervals . '' ] we call the set @xmath76 of intervals an _ interval representation _ of the graph , and sometimes identify a vertex @xmath83 with its corresponding interval @xmath84 . we denote by @xmath85 and @xmath86 the left and right endpoints of an interval @xmath87 , respectively . that is , we always have @xmath88 for any interval @xmath89 $ ] .    to specify the bottleneck of the running time of our algorithms , we suppose that an interval graph @xmath27 is given as an input by its interval representation using @xmath36 space . ( if necessary , an interval representation of @xmath3 can be found in @xmath90 time  @xcite . ) more precisely , @xmath3 is given by a string of length @xmath91 over alphabets @xmath92 . for example , a complete graph @xmath93 with three vertices can be given by an interval representation @xmath94 , and a path of length two is given by an interval representation @xmath95 . an interval graph is _ proper _ if it has an interval representation such that no interval properly contains another . the class of proper interval graphs is also known as the class of unit interval graphs  @xcite : an interval graph is _ unit _ if it has an interval representation such that every interval has unit length . hereafter , we assume that each proper interval graph is given in the interval representation of intervals of unit length . in the context of the interval representation , an interval graph is proper if and only if @xmath96 if and only if @xmath97 . an interval graph is _ trivially perfect _ if it has an interval representation such that the relationship between any two intervals is either disjoint or inclusion . that is , for any two intervals @xmath98 and @xmath99 with @xmath96 , we have either @xmath100 or @xmath101 .    a _ caterpillar _ @xmath27 is a tree ( i.e. , a connected acyclic graph ) that consists of two subsets @xmath102 and @xmath103 of @xmath104 as follows . the vertex set @xmath102 induces a path @xmath105 in @xmath3 , and each vertex @xmath21 in @xmath103 has degree 1 , and its unique neighbor is in @xmath102 . we call the path @xmath105 _ spine _ , and each vertex in @xmath103 _ leaf_. in this paper , without loss of generality , we assume that @xmath106 , @xmath107 , and @xmath108 . that is , the endpoints @xmath109 and @xmath110 of the spine @xmath105 should have at least one leaf . it is easy to see that the class of caterpillars is a proper subset of the class of interval graphs , and these three subclasses are incomparable with each other . we show the main theorem in this section for proper interval graphs , which first says that the answer of sliding token is always `` yes '' for connected proper interval graphs . we give a constructive proof of the claim , and it certainly finds a shortest sequence in linear time . [ th : proper ] for a connected proper interval graph @xmath27 , any two independent sets @xmath111 and @xmath112 with @xmath56 are reconfigurable into each other , that is , @xmath113 . moreover , the shortest reconfiguration sequence can be found in polynomial time .    we give a constructive proof for theorem  [ th : proper ] , that is , we give an algorithm which actually finds a shortest reconfiguration sequence between any two independent sets @xmath0 and @xmath1 of a connected proper interval graph @xmath3 .    a connected proper interval graph @xmath27 has a unique interval representation ( up to reversal ) , and we can assume that each interval is of unit length in the representation @xcite . therefore , by renumbering the vertices , we can fix an interval representation @xmath114 of @xmath3 so that @xmath115 ( and @xmath116 ) for each @xmath12 , @xmath117 , and each interval @xmath84 corresponds to the vertex @xmath83 . let @xmath118 and @xmath119 be any given initial and target independent sets of @xmath3 , respectively . without loss of generality , we assume that the blue vertices @xmath120 are labeled from left to right ( according to the interval representation @xmath76 of @xmath3 ) , that is , @xmath121 if @xmath122 ; similarly , we assume that the red vertices @xmath123 are labeled from left to right . then , we define a target - assignment @xmath66 , as follows : for each blue vertex @xmath124 @xmath125 to prove theorem  [ th : proper ] , it suffices to show that @xmath67 is proper , and each token takes no detours .      by traversing the interval representation @xmath76 of a connected proper interval graph @xmath3 from left to right , we can obtain a string @xmath126 which is a superstring of both @xmath127 and @xmath128 , that is , each letter @xmath129 in @xmath102 is one of the vertices in @xmath130 and @xmath129 appears in @xmath102 before @xmath131 if @xmath132 . we may assume without loss of generality that @xmath133 since the reconfiguration rule is symmetric in sliding token . if a vertex is contained in both @xmath0 and @xmath1 , as @xmath60 and @xmath134 , then we assume that it appears as @xmath135 in @xmath102 , that is , the blue vertex @xmath60 appears in @xmath102 before the red vertex @xmath134 . then , for each @xmath12 , @xmath136 , we define the _ height @xmath137 at @xmath12 _ by the number of blue vertices appeared in the substring @xmath138 minus the number of red vertices appeared in @xmath138 . for the sake of notational convenience , we define @xmath139 . then @xmath137 can be recursively computed as follows : @xmath140 note that @xmath141 for any string @xmath102 since @xmath56 .    using the notion of height , we split the string @xmath102 into substrings @xmath142 at every point of height @xmath143 , that is , in each substring @xmath144 , we have @xmath145 and @xmath146 for all @xmath12 , @xmath147 . for example , a string @xmath148 can be split into four substrings @xmath149 , @xmath150 , @xmath151 and @xmath152 . then , the substrings @xmath142 form a partition of @xmath102 , and each substring @xmath153 contains the same number of blue and red tokens . we call such a partition the _ partition of @xmath102 at height @xmath143_.    [ lem : balance ] let @xmath144 be a substring in the partition of the string @xmath102 at height @xmath143 . then ,    aaa    the blue vertices @xmath154 appear in @xmath153 , and their corresponding red vertices @xmath155 appear in @xmath153 ;    if @xmath153 starts with the blue vertex @xmath156 , then each blue vertex @xmath60 , @xmath157 , appears in @xmath153 before its corresponding red vertex @xmath158 ; and    if @xmath153 starts with the red vertex @xmath159 , then each blue vertex @xmath60 , @xmath157 , appears in @xmath153 after its corresponding red vertex @xmath158 .    by the definitions , the claim ( a ) clearly holds . we thus show that the claim ( b ) holds . ( the proof for the claim ( c ) is symmetric . ) since @xmath160 and @xmath153 starts with a blue vertex , we have @xmath161 . we now suppose for a contradiction that there exists a blue vertex @xmath162 which appears in @xmath153 after its corresponding red vertex @xmath163 . then , @xmath164 . we assume that @xmath165 is the minimum index among such blue vertices in @xmath153 . then , in the substring @xmath166 of @xmath102 , there are exactly @xmath167 red vertices . on the other hand , since @xmath164 , the substring @xmath166 contains at most @xmath168 blue vertices . therefore , by the definition of height , we have @xmath169 . since @xmath161 and @xmath169 , by eq . ( [ eq : height ] ) there must exist an index @xmath170 such that @xmath171 and @xmath172 . this contradicts the fact that @xmath153 is a substring in the partition of @xmath102 at height @xmath143 . recall that we have fixed the unique interval representation @xmath114 of a connected proper interval graph @xmath3 so that @xmath115 for each @xmath12 , @xmath117 , and each interval @xmath84 corresponds to the vertex @xmath83 . since all intervals in @xmath76 have unit length , the following proposition clearly holds . [ prop : optimalway ] for two vertices @xmath173 and @xmath174 in @xmath3 such that @xmath122 , there is a path @xmath175 in @xmath3 which passes through only intervals ( vertices ) contained in @xmath176 $ ] . furthermore , if @xmath177 for some index @xmath167 with @xmath178 , no vertex in @xmath179 is adjacent to any vertex in @xmath175 . if @xmath180 for some index @xmath181 with @xmath182 , no vertex in @xmath183 is adjacent to any vertex in @xmath175 . let @xmath102 be the string of length @xmath184 obtained from two given independent sets @xmath0 and @xmath1 of a connected proper interval graph @xmath3 , where @xmath185 . let @xmath142 be the partition of @xmath102 at height @xmath143 . the following lemma shows that the tokens in each substring @xmath153 can always reach their corresponding red vertices . ( note that we sometimes denote simply by @xmath153 the set of all vertices appeared in the substring @xmath153 , @xmath186 . ) [ lem : proper - simple ] let @xmath144 be a substring in the partition of @xmath102 at height @xmath143 . then , there exists a reconfiguration sequence between @xmath187 and @xmath188 such that tokens are slid along edges only in the subgraph of @xmath3 induced by the vertices contained in @xmath189 $ ] . we first consider the case where @xmath153 starts with the blue vertex @xmath156 , that is , @xmath190 . then , by lemma  [ lem : balance](b ) each blue vertex @xmath60 , @xmath157 , appears in @xmath153 before the corresponding red vertex @xmath158 . therefore , we know that @xmath191 , and hence it is red . suppose that @xmath192 , then all vertices appeared in @xmath193 are red . roughly speaking , we slide the tokens @xmath194 from left to right in this order . we first claim that the token @xmath195 can be slid from @xmath196 @xmath197 to @xmath198 @xmath199 . by proposition  [ prop : optimalway ] there is a path @xmath175 between @xmath196 and @xmath198 which passes through only intervals contained in @xmath200 $ ] . since @xmath0 is an independent set of @xmath3 , the vertex @xmath196 is not adjacent to any other vertices @xmath201 in @xmath187 . since @xmath202 , by proposition  [ prop : optimalway ] all vertices in @xmath175 are not adjacent to any of tokens @xmath203 that are now placed on @xmath201 , respectively . therefore , we can slide the token @xmath195 from @xmath196 to @xmath198 . we fix the token @xmath195 on @xmath204 , and will not slide it anymore . we then slide the next token @xmath205 on @xmath206 to @xmath207 along a path @xmath208 which passes through only intervals contained in @xmath209 $ ] . since @xmath1 is an independent set of @xmath3 , the corresponding red vertex @xmath207 is not adjacent to @xmath198 on which the token @xmath195 is now placed . recall that @xmath210 , and hence by proposition  [ prop : optimalway ] , @xmath198 is not adjacent to any vertex in @xmath208 . similarly as above , the tokens @xmath211 are not adjacent to any vertex in @xmath208 . therefore , we can slide the token @xmath205 from @xmath206 to @xmath207 . repeat this process until the token @xmath212 on @xmath156 is slid to @xmath159 . in this way , there is a reconfiguration sequence between @xmath187 and @xmath188 such that tokens are slid along edges only in the subgraph of @xmath3 induced by the vertices contained in @xmath213 $ ] . the symmetric arguments prove the case where @xmath153 starts with the red vertex @xmath159 . note that , in this case , we slide the tokens @xmath214 from right to left in this order . * proof of theorem  [ th : proper ] . * we now give an algorithm which slides all tokens on the vertices in @xmath111 to the vertices in @xmath1 . recall that @xmath142 are the substrings in the partition of @xmath102 at height @xmath143 . intuitively , the algorithm repeatedly picks up one substring @xmath153 , and slides all tokens in @xmath187 to @xmath188 . by lemma [ lem : proper - simple ] it works locally in each substring @xmath153 , but it should be noted that a token in @xmath153 may be adjacent to another token in @xmath215 or @xmath216 at the boundary of the substrings . to avoid this , we define a partial order over the substrings @xmath142 , as follows . consider any two consecutive substrings @xmath153 and @xmath216 , and let @xmath217 . then , the first letter of @xmath216 is @xmath218 . we first consider the case where both @xmath219 and @xmath218 are the same color . then , since @xmath219 and @xmath218 are both in the same independent set of @xmath3 , they are not adjacent . therefore , by proposition  [ prop : optimalway ] and lemma  [ lem : proper - simple ] , we can deal with @xmath153 and @xmath216 independently . in this case , we thus do not define the ordering between @xmath153 and @xmath216 . we then consider the case where @xmath219 and @xmath218 have different colors ; in this case , we have to define their ordering . suppose that @xmath219 is blue and @xmath218 is red ; then we have @xmath220 and @xmath221 . by lemma  [ lem : proper - simple ] the token @xmath195 on @xmath219 is slid to left , and the token @xmath222 will reach @xmath223 from right . therefore , the algorithm has to deal with @xmath153 before @xmath216 . note that , after sliding all tokens @xmath214 in @xmath153 , they are on the red vertices @xmath224 , respectively , and hence the tokens in @xmath216 are not adjacent to any of them . by the symmetric argument , if @xmath219 is red and @xmath218 is blue , @xmath216 should be dealt with before @xmath153 . notice that such an ordering is defined only for two consecutive substrings @xmath153 and @xmath216 , @xmath225 . therefore , the partial order over the substrings @xmath142 is acyclic , and hence there exists a total order which is consistent with the partial order defined above . the algorithm certainly slides all tokens from @xmath0 to @xmath1 according to the total order . therefore , the target - assignment @xmath67 defined in eq . ( [ eq : map_proper ] ) is proper , and hence @xmath113 . therefore , there always exists a reconfiguration sequence between two independent sets @xmath0 and @xmath1 of a connected proper interval graph @xmath3 . we now discuss the length of reconfiguration sequences between @xmath0 and @xmath1 , together with the running time of our algorithm . [ prop : proper ] for two given independent sets @xmath0 and @xmath1 of a connected proper interval graph @xmath3 with @xmath226 vertices ,    aaa    the ordering of tokens to be slid in a shortest reconfiguration sequence between them can be computed in @xmath36 time and @xmath36 space ; and    a shortest reconfiguration sequence between them can be output in @xmath38 time and @xmath36 space . we first modify our algorithm so that it finds a shortest reconfiguration sequence between @xmath0 and @xmath1 . to do that , it suffices to slide each token @xmath59 , @xmath61 , from the blue vertex @xmath60 to its corresponding red vertex @xmath158 along the shortest path between @xmath60 and @xmath134 . we may assume without loss of generality that @xmath227 , that is , the token @xmath59 will be slid from left to right . then , for the interval @xmath60 , we choose an interval @xmath228 such that @xmath229 and @xmath230 is the maximum among all @xmath231 . if @xmath232 , we can slide @xmath59 from @xmath60 to @xmath158 directly ; otherwise we slide @xmath59 to the vertex @xmath99 , and repeat . we then prove the claim ( 1 ) . if we simply want to compute the ordering of tokens to be slid in a shortest reconfiguration sequence , it suffices to compute the partial order over the substrings @xmath142 in the partition of the string @xmath102 at height @xmath143 . it is not difficult to implement our algorithm in section  [ subsec : algo_proper ] to run in @xmath36 time and @xmath36 space . therefore , the claim ( 1 ) holds . we finally prove the claim ( 2 ) . remember that each token @xmath59 , @xmath61 , is slid along the shortest path from @xmath60 to @xmath158 . furthermore , once the token @xmath59 reaches @xmath158 , it is not slid anymore . therefore , the length of a shortest reconfiguration sequence between @xmath111 and @xmath112 is given by the sum of all lengths of the shortest paths between @xmath60 and @xmath158 . it is clear that this sum is @xmath233 . we output only the shortest paths between @xmath60 and @xmath158 , together with the ordering of the tokens to be slid . therefore , the claim ( 2 ) holds . this proposition also completes the proof of theorem  [ th : proper ] . it is remarkable that there exists an infinite family of instances for which any reconfiguration sequence requires @xmath37 length . to show this , we give an instance such that each shortest path between @xmath60 and @xmath158 is @xmath234 . simple example is : @xmath3 is a path @xmath235 of length @xmath236 for any positive integer @xmath34 , @xmath237 , and @xmath238 . in this instance , each token @xmath59 must be slid @xmath234 times , and hence it requires @xmath239 time to output all of them . we note that a path is not only a proper interval graph , but also a caterpillar . thus this simple example also works as a caterpillar . the main result of this section is the following theorem .    [ th : trivialperfect ] the sliding token problem for a trivially perfect graph @xmath7 can be solved in @xmath36 time and @xmath36 space . furthermore , one can find a shortest reconfiguration sequence between two given independent sets @xmath0 and @xmath1 in @xmath36 time and @xmath36 space if there exists .    in this section , we explicitly give such an algorithm as a proof of theorem  [ th : trivialperfect ] . note that there are no - instances for trivially perfect graphs . however , for trivially perfect graphs , we construct a proper target - assignment between @xmath0 and @xmath1 efficiently if it exists .      the @xmath240-tree of an interval graph @xmath3 is a kind of decomposition tree , developed by korte and mhring @xcite , which represents the set of all feasible interval representations of @xmath3 . for an interval graph @xmath3 , although there are exponentially many interval representations for @xmath3 , its corresponding @xmath240-tree is unique up to isomorphism . for the notion of @xmath240-trees , the following theorem is known :    [ th : mpq ] for any interval graph @xmath27 , its corresponding @xmath240-tree can be constructed in @xmath90 time . since it is involved to define @xmath240-tree for general interval graphs , we here give a simplified definition of @xmath240-tree only for the class of trivially perfect graphs . ( see @xcite for the detailed definition of the @xmath240-tree for a general interval graph . ) let @xmath27 be a trivially perfect graph . recall that a trivially perfect graph has an interval representation such that the relationship between any two intervals is either disjoint or inclusion . then , the _ @xmath240-tree _ @xmath241 of @xmath3 is a rooted tree such that each node , called a _ @xmath242-node _ , in @xmath241 is associated with a non - empty set of vertices in @xmath3 such that ( a ) each vertex @xmath243 appears in exactly one @xmath242-node in @xmath241 , and ( b ) if a vertex @xmath83 is in an ancestor node of another node that contains @xmath244 , then @xmath245 in any interval representation of @xmath3 , where @xmath173 and @xmath174 correspond to the intervals @xmath98 and @xmath99 , respectively ( see  [ fig : mpq ] as an example ) . by the property ( b ) , the ancestor / descendant relationship on @xmath241 corresponds to the inclusion relationship in the interval representation of @xmath3 . thus , @xmath246\subseteq n[v_i]$ ] if @xmath173 is in an ancestor node of another node that contains @xmath174 in the @xmath240-tree . let @xmath241 be the ( unique ) @xmath240-tree of a connected trivially perfect graph @xmath7 . for two vertices @xmath72 and @xmath247 in @xmath3 , we denote by @xmath248 the least common ancestor in @xmath241 for the nodes containing @xmath72 and @xmath247 . by the property ( a ) the node @xmath248 can be uniquely defined . -tree.,scaledwidth=60.0% ]      let @xmath241 be the ( unique ) @xmath240-tree of a connected trivially perfect graph @xmath7 . recall that the interval representation of a trivially perfect graph has just disjoint or inclusion relationship . this fact implies the following observation . [ obs : twosteps ] every pair of vertices @xmath72 and @xmath247 in a connected trivially perfect graph @xmath3 has a path of length at most two via a vertex in @xmath248 . we first observe that every @xmath242-node of @xmath241 is non - empty . if the root is empty , the graph is disconnected , which is a contradiction . if some non - root @xmath242-node @xmath175 is empty , joining all children of @xmath175 to the parent of @xmath175 , we obtain a simpler @xmath240-tree than @xmath241 , which contradicts the construction of the unique @xmath240-tree in @xcite . thus every @xmath242-node is non - empty . therefore , there is at least one vertex @xmath21 in @xmath248 . then , the property ( b ) implies that @xmath73\subseteq n[v]$ ] and @xmath249\subseteq n[v]$ ] , and hence @xmath15 and @xmath250 are both in @xmath251 . therefore , there is a path @xmath252 of length at most two between @xmath72 and @xmath247 via @xmath21 . when we have @xmath253 or @xmath254 , the path degenerates to the edge @xmath255 . let @xmath256 be the set of vertices in @xmath104 appearing in the @xmath242-nodes on the ( unique ) path from @xmath248 to the root of the @xmath240-tree . by the definition of @xmath240-tree , we clearly have the following observation . ( recall also that each token must be slid along an edge of @xmath3 . ) [ obs : lca_onetoken ] consider an arbitrary reconfiguration sequence @xmath54 which slides a token @xmath59 from @xmath124 to some vertex @xmath158 . then , @xmath59 must pass through at least one vertex in @xmath257 , that is , there exists at least one independent set @xmath258 in @xmath54 such that @xmath259 . we are now ready to give the key lemma for trivially perfect graphs . [ lem : lca ] let @xmath66 be a target - assignment between @xmath0 and @xmath1 . then , @xmath67 is proper if and only if the nodes @xmath260 and @xmath261 are not in the ancestor / descendant relationship on @xmath241 for every pair of vertices @xmath262 . we first show the sufficiency . for a target - assignment @xmath67 between @xmath0 and @xmath1 , suppose that the nodes @xmath260 and @xmath261 are not in the ancestor / descendant relationship on @xmath241 for every pair of vertices @xmath262 . then , we can simply slide the tokens one by one in an arbitrary order ; by observation  [ obs : twosteps ] each token @xmath59 , @xmath61 , can be slid along a path from @xmath60 to @xmath263 via a vertex @xmath264 in @xmath260 . note that there is no token @xmath265 adjacent to @xmath264 , because the nodes @xmath260 and @xmath261 are not in the ancestor / descendant relationship on @xmath241 . thus , there is a reconfiguration sequence between @xmath0 and @xmath1 according to @xmath67 , and hence @xmath67 is proper . we then show the necessity . suppose that @xmath67 is proper , and suppose for a contradiction that there exists a pair of vertices @xmath262 such that the nodes @xmath260 and @xmath261 are in the ancestor / descendant relationship on @xmath241 ; without loss of generality , we assume that @xmath260 is an ancestor of @xmath261 . since @xmath67 is proper , there exists a reconfiguration sequence @xmath54 between @xmath0 and @xmath1 which slides the token @xmath59 from @xmath60 to @xmath263 and also slides the token @xmath265 from @xmath266 to @xmath267 . by observation  [ obs : lca_onetoken ] there is at least one vertex @xmath264 in @xmath268 which is passed through by @xmath59 . similarly , there is at least one vertex @xmath269 in @xmath270 which is passed through by @xmath265 . let @xmath271 and @xmath272 be the @xmath242-nodes that contains @xmath264 and @xmath269 , respectively . since @xmath260 and @xmath261 are in the ancestor / descendant relationship on @xmath241 , so are @xmath271 and @xmath272 . first suppose @xmath272 is an ancestor of @xmath271 . then we have @xmath273 \subseteq n[v_{i'}]$ ] , @xmath274\subseteq n[v_{i'}]$ ] and @xmath275\subseteq n[v_{i'}]$ ] . therefore , if we slide @xmath59 via @xmath264 , then @xmath59 would be adjacent to the other token @xmath265 which is on one of the three vertices @xmath276 , @xmath267 and @xmath269 . thus , the token @xmath265 should `` escape '' from @xmath266 before sliding @xmath59 . however , we can establish the same argument for any descendant of @xmath271 , and hence @xmath265 must escape to some vertex @xmath72 that is contained in an ancestor of @xmath271 at first . however , the vertex @xmath72 is adjacent to all of @xmath277 , and hence @xmath265 can not escape before sliding @xmath59 . this contradicts the assumption that @xmath54 slides the token @xmath59 from @xmath60 to @xmath263 and also slides the token @xmath265 from @xmath266 to @xmath267 . the other case , @xmath271 is an ancestor of @xmath271 , is symmetric . we now describe our linear - time algorithm for a trivially perfect graph . let @xmath241 be the @xmath240-tree of a connected trivially perfect graph @xmath7 . let @xmath58 and @xmath278 be given initial and target independent sets of @xmath3 , respectively . then , we determine whether @xmath279 as follows :    aaa    construct some particular target - assignment @xmath280 between @xmath0 and @xmath1 ; and    check whether @xmath280 is proper or not , using lemma  [ lem : lca ] .    we will show later in lemma  [ lem : no_case ] that it suffices to check only @xmath280 in order to determine whether @xmath279 or not . indeed , our linear - time algorithm executes ( a ) and ( b ) above at the same time , in the bottom - up manner based on @xmath241 . [ [ description - of - the - algorithm ] ] description of the algorithm + + + + + + + + + + + + + + + + + + + + + + + + + + + +    remember that the vertex - set associated to each @xmath242-node in @xmath241 induces a clique in @xmath3 . therefore , for any independent set @xmath62 of @xmath3 , each @xmath242-node contains at most one vertex in @xmath62 , and hence contains at most one token . we put a `` blue token '' for each @xmath242-node containing a blue vertex in @xmath0 , and also put a `` red token '' for each @xmath242-node containing a red vertex in @xmath1 . note that a @xmath242-node may contain a pair of blue and red tokens . our algorithm lifts up the tokens from the leaves to the root of @xmath241 , and if a blue token @xmath281 meets a red token @xmath282 at their least common ancestor @xmath283 in @xmath241 , then we replace them by a single `` green token . '' this corresponds to setting @xmath284 . more precisely , at initialization step , the algorithm first collects all leaves of @xmath241 in a queue , which is called _ the algorithm marks the nodes in the frontier , and lifts up each token to its parent @xmath242-node . each @xmath242-node @xmath175 is put into the frontier if its all children are marked , and then , all children of @xmath175 are removed from the frontier after the following procedure at @xmath175 :    aaa    @xmath175 contains at most one token : the algorithm has nothing to do . @xmath175 contains only one pair of blue token @xmath281 and red token @xmath282 : the algorithm replaces them by a single green token , and let @xmath284 . @xmath175 contains only green tokens : the algorithm replaces them by a single green token . @xmath175 contains two or more blue tokens , or two or more red tokens : the algorithm outputs `` no '' and halts ( that is , @xmath285 in this case ) . @xmath175 contains at least one green token and at least one blue or red token : the algorithm outputs `` no '' and halts ( that is , @xmath285 in this case ) .    repeating this process , and the algorithm outputs `` yes '' if and only when the frontier contains only the root @xmath242-node @xmath282 of @xmath241 which is in one of cases ( 1)(3 ) above . [ [ correctness - of - the - algorithm ] ] correctness of the algorithm + + + + + + + + + + + + + + + + + + + + + + + + + + + +    it is not difficult to implement our algorithm to run in @xmath36 time and @xmath36 space . therefore , we here prove the correctness of the algorithm . we first show that @xmath279 if the algorithm outputs `` yes . '' in this case , the algorithm is in cases ( 1 ) , ( 2 ) , or ( 3 ) at each @xmath242-nodes in @xmath241 ( including the root @xmath282 ) . then , the target - assignment @xmath280 has been ( completely ) constructed : for each blue vertex @xmath124 , @xmath286 is the red vertex in @xmath1 such that @xmath287 has the minimum height in @xmath241 among all vertices @xmath288 . then , we have the following lemma .    [ lem : yes_case ] if the algorithm outputs `` yes , '' then @xmath279 .    by lemma  [ lem : lca ] it suffices to show that the target - assignment @xmath280 constructed by the algorithm satisfies that the nodes @xmath289 and @xmath290 are not in the ancestor / descendant relationship on @xmath241 for every pair of vertices @xmath262 . we first consider the case where a @xmath242-node @xmath175 is in case ( 2 ) . then , there is exactly one pair of a blue token @xmath281 and a red token @xmath291 , and @xmath292 . since @xmath281 and @xmath282 did not meet any other tokens before @xmath175 , the subtree @xmath293 of @xmath241 contains only the two tokens @xmath281 and @xmath282 . therefore , the lemma clearly holds for @xmath293 . we then consider the case where a @xmath242-node @xmath175 is in case ( 3 ) . then , two or more least common ancestors of pairs of blue and red tokens meet at this node @xmath175 . notice that the green tokens were placed on children s node of @xmath175 in the previous step of the algorithm , and hence they were sibling in @xmath241 . therefore , their corresponding least common ancestors are not in the ancestor / descendant relationship on @xmath241 . the following lemma completes the correctness proof of our algorithm . [ lem : no_case ] if the algorithm outputs `` no , '' then @xmath69 . we assume that the algorithm outputs `` no . '' then , by lemma  [ lem : lca ] , it suffices to show that there is no target - assignment @xmath67 between @xmath0 and @xmath1 such that @xmath260 and @xmath261 are not in the ancestor / descendant relationship on @xmath241 for every pair of vertices @xmath262 . suppose for a contradiction that the algorithm outputs `` no , '' but there exists a target - assignment @xmath294 between @xmath0 and @xmath1 such that @xmath295 and @xmath296 are not in the ancestor / descendant relationship on @xmath241 for every pair of vertices @xmath262 . then , by lemma  [ lem : lca ] , @xmath294 is proper and hence @xmath297 . since the algorithm outputs `` no , '' there is a @xmath242-node @xmath175 which is in either case ( 4 ) or ( 5 ) . we first assume that the @xmath242-node @xmath175 is in case ( 4 ) . without loss of generality , at least two blue tokens @xmath298 and @xmath299 meet at this node @xmath175 . then , the @xmath240-tree @xmath241 contains two red tokens @xmath300 and @xmath301 placed on @xmath302 and @xmath303 , respectively . notice that , since @xmath298 and @xmath299 did not meet any red token before at the node @xmath175 , both @xmath300 and @xmath301 must be placed on either @xmath175 or nodes in @xmath304 . then , the least common ancestor @xmath305 must be an ancestor of @xmath175 , and so is the least common ancestor @xmath306 . the nodes @xmath305 and @xmath306 are in the ancestor / descendant relationship , a contradiction . thus , the algorithm outputs `` no '' because the @xmath242-node @xmath175 is in case ( 5 ) . in this case , without loss of generality , at least one blue token @xmath298 and at least one green token @xmath307 meet at this node @xmath175 . then , the red token @xmath300 corresponding to @xmath302 must be placed on either @xmath175 or some node in @xmath304 . therefore , the least common ancestor @xmath305 is an ancestor of @xmath307 . note that @xmath307 corresponds to the least common ancestor of some pair of blue and red tokens , say @xmath266 and @xmath308 , and @xmath309 is an ancestor of it . therefore , the nodes @xmath305 and @xmath296 are in the ancestor / descendant relationship on @xmath241 , a contradiction .      to complete the proof of theorem  [ th : trivialperfect ] , we finally show that our algorithm in section  [ subsec : algo_trivially ] can be modified so that it actually finds a shortest reconfiguration sequence between @xmath0 and @xmath1 . once we know that @xmath279 holds by the @xmath36-time algorithm in section  [ subsec : algo_trivially ] , we run it again with modification that `` green '' tokens are left at the corresponding least common ancestors . as in the proof of lemma  [ lem : lca ] , we can now obtain a reconfiguration sequence @xmath310 between @xmath24 and @xmath311 such that each token @xmath59 , @xmath61 , is slid at most twice . it is sufficient to output @xmath312 and @xmath313 , and hence the running time of the modified algorithm is proportional to @xmath32 , the number of independent sets in @xmath54 . since @xmath314 and each token @xmath59 , @xmath61 , is slid at most twice in @xmath54 , we have @xmath315 , that is , the length @xmath32 of @xmath54 is @xmath36 . therefore , the modified algorithm also runs in @xmath36 time and @xmath36 space . notice that each token @xmath59 is slid to its target vertex @xmath286 along a shortest path ( of length at most two ) between @xmath60 and @xmath286 without detour , and hence @xmath54 has the minimum length . this completes the proof of theorem  [ th : trivialperfect ] . the main result of this section is the following theorem .    [ th : caterpillar ] the sliding token problem for a connected caterpillar @xmath7 and two independent sets @xmath0 and @xmath1 of @xmath3 can be solved in @xmath36 time and @xmath36 space . moreover , for a yes - instance , a shortest reconfiguration sequence between them can be output in @xmath38 time and @xmath36 space . let @xmath316 be a caterpillar with spine @xmath102 which induces the path @xmath105 , and leaf set @xmath103 . we assume that @xmath317 , @xmath107 , and @xmath108 . first we show that we can assume that each spine vertex has at most one leaf without loss of generality . [ lem : cat ] for any given caterpillar @xmath316 and two independent sets @xmath0 and @xmath1 on @xmath3 , there is a linear time reduction from them to another caterpillar @xmath318 and two independent sets @xmath319 and @xmath320 such that ( 1 ) @xmath3 , @xmath0 , and @xmath1 are a yes - instance of the sliding token problem if and only if @xmath321 , @xmath319 , and @xmath1 are a yes - instance of the sliding token problem , ( 2 ) the maximum degree of @xmath321 is at most 3 , and ( 3 ) @xmath322 , where @xmath323 . in other words , the sliding token problem on a caterpillar is sufficient to consider only caterpillars of maximum degree 3 . on @xmath3 , let @xmath129 be any vertex in @xmath102 with @xmath324 . then there exist at least two leaves @xmath325 and @xmath326 attached to @xmath129 ( note that they are weak twins ) . now we consider the case that two tokens in @xmath0 are on @xmath325 and @xmath326 . then , we can not slide these two tokens at all , and any other token can not pass through @xmath129 since it is blocked by them . if @xmath1 contains these two tokens also , we can split the problem into two subproblems by removing @xmath129 and its leaves from @xmath3 , and solve it separately . otherwise , the answer is `` no '' ( remind that the problem is reversible ; that is , if tokens can not be slid , there are no other tokens which slide into the situation ) . therefore , if at least two tokens are placed on the leaves of a vertex of the original graph , we can reduce the case in linear time . thus we assume that every spine vertex with its leaves contains at most one token in @xmath0 and @xmath1 , respectively . then , by the same reason , we can remove all leaves but one of each spine vertex . more precisely , regardless whether @xmath279 or @xmath69 , at most one leaf for each spine vertex is used for the transitions . therefore , we can remove all other useless leaves but one from each spine vertex . especially , removing all useless leaves , we have @xmath322 . hereafter , we only consider the caterpillars stated in lemma [ lem : cat ] . that is , for any given caterpillar @xmath316 with spine @xmath105 , we assume that @xmath322 and @xmath327 for each @xmath328 . then , we denote the unique leaf of @xmath129 by @xmath325 if it exists . we here introduce a key notion of the problem on these caterpillars that is named _ locked _ path . let @xmath3 and @xmath62 be a caterpillar and an independent set of @xmath3 , respectively . a path @xmath329 on @xmath3 is _ locked _ by @xmath62 if and only if    aaa    @xmath34 is odd and greater than 2 ,    @xmath330 ,    @xmath331 ( in other words , they are leaves ) , and @xmath332 . this notion is simplified version of a _ locked _ tree used in @xcite . using the discussion in @xcite , we obtain the condition for the immovable independent set on a caterpillar :    [ th : cat - fix ] let @xmath3 and @xmath62 be a caterpillar and an independent set of @xmath3 , respectively . then we can not slide any token in @xmath62 on @xmath3 at all if and only if there exist a set of locked paths @xmath333 for some @xmath334 such that @xmath62 is a union of them . the proof can be found in @xcite , and omitted here . intuitively , for any caterpillar @xmath3 and its independent set @xmath62 , if @xmath62 contains a locked path @xmath175 , we can not slide any token through the vertices in @xmath175 . therefore , @xmath175 splits @xmath3 into two subgraphs , and we obtain two completely separated subproblems . ( we note that the endpoints of @xmath175 are leaves with tokens , and their neighbors are spine vertices without tokens . this property admits us to cut the graph at the spine vertices on the locked path . ) therefore , we obtain the following lemma :    [ lem : cat2 ] for any given caterpillar @xmath316 and two independent sets @xmath0 and @xmath1 on @xmath3 , there is a linear time reduction from them to another caterpillar @xmath318 and two independent sets @xmath319 and @xmath320 such that ( 1 ) @xmath3 , @xmath0 , and @xmath1 are a yes - instance of the sliding token problem if and only if @xmath321 , @xmath319 , and @xmath1 are a yes - instance of the sliding token problem , and ( 2 ) both of @xmath319 and @xmath320 contain no locked path .    in @xmath3 , when @xmath0 contains a locked path @xmath175 , it should be appear in @xmath1 ; otherwise , the answer is no . therefore , we can remove all vertices in @xmath175 and obtain the new graph @xmath335 with two independent sets @xmath336 and @xmath337 such that @xmath3 with @xmath0 and @xmath1 is a yes - instance if and only if @xmath335 with @xmath338 and @xmath339 is a yes - instance . repeating this process , we obtain disconnected caterpillar @xmath340 and two independent sets @xmath341 and @xmath342 such that both of @xmath341 and @xmath342 contain no locked paths . on a disconnected graph , we can solve the problem separately for each connected component . therefore , we can assume that the graph is connected , which completes the proof . hereafter , without loss of generality , we assume that the caterpillar @xmath3 with two independent sets @xmath0 and @xmath1 satisfies the conditions in lemmas [ lem : cat ] and [ lem : cat2 ] . that is , each spine vertex @xmath129 has at most one leaf @xmath325 , @xmath109 and @xmath110 have one leaf @xmath343 and @xmath344 , respectively , both of @xmath0 and @xmath1 contain no locked path , and @xmath2 . by the result in @xcite , this is a yes - instance . thus , it is sufficient to show an @xmath38 time algorithm that computes a shortest reconfiguration sequence between @xmath0 and @xmath1 . each pair @xmath345 can have at most one token . therefore , without loss of generality , we can assume that the blue vertices @xmath120 in @xmath0 are labeled from left to right ( according to the order @xmath346 , @xmath347 , @xmath31 , @xmath348 of @xmath3 ) , that is , @xmath121 if @xmath122 ; similarly , the red vertices @xmath123 are also labeled from left to right . then , we define a target - assignment @xmath66 , as follows : for each blue vertex @xmath124 @xmath349 to prove theorem  [ th : caterpillar ] , it suffices to show that @xmath67 is proper , and we can slide tokens with fewest detours . here , any token can not bypass the other token since each token is on a leaf or spine vertex . thus , by the results in @xcite , it has been shown that @xmath67 is proper . we show that we can compute a shortest reconfiguration in case analysis . now we introduce _ direction _ of a token @xmath350 denoted by @xmath351 as follows : when @xmath350 slides from @xmath352 in @xmath0 to @xmath353 in @xmath1 with @xmath354 , the direction of @xmath350 is said to be _ r _ and denoted by @xmath355 . if @xmath356 , it is said to be _ l _ and denoted by @xmath357 . if @xmath358 , the direction of @xmath350 is said to be _ c _ and denoted by @xmath359 .     has to precede the most left l token @xmath360.,scaledwidth=80.0% ]    we first consider a simple case : all directions are either r or l. in this case , we can use the same idea appearing in the algorithm for a proper interval graph in section [ sec : proper ] . we can introduce a partial order over the tokens , and slide them straightforwardly using the same idea in section [ subsec : algo_proper ] . intuitively , a sequence of r tokens are slid from left to right , and a sequence of l tokens are slid from right to left , and we can define a partial order over the sequences of different directions . the only additional considerable case is shown in  [ fig : rl ] . that is , when the token @xmath361 slides to @xmath325 from left and the other token @xmath360 slides to @xmath362 from right , @xmath361 should precede @xmath360 . it is not difficult to see that this ( and its symmetric case ) is the only exception than the algorithm in section [ subsec : algo_proper ] when all tokens slide to right or left . in other words , in this case , detour is required , and unavoidable . we next suppose that @xmath0 ( and hence @xmath1 ) contains some token @xmath350 with @xmath359 . in other words , @xmath350 is put on @xmath129 or @xmath325 for some @xmath12 in both of @xmath0 and @xmath1 . we have five cases . bbb    @xmath350 is put on @xmath325 in @xmath0 and @xmath1 . in this case , we have nothing to do ; @xmath350 does not need to be slid . @xmath350 is put on @xmath129 in @xmath0 and slid to @xmath325 in @xmath1 . in this case , we first slide it from @xmath129 to @xmath325 , and do nothing any more . then no detour is needed for @xmath350 . @xmath350 is put on @xmath325 in @xmath0 and slid to @xmath129 in @xmath1 . in this case , we lastly slide it from @xmath325 to @xmath129 , and no detour is needed for @xmath350 again .    @xmath350 is put on @xmath129 in @xmath0 and @xmath1 , and @xmath325 exists . using a simple induction by the number of tokens , we can determine if @xmath350 should make a detour or not in linear time . if not , we never slide @xmath350 . otherwise , we first slide @xmath350 to @xmath325 , and lastly slide back from @xmath325 to @xmath129 . it is clear that the length of detour with respect to @xmath350 is as few as possible . @xmath350 is put on @xmath129 in @xmath0 and @xmath1 , and @xmath325 does not exist . by assumption , @xmath363 ( since @xmath343 and @xmath344 exist ) . without loss of generality , we suppose @xmath350 is the leftmost spine vertex having the condition . we first observe that @xmath364 is at most 1 . clearly , we have no token on @xmath365 and @xmath362 . when we have two tokens on @xmath366 and @xmath367 , the path @xmath368 is a locked path , which contradicts the assumption . we also have @xmath369 by the same argument . now we consider the most serious case since the other cases are simpler and easier than this case . the most serious case is that a blue token on @xmath366 and a red token on @xmath367 . since any token can not bypass the other , @xmath0 contains an l token on @xmath366 , and @xmath1 contains an l token on @xmath367 . in this case , by the l token on @xmath366 , first , @xmath350 should make a detour to right , and by the l token in @xmath1 , @xmath350 next should make a detour to left twice after the first detour . it is clear that this three slides should not be avoided , and this ordering of three slides can not be violated . therefore , @xmath350 itself should slide at least four times to return to the original position , and @xmath350 can done it in four slides . during this slides , since @xmath350 is the leftmost spine with this condition , the tokens on @xmath370 do not make any detours . thus we focus on the tokens on @xmath371 . let @xmath372 be the token that should be on @xmath367 in @xmath1 . since @xmath350 is on @xmath129 , @xmath372 is not on @xmath373 . if @xmath372 is on one of @xmath374 in @xmath0 , we have nothing to do ; just make a detour for only @xmath350 . the problem occurs when @xmath372 is on @xmath375 in @xmath0 . if there exists @xmath376 , we first slide @xmath372 to it , and this detour for @xmath372 is unavoidable . if @xmath376 does not exist , we have to slide @xmath372 to @xmath377 before slide of @xmath350 . this can be done immediately except the only considerable case ; when we have another l or s token @xmath378 on @xmath377 . we can repeat this process recursively and confirm that each detour is unavoidable . since @xmath3 with @xmath0 and @xmath1 contains no locked path , this process will halts . ( more precisely , this process will be stuck if and only if this sequence of tokens forms a locked path on @xmath3 , which contradicts the assumption . ) therefore , traversing this process , we can construct the shortest reconfiguration sequence . * proof of theorem  [ th : caterpillar ] . * for a given independent set @xmath0 on a caterpillar @xmath27 , we can check if each vertex is a part of locked path as follows in @xmath36 time ( which is much simpler than the algorithm in @xcite ) :    aaa    initialize a state @xmath102 by `` not locked path '' . for @xmath379 , check @xmath129 and @xmath325 . we here denote their states by @xmath380 , where @xmath381 , @xmath382 such that @xmath383 means `` token is placed on the vertex '' , @xmath143 means `` no token is placed on the vertex '' , and @xmath384 means `` the leaf does not exist . '' in each case , update the state @xmath102 as follows :    bbb    if @xmath102 is `` not locked path , '' set @xmath102 by `` locked path ? , '' and remember @xmath12 as a potential left endpoint of a locked path . if @xmath102 is `` locked path '' , @xmath345 is a part of locked path . therefore , mark all vertices between the previously remembered left endpoint to this endpoint as `` locked path '' . after that , set @xmath102 by `` locked path ? '' again , and remember @xmath12 as a potential left endpoint of the next locked path . if there is a token on @xmath365 , nothing to do . if there is no token on @xmath365 , reset @xmath102 by `` not locked path '' ( regardless of the previous state of @xmath102 ) . reset @xmath102 by `` not locked path '' ( regardless of the previous state of @xmath102 ) . nothing to do . simple case analysis shows that after the procedure above , every vertex in a locked path is marked in @xmath36 time . thus , we first run this procedure twice for @xmath385 and @xmath386 in @xmath36 time , and check whether the marked vertices coincide with each other . if not , the algorithm outputs `` no '' . otherwise , the algorithm splits the caterpillar @xmath3 into subgraphs @xmath387 induced by only unmarked vertices . then we can solve the problem for each subgraph ; we note that two endpoints of which tokens are placed of a locked path @xmath175 are leaves . that is , for example , when a locked path @xmath329 splits @xmath3 into @xmath388 and @xmath389 , the neighbors of @xmath388 and @xmath389 in @xmath175 are @xmath390 and @xmath391 , and there are no token on them . thus , in the case , we can solve the problem on @xmath388 and @xmath389 separately , and we do not need to consider their neighbors .    for each subgraph @xmath392 , the algorithm next checks whether each subgraph contains the same number of blue and red tokens . if they do not coincide with each other , the algorithm output `` no.''otherwise , we have a yes - instance . the correctness of the algorithm so far follows from theorem [ th : cat - fix ] with results in @xcite immediately . it is also easy to implement the algorithm to run in @xmath36 time and space . it is not difficult to modify the algorithm to output the sequence itself based on the previous case analysis . for each token , the number of detours made by the token is bounded above by @xmath36 , the number of slides of the token itself is also bounded above by @xmath36 , and the computation for the token can be done in @xmath36 time . therefore , the algorithm runs in @xmath38 time , and the length of the sequence is @xmath38 . ( as shownn in the last paragraph in section [ sec : proper ] , there exist instances that require a shortest sequence of length @xmath239 . ) in this paper , we showed that the shortest sliding token problem can be solved in polynomial time for three subclasses of interval graphs . the computational complexity of the problem for chordal graphs , interval graphs , and trees are still open . especially , tree seems to be the next target . we can decide if two independent sets are reconfigurable in linear time @xcite , then can we find a shortest sequence for a yes - instance in polynomial time ? as in the 15-puzzle , finding a shortest sequence can be np - hard . for a tree , we do not know that the length can be bounded by any polynomial or not . it is an interesting open question whether there is any instance on some graph classes whose reconfiguration sequence requires super - polynomial length . demaine , e.d . , demaine , m.l . , fox - epstein , e. , hoang , d.a . , ito t. , ono , h. , otachi , y. , uehara , r. , yamada , t. : linear - time algorithm for sliding tokens on trees . theoretical computer science 600 , pp . 132142 ( 2015 )            hearn , r.a . , demaine , e.d . : pspace - completeness of sliding - block puzzles and other problems through the nondeterministic constraint logic model of computation . theoretical computer science 343 , pp . 7296 ( 2005 )                mouawad , a.e . , nishimura , n. , pathak , v. , raman , v. : shortest reconfiguration paths in the solution space of boolean formulas . in proc .  of icalp 2015 , lncs 9134 , pp . 985996 ( 2015 ) mouawad , a.e . , nishimura , n. , raman , v. , simjour , n. , suzuki , a. : on the parameterized complexity of reconfiguration problems . in proc .  of ipec 2013 , lncs 8296 , pp . 281294 ( 2013 ) mouawad , a.e . , nishimura , n. , raman , v. , wrochna , m. : reconfiguration over tree decompositions . in proc .  of ipec 2014 , lncs 8894 , pp . 246257 ( 2014 )
suppose that we are given two independent sets @xmath0 and @xmath1 of a graph such that @xmath2 , and imagine that a token is placed on each vertex in @xmath0 . 
 then , the sliding token problem is to determine whether there exists a sequence of independent sets which transforms @xmath0 into @xmath1 so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph . 
 the sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science . 
 the reconfiguration problems tend to be pspace - complete in general , and some polynomial time algorithms are shown in restricted cases . 
 recently , the problems that aim at finding a shortest reconfiguration sequence are investigated . for the 3sat problem 
 , a trichotomy for the complexity of finding the shortest sequence has been shown ; that is , it is in p , np - complete , or pspace - complete in certain conditions . in general , even if it is polynomial time solvable to decide whether two instances are reconfigured with each other , it can be np - complete to find a shortest sequence between them . 
 namely , finding a shortest sequence between two independent sets can be more difficult than the decision problem of reconfigurability between them . in this paper 
 , we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs . more precisely 
 , we can find a shortest sequence between two independent sets on a graph @xmath3 in polynomial time if either @xmath3 is a proper interval graph , a trivially perfect graph , or a caterpillar . 
 as far as the authors know , this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours .