# Minimal Hitting Sets Problem

Let $$\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$$ a collection of subset of some universe $$U$$.

We want to find a partition $$P$$ of $$\mathcal{I}$$ of minimal cardinality such that the intersection of each set in $$P$$ is not empty.

Is this, or the corresponding decision problem, a well known problem? I found many similar problem, such as the hitting set problem and the set cover problem, but I did not find my problem.

Also, in the context I'm using it, sets $$I_j$$ are closed intervals $$[a_j, b_j]$$ of real numbers. I've also looked into scheduling problems, with no results. Is this a well known scheduling problem?

• Can you illustrate with an example? It looks the partition problem in the question is the optimization version of the usual hitting set problem, which is NP-hard. However, the case with closed intervals, which should be well-known, can be done in $O(n\log n)$ time. May 11, 2023 at 19:24
• @JohnL. I don't have an example, it's a subproblem that emerged from the study of a learned index structure. I already have a linear algorithm for the case with closed intervals: sort the I_js lexicographically, and then proceed in a greedy way, which I think founds a minimal partition. May 11, 2023 at 22:15
• @JohnL. If this case is well known, do you know some names that are used to refer to it, or some references in general? May 11, 2023 at 22:16

Define $$s_x = \{I_j \mid x \in I_j\}$$ for each $$x \in U$$. The set cover problem is to find a minimal cardinality set $$X$$ such that $$\cup_{x \in X} s_x = U$$. Any solution to this set cover problem immediately yields a partition $$P$$ of the same cardinality; namely, we initially treat each $$s_x$$ (for each $$x \in X$$) as part of the partition, and if two parts $$s_x,s_y$$ have some $$I_j$$ in common, we remove $$I_j$$ from one of them, and repeat until this is a partition. Conversely, any solution $$P$$ to your problem yields a solution to the set cover problem of the same cardinality; namely, pick one element $$x$$ from the intersection of each part of $$P$$ and add it to $$X$$.