0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – John L.
    May 11, 2023 at 19:24
  • $\begingroup$ @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. $\endgroup$
    – matteo_c
    May 11, 2023 at 22:15
  • $\begingroup$ @JohnL. If this case is well known, do you know some names that are used to refer to it, or some references in general? $\endgroup$
    – matteo_c
    May 11, 2023 at 22:16

1 Answer 1

1
$\begingroup$

This is NP-hard and is closely related to the set cover problem.

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$.

This shows that there is a one-to-one correspondence between solutions to your problem and solutions to the associated set cover problem.

$\endgroup$

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.