I have the following problem.
I have $n$ sets $A_1$ to $A_n$ each with $k$ elements. Any two sets are disjoint. I'm looking to determine a second set of $m$ sets $B_1$ to $B_m$ such that:
- the sets B contain elements from the sets A
- the sets B are disjoint
- the sets B contain all the elements from the sets A
- no two elements from the same A set can be in the same B set
- given any pair of A sets, at least one B set contains two elements where one belongs to one member of the pair and the other belongs to the second member
- the number of elements in any B set cannot exceed a value $l$, $l>k$, and $m$ is minimal
Formally:
- $\forall j, 1 \leq j \leq m, B_j \subseteq \bigcup_{i=1}^n A_i$
- $\forall i,j, 1 \leq i,j \leq m, i \neq j, B_i \cap B_j = \emptyset$
- $\bigcup_{i=1}^n A_i = \bigcup_{j=1}^m B_j$
- $\forall i,j, 1 \leq i \leq n, 1 \leq j \leq m, |A_i \cap B_j| \leq 1$
- $\forall i,j, 1 \leq i,j \leq n, i \neq j, \exists t, 1 \leq t \leq m, s.t. A_i \cap B_t \neq \emptyset \wedge A_j \cap B_t \neq \emptyset$
- $\forall j, 1 \leq j \leq m, |B_j| \leq l$
- $m$ is minimal
Any ideas on what the complexity of this problem is, what would be an equivalent more generic problem in set/graph theory and/or what an algorithm would be to determine the B sets?
EDIT:
$l$ is a fixed value, $k \leq l < n$ ($n$ can be assumed to be in the order of $l \cdot k$).
EDIT 2:
I would also be interested in solutions for the special case where $l=k$ and/or $n = k \cdot (l-1) + 1$. The latter condition implies that the existence condition ($\exists t$) in bullet $5$ above is strict, that is, $t$ is unique.