<p>I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem  (<a href="http://www.crab.rutgers.edu/~guyk/pub/hard/nabs.pdf" rel="nofollow noreferrer">introduced in this paper by Kortsarz</a>). Roughly, an input to Min-Rep consists of a bipartite graph <span class="math-container">$G=(A;B,E)$</span>, with each of <span class="math-container">$A$</span> and <span class="math-container">$B$</span> sub-partitioned into a collection of equal-sized  so-called <em>supervertices</em>. A <em>superedge</em> between two supervertices <span class="math-container">$a,b$</span> is the set edges of the form <span class="math-container">$u,v$</span> where <span class="math-container">$u \in a$</span> and <span class="math-container">$v \in b$</span>. For a vertex set <span class="math-container">$S \subseteq A \cup B$</span>, we say <span class="math-container">$S$</span> covers superedge <span class="math-container">$\hat{e}$</span> if there exists some <span class="math-container">$(u,v) \in \hat{e}$</span> such that <span class="math-container">$\{u,v\} \subseteq S$</span>. The problem is then to find the smallest subset of <span class="math-container">$S \subseteq A \cup B$</span> such that all nonempty superedges are covered by <span class="math-container">$S$</span>. 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.</p>

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

<p>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 <span class="math-container">$2^{\log^{1-\epsilon} n}$</span> under standard complexity theoretic conjectures.</p>

<p>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.</p>

CC BY-SA 4.0
2019-07-04T06:12:40.900Z
2019-07-07T18:42:43.180Z
2019-07-07T18:42:43.180Z
Yonatan N
<p>Given a ground set, say <span class="math-container">$[n]=\{1,2,\dots,n\}$</span>, and a collection of subset families <span class="math-container">$\mathcal F_i\subseteq 2^{[n]}$</span>, <span class="math-container">$i=1,2,\dots,m$</span>, I want to select <span class="math-container">$m$</span> sets <span class="math-container">$B_i\in\mathcal F_i$</span> such that the cardinality of the union <span class="math-container">$B_1\cup B_2\cup\dots\cup B_m$</span> is minimized. In other words, I want to hit each of the families <span class="math-container">$\mathcal F_i$</span> using as few elements of the ground set as possible.</p>

<p><strong>Edit (an example for a special case):</strong> A scheduling problem that can be interpreted in this way is where you want to schedule a set of jobs indexed by <span class="math-container">$i$</span> (given by earliest start time <span class="math-container">$r_i$</span>, latest completion time <span class="math-container">$d_i$</span>  and processing time <span class="math-container">$p_i$</span>) 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 <span class="math-container">$\mathcal F_i$</span> would just be the set of intervals <span class="math-container">$\{[r_i,r_i+p_i-1],[r_i+1,r_i+p_i],\dots,[d_i-p_i+1,d_i]\}$</span>, 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:<a href="https://doi.org/10.1007/s10951-014-0411-z" rel="nofollow noreferrer">10.1007/s10951-014-0411-z</a>)  </p>

<p>I am looking for references where this problem (or something similar) has been considered with more general families <span class="math-container">$\mathcal F_i$</span>.</p>

CC BY-SA 4.0
2019-07-05T14:56:55.237Z
A slight variant has been considered. The input is a single collection of sets $\mathcal{F}$ and an integer $k$ and the goal is to pick $k$ sets from the collection to minimize their union. This is the dual version of the $h$-densest hypergraph problem and is very hard to approximate under SETH.
Chandra Chekuri
<reference-request><packing><covering-problems>
Does the following type of hitting problem have a name?
Thomas Kalinowski
# Does the following type of hitting problem have a name?

(Asked by: username_0 on 2019-07-04)

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](https://doi.org/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$.

**Tags:** reference-request, packing, covering-problems
> **Comments:**
> **username_1**: A slight variant has been considered. The input is a single collection of sets $\mathcal{F}$ and an integer $k$ and the goal is to pick $k$ sets from the collection to minimize their union. This is the dual version of the $h$-densest hypergraph problem and is very hard to approximate under SETH.  

---

## 1 answers

### Answer by username_2 on 2019-07-04. Score: 3 | Accepted answer

I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem ([introduced in this paper by Kortsarz](http://www.crab.rutgers.edu/~guyk/pub/hard/nabs.pdf)). 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.


---

