4
$\begingroup$

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.

$\endgroup$

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.