# Is this intersection set problem NP-Hard?

Suppose we have collection of n sets $$S_1, S_2, \dots, S_n$$. Each set has a size of at least $$k$$. We know for sure that $$\exists k$$ sets where all of them contain the same $$k$$ elements; $$|S_1 \cap S_2 \cap,\dots,\cap S_k| \geq k$$. We don't know the sets nor the intersection elements. I would like to know if these questions are NP-hard or if there is a polynomial algorithm to solve them.

1. Can we find the $$k$$ intersection elements in $$|S_1 \cap S_2 \cap,\dots,\cap S_k| \geq k$$?
2. Assume we have set $$S_t$$, we would like to know if set $$S_t$$ is one of the $$k$$ sets that have $$k$$ common elements among them. $$S_t \in ?$$ $$(S_1,S_2,\dots, S_k)$$. In other words, does $$S_t$$ intersect with any $$k-1$$ sets on the same $$k$$ elements?
• Question 2 may be related to the well known $k$-clique problem which is NPC. Feb 25 at 20:47
• The promise that such an intersection exists makes the problem trivially not $NP$-hard (assuming the promise complexity class), though the functional variant (returning the certificate) probably could still be $FNP$-hard?.. Feb 25 at 22:06
• Thanks for the reference to FNP; never heard of it before
– Xfae
Feb 26 at 23:14

This is at least as hard as the problem of detecting a $$k$$-clique in a graph, given a promise that there contains at least one $$k$$-clique in the graph. In particular, given a graph $$G$$, let $$S_i$$ be equal to the set of vertices adjacent to vertex $$i$$, along with $$i$$.
This problem is NP-hard. If you had a polynomial-time algorithm for your problem, then we could use it to solve the clique problem by running it multiple times, once for each possible value of $$k$$, and checking which is the largest value of $$k$$ for which it returns a valid $$k$$-clique.