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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.