4
$\begingroup$

I asked this question on the CS theory stack exchange, but didn't get an answer. Was wondering whether anyone here might have some insight. Thanks in advance for any help.

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 $t$ sets such that the size of the maximum pairwise intersection between any two $t_i, t_j$ is $\leq k$? What is the complexity of this decision problem? Is minimizing the maximum pairwise intersection between the sets $\mathsf{NP}$-hard?

A comment on the CS Theory stackexchange pointed out that this probably is not NP-complete, since verifying the intersection of all of the sets is quadratic in t and therefore exponential in the size of the input.

There is a lower bound on the max pairwise intersection given by ceiling(number of identical value pairs / number of set pairs), $\lceil (s \cdot {r \choose 2}) / {t \choose 2} \rceil$. This is a natural value for $k$ above, making the question whether there exists an assignment that achieves this bound.

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 wonder if you ever answered your own question or did any further work? Self answers are allowed and even encouraged. :) $\endgroup$ – Wildcard Jun 7 '17 at 0:17

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.