• $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\}$.

Short example

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.

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


Your Answer

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