1
$\begingroup$

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?
$\endgroup$
3
  • $\begingroup$ Question 2 may be related to the well known $k$-clique problem which is NPC. $\endgroup$ Feb 25 at 20:47
  • 1
    $\begingroup$ 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?.. $\endgroup$
    – rus9384
    Feb 25 at 22:06
  • $\begingroup$ Thanks for the reference to FNP; never heard of it before $\endgroup$
    – Xfae
    Feb 26 at 23:14

1 Answer 1

0
$\begingroup$

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.

See also https://en.wikipedia.org/wiki/Clique_problem and https://en.wikipedia.org/wiki/Planted_clique.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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