Does the following type of hitting problem have a name?

Question

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the cardinality of the union $B_1\cup B_2\cup\dots\cup B_m$ is minimized. In other words, I want to hit each of the families $\mathcal F_i$ using as few elements of the ground set as possible.

Edit (an example for a special case): A scheduling problem that can be interpreted in this way is where you want to schedule a set of jobs indexed by $i$ (given by earliest start time $r_i$, latest completion time $d_i$ and processing time $p_i$) on a single machine of infinite capacity, and the objective is to minimize the total busy time of the machine. In this setting, the family $\mathcal F_i$ would just be the set of intervals $\{[r_i,r_i+p_i-1],[r_i+1,r_i+p_i],\dots,[d_i-p_i+1,d_i]\}$, and the problem can be solved efficiently (Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. “Real-time scheduling to minimize machine busy times”. In: Journal of Scheduling 18.6 (2015), p. 561-573, doi:10.1007/s10951-014-0411-z)

I am looking for references where this problem (or something similar) has been considered with more general families $\mathcal F_i$.

Answer 1

I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph $G=(A;B,E)$, with each of $A$ and $B$ sub-partitioned into a collection of equal-sized so-called supervertices. A superedge between two supervertices $a,b$ is the set edges of the form $u,v$ where $u \in a$ and $v \in b$. For a vertex set $S \subseteq A \cup B$, we say $S$ covers superedge $\hat{e}$ if there exists some $(u,v) \in \hat{e}$ such that $\{u,v\} \subseteq S$. The problem is then to find the smallest subset of $S \subseteq A \cup B$ such that all nonempty superedges are covered by $S$. Phrased alternatively, we wish to distinguish (at least) one "witness" edge per nonempty superedge, and the objective function is to minimize the cardinality of the union of the various distinguished edges' endpoints.

Viewed in this light, the connection to your problem is now straightforward. The set of vertices $A \cup B$ will become your ground set $[n]$. The collection of nonempty superedges will become the subset families $\mathcal{F}_i$. If a superedge $e$ contains the edge $(u,v)$, then its corresponding subset family contains the set $\{i,j\}$, where $i$ and $j$ are the images of $u$ and $v$ in this reduction.

There is a clear bijection between solutions the Min-Rep instance and in your original problem, and this bijection preserves objective value. Thus, your problem is at least as hard as Min-Rep to approximate, and Min-Rep is known to be hard to something like $2^{\log^{1-\epsilon} n}$ under standard complexity theoretic conjectures.

Min-Rep is very intimately related to the famous graph label cover problem. My guess is that your problem is also related (or maybe even equivalent) to hypergraph label-cover (probably using a similar reduction), but I'm not familiar with the recent literature in the area, and someone else can probably elaborate on that connection.