Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$.

I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. With the sets I'm working with, the cardinality of $|S_1 \cdot S_2|$ should be considerably smaller than $|S_1||S_2|$, thus I was wondering if there's a better solution. Is there an efficient data structure, which after preptime, can generate $S_1 \cdot S_2$, in $O(|S_1 \cdot S_2|+n^c)$ time? (so it takes polynomial time to create to encodes the pairings, and then constant time to return each pairing) I'd imagine there'd be a smart way to do this with posets, but a concrete structure eludes me currently.

If so, is there a way to be able to quickly update our structure, allowing us to add supersets of elements like so:

$$S_1 = S_1 \cup \{f(s_1,s_2) \supset s_1, \forall (s_1,s_2) \in S_1 \cdot S_2 \}$$ $$ S_2 = S_2 \cup \{ g(s_1,s_2) \supset s_2, \forall (s_1,s_2) \in S_1 \cdot S_2\}$$

with complexity $O(n^c|S_1 \cdot S_2|)$, where $f$ and $g$ are some arbitrary functions with the stated superset properties?



Your Answer

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

Browse other questions tagged or ask your own question.