Set Cover with bounded intersection size

Question

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

Answer 1

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.

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