2

Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?

  • sameCycle($\pi,x,y$): determines whether $x$ and $y$ belong to the same permutation cycle;
  • transpose($\pi,x,y$): replaces $\pi$ by the composition $(xy)\pi$ of the transposition $(xy)$ with $\pi$.

This can be viewed as a special case of the fully-dynamic graph connectivity problem in which the connected components are always cycles. Therefore it admits such a data structure, but one may hope that the cycle structure makes the problem easier and/or faster.

Timothy
  • 121
  • 2
  • 1
    Sounds something that should be doable with link/cut trees with $O(\log n)$ complexity because cycles are just one edge away from trees. – Laakeri Nov 16 '20 at 20:58

0 Answers0