Enumerating proper intersections

Question

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?

Answer 1

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.