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?
Is Clique completion for intersection models hard?
cc.complexity theory;np hardness
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$.