5
$\begingroup$

Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is:

Is it possible to construct these sets such that the size of the maximum pairwise intersection between any two $t_i, t_j$ is $k$? Is this question $\mathsf{NP}$-complete? Or equivalently, is minimizing the maximum pairwise intersection between the sets $\mathsf{NP}$-hard?

There is a lower bound on the max pairwise intersection given by ceiling(number of identical value pairs / number of set pairs), meaning $\lceil (s \cdot {r \choose 2}) / {t \choose 2} \rceil$.

The problem seems related to, but slightly different from, the block design problem. In the block design problem, there is a parameter $\lambda$ that dictates in how many of the $t$ sets each pair of integers in $\{1, \ldots, s\}$ must appear, so if $\lambda$ is 1, the maximum pairwise intersection between sets is 1 (since each pair of values appears in at most 1 set together). I've seen claims that deciding the existence of a block design is $\mathsf{NP}$-complete, but no actual proof - would also appreciate any link to such a proof.

$\endgroup$
  • $\begingroup$ I have two problems with this question. 1) What is k, is it a part of the input? Do you want exactly k or <=k? 2) Is the input unary or binary? If the latter, why is the problem in NP? In either case, I really don't think there is any chance for it to be NP-complete. $\endgroup$ – domotorp Jul 14 '13 at 15:07
  • $\begingroup$ 1) k could be part of the input, but there is also the simpler question of whether there is a solution that achieves the lower bound given above. $\endgroup$ – ragip Jul 14 '13 at 20:28
  • $\begingroup$ 2) This is a good point. So verifying a solution would take exponential time in the size of the input. Any suggestions as to what I should expect the complexity of this problem to be then? Also, I've seen claims that deciding block design existence is NP-complete, but it seems to me that this same consideration should apply - is there something I'm missing here? $\endgroup$ – ragip Jul 14 '13 at 21:05
  • $\begingroup$ Maybe the problem is that given unary parameters and a set system on the base set, whether it can be extended into a suitable family, these sort of problems are often NP-complete. $\endgroup$ – domotorp Jul 15 '13 at 5:05

Your Answer

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

Browse other questions tagged or ask your own question.