0
$\begingroup$

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;

Example

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?

$\endgroup$
1
  • $\begingroup$ Thanks for the attention. An update was added. $\endgroup$ Nov 16, 2023 at 18:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the comment, but there is a constraint I forgot of including: $|C| > 1$ in the dominance condition. $\endgroup$ Nov 16, 2023 at 18:42
  • $\begingroup$ By the way, I think your reasoning also works even with this new constraint. $\endgroup$ Nov 16, 2023 at 18:43

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.