1
$\begingroup$

Given $G(V,E)$ and $k$. Is there a clique with size $k$?

Given set $X = \{x_1,x_2,\dots,x_n \}$, and collection $A = \{A_1,A_2,...,A_n\}$ of sub-sets of $X$ and $k$. Are there are $k$ different elements in $A$, that every two of them has intersection that isn't empty? For example $A_1 = \{ x_1,x_2,x_3 \}$, $A_2 = \{x_4,x_5,x_1 \}$ so their intersection is $x_1$ and its valid, but it should be applied for every two $A_i,A_j$ in $A$.

Prove: That unnamed problem (which surely has a name) is NP-Hard.

The reduction is..

$X=E$, and every $A_i$ in $A$ is composed of edges that are connected to vertex $v_i$.

I can't understand the reduction, can someone explain why it works please?

$\endgroup$
1
$\begingroup$

$X = E$, so it remains to define the collection $A$. For each vertex $v_i$ in $V$ create $A_i$ as following: for each edge $x_t$ incident to the vertex $v_i$, add $x_t$ to $A_i$. Thus the edge $x_t=(v_i, v_j) \in E \Leftrightarrow A_i \cap A_j = \{x_t\}$, and every pair $A_i, A_j$ has at most one common element. So, if there are $k$ different elements in $A$ such that every two $A_i, A_j$ of them has non-empty intersection which is exactly the edge between vertices $v_i$ and $v_j$, then these $k$ vertices are pairwise connected meaning that they form a clique.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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