# Cardinalities in set coverings

Let

• $$I$$ be a set of items;
• $$C \subseteq \mathcal{P}(I)$$ be a set of subsets of $$I$$, where $$\mathcal{P}(I)$$ stands for the power set of $$I$$; And
• $$C(i) = \{ c \in C \mid i \in c \}$$ be the set of sets, in $$C$$, containing item $$i \in I$$.

We state the following definitions.

Definition 1: We say that $$\mathcal{C} \subseteq C$$ covers item $$i \in I$$ iff. $$C(i) \subseteq \mathcal{C}$$, i.e. all sets containing item $$i$$ belong to $$\mathcal{C}$$.

For instance, let's consider the below example, where

• $$I = \{1, \dots, 7 \}$$;
• $$C = \{a, b, c\}$$;
• $$a = \{1, 2, 4, 5\}$$;
• $$b = \{1, 2, 3, 6\}$$; And
• $$c = \{1, 3, 4, 7\}$$.

In this case, the following coverage (cover/covered by) relations are present.

• Node 1 is covered by $$\{a, b, c\}$$;
• Node 2 is covered by $$\{a, b, c\}$$, and $$\{a, b\}$$;
• Node 3 is covered by $$\{a, b, c\}$$, and $$\{b, c\}$$;
• Node 4 is covered by $$\{a, b, c\}$$, and $$\{a, c\}$$;
• Node 5 is covered by $$\{a, b, c\}, \{a, b\}, \{a, c\}$$, and $$\{a\}$$;
• Node 6 is covered by $$\{a, b, c\}, \{a, b\}, \{b, c\}$$, and $$\{b\}$$; And
• Node 7 is covered by $$\{a, b, c\}, \{a, c\}, \{b, c\}$$, and $$\{c\}$$;

Definition 2: $$\mathcal{C} \subseteq C$$ is violated iff. $$|\{ i \in I : C(i) \subseteq \mathcal{C} \}| > |\mathcal{C}|$$, i.e. the number of items covered by $$\mathcal{C}$$ is greater than the cardinality of $$\mathcal{C}$$.

Still using the previous example, we have the following list of violated sets.

• $$\{a, b\}$$, since $$|\{2, 5, 6\}| > |\{a, b\}|$$;
• $$\{a, c\}$$, since $$|\{4, 5, 7\}| > |\{a, c\}|$$;
• $$\{b, c\}$$, since $$|\{3, 6, 7\}| > |\{b, c\}|$$; And
• $$\{a, b, c\}$$, since $$|\{1, 2, 3, 4, 5, 6, 7\}| > |\{a, b, c\}|$$.

My question is, how could we find all violated $$\mathcal{C}$$s? Obviously, we could simply enumerate $$\mathcal{P}(C)$$ and pick the proper subsets, however, I would like to know if the above problem could be translated to another problem or, even if there is a polynomial treatment for it.

Thanks and regards.

• Considering the bipartite graph $(I, C, (\in))$. The condition looks similar to Hall's marriage condition but it is quite not the same. Commented Feb 13 at 18:20
• @pcpthm thank you very much. Commented Feb 14 at 18:02