7
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ The title of this question does not say much. Please modify it to say "Is Min Set Clique Completion Problem NP-hard". $\endgroup$
    – Shiva Kintali
    Nov 28, 2010 at 21:51

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ And why would $S_l = \{n+1\}$ not do the trick? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Nov 28, 2010 at 21:52
  • 2
    $\begingroup$ 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. $\endgroup$
    – Karolina Sołtys
    Nov 28, 2010 at 22:02
  • 2
    $\begingroup$ Thanks everyone for the observations.... indeed, it's a simple reduction (how embarrassing) and, no, this wasn't homework :) $\endgroup$
    – JimN
    Nov 28, 2010 at 22:29
  • 1
    $\begingroup$ 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} \} $ $\endgroup$
    – JimN
    Nov 28, 2010 at 22:51
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Karolina Sołtys
    Nov 28, 2010 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.