1
$\begingroup$

Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ is expensive (say, $O(n^2)$).

I am looking for an efficient data structure $D$ that supports queries of the form "given $s$, does $D$ contain an element $s'$ in the same equivalence class as $s$"?
A naive approach is to search element by element in $D$ and test, but is there other solution?

$\endgroup$

1 Answer 1

2
$\begingroup$

The best you can do is keep track of all currently known equivalences using a Union-Find data structure. Initially, each element is in own group. Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.