# Is Clique completion for intersection models hard?

The following seems like a natural problem and I'm surprised I can't find any literature on it... but maybe it's because I don't know the name for it.

Given a list of sets $S_1, S_2, S_3, \ldots$ Can we make $k$ additions (that is, adding an element to any single $S_i$ ) so that every pair of sets has nonempty intersection?

If we treat each subset $S_i$ as a vertex and say two vertices are adjacent if their corresponding sets have at least one common element, this is like an intersection model for a graph and we are augmenting the representation to turn the graph into a clique. I think of this as some sort of "clique completion" problem, but I don't know if it has been studied in another context under a different name.

Does anyone know of this problem?

• The title of this question does not say much. Please modify it to say "Is Min Set Clique Completion Problem NP-hard". – Shiva Kintali Nov 28 '10 at 21:51

## 1 Answer

Good question. I hope this is not a homework problem.

I don't know if this problems exists in the literature, so let's call your problem Min Set Clique Completion Problem (MSCC). Here is a reduction from Hitting Set Problem to MSCC. Hitting Set problem is a well-known NP-complete problem.

Instance of Hitting Set problem is as follows : Let $U = \{1,2,\dots,n\}$ be the ground set. Let $T_1, T_2, \dots, T_l$ be $l$ subsets of $U$. Find a set $H \subseteq U$ that has at least one element from each set $T_i$. The goal is to minimize $|H|$.

• We construct an instance of MSCC with $U' = U \cup \{n+1\}$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i \cup \{n+1\}$ and $S_{l+1}$ is an empty set. (Edit : this is wrong as pointed out in the comment.)

• We construct an instance of MSCC with $U' = U$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i$ and $S_{l+1}$ is an empty set (Edit : Use this along with Karolina's fix in the comments).

Now if we run MSCC on this instance the solution $S_{l+1}$ returned by MSCC is precisely the hitting set of the sets $T_1, T_2, \dots, T_l$.

• And why would $S_l = \{n+1\}$ not do the trick? – Kristoffer Arnsfelt Hansen Nov 28 '10 at 21:52
• I was just writing the same reduction :) We can fix the above by adding $n^2$ new elements $a_{11}, a_{12},...,a_{1n},...a_{nn}$ to the universe, and having $S_i$ and $S_j$ sharing exactly $a_{ij}$ (we set $S_i$ to be $T_i \cup \bigcup_{j = 1...n} a_{ij})$. Adding one of these $a_{ij}$ elements to $S_{l+1}$ doesn't help, because it makes it intersect with at most 2 more sets, so we have to create the solution in $S_{l+1}$ without cheating. This actually shows that this problem is not only NP-hard, but even W-hard. – Karolina Sołtys Nov 28 '10 at 22:02
• Thanks everyone for the observations.... indeed, it's a simple reduction (how embarrassing) and, no, this wasn't homework :) – JimN Nov 28 '10 at 22:29
• Hold on... the construction: * we set $S_i$ to be $T_i \cup \bigcup_{j = 1...n} a_{ij}$ does not ensure all the $S_i$ sets to have intersection... perhaps it should instead be * we set $S_i$ to be $T_i \cup \bigcup_{j = 1...n} \{ a_{ij}, a_{ji} \}$ – JimN Nov 28 '10 at 22:51
• @Jim: you're right. I think your suggestion works, but maybe it would be more elegant just to make $n(n+1)/2$ new elements, $a_{ij}$ for $i, j \in \{{1,...,n\}}, i < j$, and add to $T_i$ all the elements $a_{jk}$ where $i=j$ or $i=k$. – Karolina Sołtys Nov 28 '10 at 23:04