The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article

🌾

Understanding Hitting Sets

2026/05/02に公開

What is a Hitting Set?

A Hitting Set is a set that has a non-empty intersection with each set in a given collection of sets.

For example, consider the following collection of sets:

A1 = {1, 2, 3}
A2 = {2, 4}
A3 = {3, 4, 5}

In this case,

{2, 3}

is a Hitting Set.

If we name this set $H$ , then:

A1 ∩ H = {2, 3}
A2 ∩ H = {2}
A3 ∩ H = {3}

Since it has a non-empty intersection with each set, $H$ can be called a Hitting Set.

Let $U$ be the universe (the universal set) and $\mathcal{S}$ be a collection of sets, specifically defined as follows:

U = {1, 2, 3, 4, 5}
S = {A1, A2, A3}

In this context, $H \subseteq U$ is called a Hitting Set if it satisfies the following condition:

\forall A \in \mathcal{S}, \; H \, \cap \, A \neq \emptyset

There is a distinction between Minimal and Minimum Hitting Sets.

Minimal Hitting Set: A set from which no element can be removed without it ceasing to be a Hitting Set.
Minimum Hitting Set: A Hitting Set with the smallest number of elements.

For instance, given:

A1 = {1, 2}
A2 = {2, 3}

{1, 3} is a Minimal Hitting Set.
On the other hand, {2} is a Minimum Hitting Set.

By using Hitting Sets, one can view MUS (Minimal Unsatisfiable Subset) and MCS (Minimal Correction Subset) in a dual relationship.