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
scroll top