<p>Good question. I hope this is not a homework problem.</p>

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

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

<ul>
<li><p><strike>We construct an instance of MSCC with $U&#39; = 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.</strike> (<strong>Edit</strong> : this is wrong as pointed out in the comment.)</p></li>
<li><p>We construct an instance of MSCC with $U&#39; = 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 (<strong>Edit</strong> : Use this along with Karolina's fix in the comments).</p></li>
</ul>

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

CC BY-SA 2.5
2010-11-28T21:52:54.073Z
And why would $S_l = \{n+1\}$ not do the trick?
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-11-28T21:56:50.700Z
You meant $S_{l+1} = \{n+1\}$. Thanks for pointing it. I will fix the reduction.
Shiva Kintali
CC BY-SA 2.5
2010-11-28T22:02:02.023Z
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[2]-hard.
Karolina Sołtys
CC BY-SA 2.5
2010-11-28T22:29:16.840Z
Thanks everyone for the observations.... indeed, it's a simple reduction (how embarrassing) and, no, this wasn't homework :)
JimN
CC BY-SA 2.5
2010-11-28T22:51:08.373Z
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
CC BY-SA 2.5
2010-11-28T23:04:44.807Z
@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
CC BY-SA 2.5
2010-11-28T21:49:21.190Z
2010-11-28T22:11:21.280Z
2010-11-28T22:11:21.280Z
Shiva Kintali
<p>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.</p>

<p><b>
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?
</b></p>

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

<p>Does anyone know of this problem?</p>

CC BY-SA 2.5
2010-11-28T21:51:28.583Z
The title of this question does not say much. Please modify it to say "Is Min Set Clique Completion Problem NP-hard".
Shiva Kintali
<cc.complexity-theory><np-hardness>
Is Clique completion for intersection models hard?
JimN
# Is Clique completion for intersection models hard?

(Asked by: username_0 on 2010-11-28)

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?

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: The title of this question does not say much. Please modify it to say "Is Min Set Clique Completion Problem NP-hard".  

---

## 1 answers

### Answer by username_1 on 2010-11-28. Score: 9 | Accepted 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$.

> **Comments:**
> **username_2**: And why would $S_l = \{n+1\}$ not do the trick?  
> **username_1**: You meant $S_{l+1} = \{n+1\}$. Thanks for pointing it. I will fix the reduction.  
> **username_3**: 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[2]-hard.  
> **username_0**: Thanks everyone for the observations.... indeed, it's a simple reduction (how embarrassing) and, no, this wasn't homework :)  
> **username_0**: 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} \} $  
> **username_3**: @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$.  

---

