Shortest Reconfiguration for Sliding Tokens on a Tree

Duc A. Hoang 28 May 2018 30 May 2018 research

Summary

This post contains a brief summary on the progress of solving Shortest Sliding Token for trees, a research problem I’ve focused on for some time.


Introduction

I’ve focused on Shortest Sliding Token for trees for quite some time. This problem falls into the category of combinatorial reconfiguration — a young and growing research area in theoretical computer science. More information regarding the history and development of this area can be found in the surveys [van den Heuvel, J., 2013] and [Nishimura, N., 2018]. In an instance of Shortest Sliding Token, two independent sets $I, J$ of a graph $G$ are given. Each independent set can be viewed as a set of tokens placed on distinct vertices of $G$ such that no two tokens are connected by an edge. A token can only be moved (slid) to one of its neighbors. A $\mathsf{TS}$-sequence of length $\ell$ in $G$ between $I$ and $J$ is a sequence of $\ell$ token-slides transforming $I$ into $J$ such that each intermediate result also forms an independent set of $G$. There are two variants of Shortest Sliding Token: the decision variant asks whether there exists a $\mathsf{TS}$-sequence between $I$ and $J$ of length at most $\ell$; while the non-decision variant asks for explicilty outputing (if exists) a $\mathsf{TS}$-sequence of minimum length between $I$ and $J$. It is well-known that the decision variant of Shortest Sliding Token is $\mathsf{NP}$-complete even when the input graph $G$ is a perfect graph and $\ell$ is polynomial in $\vert V(G) \vert$ [Kamiński, M. et al., 2012]. On the positive side, one can solve the non-decision variant of Shortest Sliding Token efficiently when the input graph is a cograph [Kamiński, M. et al., 2012], a proper interval graph, a trivially perfect graph, or a caterpillar [Yamada, T., Uehara, R., 2016]. Note that if we change the assumption by allowing that a set of tokens is any vertex-subset of $G$ (which is not necessarily independent) then the problem can be solved in polynomial time for any input graph; while it becomes $\mathsf{NP}$-complete even when there is one speical token and all others are identical (see [van den Heuvel, J., 2013]).

Motivation

For the last few years, Shortest Sliding Token remains open even when the input graph is a tree. It is well-known that for two independent sets $I, J$ of a tree $T$ on $n$ vertices, it takes $O(n)$ time for deciding if a $\mathsf{TS}$-sequence between $I$ and $J$ exists, and $O(n^2)$ time for outputing such a sequence (whose length is not necessarily shortest) [Demaine, E.D. et al., 2015]. One of the main issues when dealing with Shortest Sliding Token for trees is that a token may sometimes need to make “detour” in order to preserve the independence property of the resulting token-set. For example, in the figure below, the token $t$ on $v_2$ must be moved “up” to $v_1$ first, in order to allow the token $t^\prime$ on $v_3$ to move to the bottom-right vertex $v_5$. Once $t^\prime$ is placed on $v_5$, the token $t$ can now move back from $v_1$ to $v_2$.

A $\mathsf{TS}$-sequence between two independent sets $I = I_1$ and $J = I_5$ of a tree $T$.

For the case of caterpillars, each token in $I$ corresponds to a fixed destination vertex in $J$, and Yamada and Uehara [Yamada, T., Uehara, R., 2016] showed how to construct a shortest $\mathsf{TS}$-sequence between them (if exists) by analyzing all possible cases when a token is required to make detour. Performing a similar strategy for trees might be difficult, simply because there is no fixed destination for each token in $I$, and the number of ways to assign a destination for each token is $O(n!)$ (it is indeed the number of bijective mappings between $I$ and $J$), which is quite large.

Result

It has been annouced recently by Ken Sugimori (University of Tokyo, Japan) in the 11th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC 2018) that Shortest Sliding Token for trees can be solved in $O(poly(n))$ time when the input graph is a tree $T$ on $n$ vertices.

References

  1. Kamiński, M., Medvedev, P., Milanič, M.: Complexity of independent set reconfigurability problems. Theoretical Computer Science. 439, 9–15 (2012).
    doi:10.1016/j.tcs.2012.03.004.
  2. van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., and Wildon, M. (eds.) Surveys in Combinatorics 2013. pp. 127–160. Cambridge University Press (2013).
    doi:10.1017/CBO9781139506748.005.
  3. 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, 132–142 (2015).
    doi:10.1016/j.tcs.2015.07.037.
  4. Yamada, T., Uehara, R.: Shortest reconfiguration of sliding tokens on a caterpillar. In: Kaykobad, M. and Petreschi, R. (eds.) The 10th International Workshop on Algorithms and Computation, WALCOM 2016. pp. 236–248. Springer (2016).
    doi:10.1007/978-3-319-30139-6_19.
  5. Nishimura, N.: Introduction to Reconfiguration. Algorithms. 11, (2018).
    doi:10.3390/a11040052.