<p>If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this <a href="https://cstheory.stackexchange.com/questions/20386/restriction-of-exact-cover-by-3-sets">cstheory question</a>.</p>

<p>EXACT COVER BY THREE SETS (X3C):</p>

<p><strong>Instance</strong>: Set $X=\{x_1,x_2,...,x_{3q}\}$ and a collection $C=\{C_1,...,C_m\}$ of 3-element subsets of $X$.<br>
<strong>Question</strong>: Does C contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$ such that every element of $X$ occurs in exactly one member of $C′$?</p>

<p>X3C is NP-complete (see G&amp;J), and as shown in [1] it remains NP-complete even if every element $x_i$ is contained in exactly 3 subsets of $C$ (RESTRICTED EXACT COVER BY THREE SETS, RX3C).</p>

<p>I proved that it remains NP-complete even if every pair of subsets in $C$  share at most one element; i.e. for all $i\neq j$, $|C_i \cap C_j|\leq 1$ (I called this restricted version SINGLE OVERLAP RX3C).</p>

<p>The SET COVER WITH BOUNDED INTERSECTION SIZE 1 (its decision version)  is simply a generalization of SINGLE OVERLAP RX3C, indeed you can pick the same universe $X$  and the same collection of subsets $C_1,...C_m$ of the SINGLE OVERLAP RX3C and ask for a cover with $q$ subsets or less.</p>

<p>Obviously a cover with $&lt; q$ subsets cannot exist because every subset contains three elements and there are $3q$ elements in $X$. A cover with $q$ subsets must be exact: if two subsets contain a shared element then there are less than $3q$ elements covered.</p>

<p>[1] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).</p>

CC BY-SA 3.0
2014-05-01T00:47:35.380Z
2014-05-01T01:04:08.557Z
2017-04-13T12:32:28.080Z
Marzio De Biasi
<p>So, the set cover problem is trivial if none of the candidate sets intersect eachother.</p>

<p>However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-hard?</p>

<p>I would appreciate any insight.</p>

<p>Thanks,
Garrett</p>

CC BY-SA 3.0
2014-04-24T22:58:03.587Z
This paper might be relevant: http://www.hariharan-ramesh.com/papers/setco.pdf
Hsien-Chih Chang 張顯之
<set-cover>
Set Cover with bounded intersection size
Garrett Andersen
# Set Cover with bounded intersection size

(Asked by: username_0 on 2014-04-24)

So, the set cover problem is trivial if none of the candidate sets intersect eachother.

However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-hard?

I would appreciate any insight.

Thanks,
Garrett

**Tags:** set-cover
> **Comments:**
> **username_1**: This paper might be relevant: http://www.hariharan-ramesh.com/papers/setco.pdf  

---

## 1 answers

### Answer by username_2 on 2014-05-01. Score: 5

If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this [cstheory question](https://cstheory.stackexchange.com/questions/20386/restriction-of-exact-cover-by-3-sets).

EXACT COVER BY THREE SETS (X3C):

**Instance**: Set $X=\{x\_1,x\_2,...,x\_{3q}\}$ and a collection $C=\{C\_1,...,C\_m\}$ of 3-element subsets of $X$.  
**Question**: Does C contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$ such that every element of $X$ occurs in exactly one member of $C′$?

X3C is NP-complete (see G&J), and as shown in [1] it remains NP-complete even if every element $x\_i$ is contained in exactly 3 subsets of $C$ (RESTRICTED EXACT COVER BY THREE SETS, RX3C).

I proved that it remains NP-complete even if every pair of subsets in $C$ share at most one element; i.e. for all $i\neq j$, $|C\_i \cap C\_j|\leq 1$ (I called this restricted version SINGLE OVERLAP RX3C).

The SET COVER WITH BOUNDED INTERSECTION SIZE 1 (its decision version) is simply a generalization of SINGLE OVERLAP RX3C, indeed you can pick the same universe $X$ and the same collection of subsets $C\_1,...C\_m$ of the SINGLE OVERLAP RX3C and ask for a cover with $q$ subsets or less.

Obviously a cover with $< q$ subsets cannot exist because every subset contains three elements and there are $3q$ elements in $X$. A cover with $q$ subsets must be exact: if two subsets contain a shared element then there are less than $3q$ elements covered.

[1] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).


---

