# Enumerating proper intersections

Let

• $$U \subset \mathbb{N}$$ be a finite universe set;
• $$B$$ be a set of nonempty subsets of $$U$$ such that $$B$$ covers all elements in $$U$$, i.e. $$\bigcup_{b \in B} b = U$$, and if $$b \in B$$ then $$b \subseteq U \wedge b \neq \emptyset$$;
• $$c(i) = \{ b \in B : i \in b \}$$ be the set of all subsets containing element $$i \in U$$;
• $$\cap(C) = \bigcap_{b \in C} b$$ be the intersection of all sets in $$C \subseteq B$$; And
• $$\cup_E(C) = \{ i \in U : c(i) \subseteq C \}$$ be the exclusive union of all elements in $$C \subseteq B$$; here the word 'exclusive' stands for proper, in a sense that an element $$i$$ belongs to the exclusive union of $$C$$ iff. the sets containing $$i$$ ($$c(i)$$) are covered by $$C$$.

We say that an element $$i$$ dominates an element $$j$$ iff. $$i \neq j$$ and

$$\exists_{C \subseteq B} (|C|\ge 1 \wedge i \in \cap(C) \wedge j \in \cup_E(C))\tag{Dominance}$$

That is, $$i$$ dominates $$j$$ iff. the elements are different, and there exist some set of sets $$C \subseteq B$$ such that $$i$$ belongs to the intersection of $$C$$ and $$j$$ to the exclusive union $$\cup_E(C)$$.

For instance, in the picture below, we have that:

• 1 dominates 2, 3 and 9: Since $$1 \in \cap(\{b_1, b_2\})$$ and $$2, 3, 9 \in \cup_E(\{b_1, b_2\}) = \{1, 2, 3, 9\}$$;
• 5 dominates 6 and 9: Since $$5 \in \cap(\{ b_2, b_3 \})$$ and $$6, 9 \in \cup_E(\{ b_2, b_3 \}) = \{ 5, 6, 9 \}$$; And
• The remaining dominance relationships; A straightforward strategy for determining whether there is a dominance relationship between two elements $$i$$ and $$j$$, is to algorithmically check the condition $$(\text{Dominance})$$, which would take a time complexity of $$\mathcal{O}(2^{|B|})$$, as it would be required to enumerate the power set of $$B$$.

My question is, given a pair of elements $$i$$ and $$j$$, is there any strategy for determining whether such set of sets $$C \subseteq B$$ exist in a polynomial time?

• Thanks for the attention. An update was added. Nov 16 at 18:40

Yes. If there is any $$C$$ that works, then taking $$C = c(i)$$ works [*]. It is easy to compute $$c(i)$$ and then check if it satisfies your definition.
Better yet, the following is a simpler characterization of dominance: $$i$$ dominates $$j$$ if $$i\ne j$$ and $$\forall b \in B$$, $$j \in b \implies i \in b$$. This makes it easy to check for dominance in linear time, by iterating through all sets in $$B$$ and checking whether $$j \in b$$ and whether $$i \in b$$.
Footnote [*]: Why is this true? It is easy to verify that if you have two candidates $$C_1,C_2$$, where $$C_1 \subseteq C_2$$, and if $$j \in \cup_E(C_1)$$, then $$j \in \cup_E(C_2)$$ too. So we might as well take $$C$$ to be as large as possible, subject to the restriction that $$C \subseteq B$$ and $$i \in \cap(C)$$, and then check whether $$j \in \cup_E(C)$$. $$c(i)$$ is the largest such set.
• Thanks for the comment, but there is a constraint I forgot of including: $|C| > 1$ in the dominance condition. Nov 16 at 18:42