<p>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: </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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$. </p>

<p>The problem seems related to, but slightly different from, the <a href="http://en.wikipedia.org/wiki/Block_design" rel="nofollow">block design problem</a>. 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.</p>

CC BY-SA 3.0
2013-07-14T15:07:49.023Z
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.
domotorp
CC BY-SA 3.0
2013-07-14T20:28:46.177Z
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.
ragip
CC BY-SA 3.0
2013-07-14T21:05:58.050Z
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?
ragip
CC BY-SA 3.0
2013-07-15T05:05:19.563Z
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.
domotorp
<np-hardness><partition-problem>
Variation on block design/set cover
ragip
# Variation on block design/set cover

(Asked by: username_0 on 2013-07-13)

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](http://en.wikipedia.org/wiki/Block_design). 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.

**Tags:** np-hardness, partition-problem

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  

---

## 0 answers

