I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently:

  1. Add a new element $i$ to $I$.
  2. Identify elements $i, j \in I$, i.e. take the quotient set $I' = I_{/ i \sim j}$ and take for $R'$ the obvious relation on $I'$ induced by $R$, i.e. \begin{equation} R'([i_1], \dots, [i_d]) \iff \exists j_1 \sim i_1, \dots, i_n \sim j_n: R(j_1, \dots, j_n) \end{equation} where $[-]$ denotes equivalence class under $\sim$. For example, if $d = 2$ and $k \neq i, j$, then $R'([i], [k]) \iff R(i, k) \lor R(j, k)$.
  3. Check whether elements $i, j \in I$ are equal/represent the same element.
  4. Insert a tuple $(i_1, \dots, i_d)$ into $R$
  5. Check whether a tuple $(i_1, \dots, i_d)$ is in $R$.

If it weren't for the relation $R$, then a union-find data structure would be a perfect solution, supporting 1, 2 (minus the relation part) and 3 in essentially constant time. On the other hand, a hash table would support 4 and 5 in constant time. I don't see a way of combining those data structures without blowing up some step to $O(\mathrm{max}(|R|, |I|))$ though.

Bonus points if the data structure can be adapted to support snapshots, i.e. saving the current $(I, R)$ and reverting back to it later efficiently.


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.