Reduction from Clique to something else
-
04-11-2019 - |
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange