# What's complexity of this set problem which looks like “Linear Programming”?

I came up with a problem below, which looks like a linear programming problem:

Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :
$$\forall i=1, 2, 3,...,n\space\space \left | S_{i} \right |=k;\\ \left | S_{j_{11}}\bigcup S_{j_{12}} \right |\leqslant k_{1};\\ \left | S_{j_{21}}\bigcup S_{j_{22}} \right |\leqslant k_{2};\\ ...\\ \left | S_{j_{m1}}\bigcup S_{j_{m2}} \right |\leqslant k_{m}.\\$$ $j_{11},j_{21},...,j_{m1},j_{12},j_{22},...,j_{m2}$ are integers between $1$ and $n$.
$k,k_{1},k_{2},...,k_{m}$ are constant positive integers.
The questions is: For a positive integer $q$,Do such $S_{1}, S_{2},..., S_{n}$ exsit, such that $\left| \bigcup_{i}^{n}S_{i} \right |=q$?

I came up with this problem in order to judge complexity of another graph problem. But I failed to find any relative research. So has complexity of this kind of problem been studied? Is this problem NP-Complete or just P? How to judge this problem? Thanks.
By the way, what if $k=2,k_{1}=k_{2}=...=k_{m}=3$?

If I'm not mistaken, the case you specify (with $k =2$, $k_i = 3$) is in P.
Note that the condition $|S \cup S'| \le 3$ is equivalent to saying that $S, S'$ intersect (since $k=2$). Thus, if you think of the $S_i$ as vertices, then the constraints specify a graph $G$, and your problem reduces to finding a graph $H$ such that $G$ is the line graph of $H$.
Verifying that $G$ is indeed a line graph and then finding $H$ can be done in linear time.
• I'm sorry that I did not really get the point. Where is $q$ in the reduced problem? Thank you. – RIC_Eien May 28 '13 at 8:45
• Is that Vertex Number of $H$? – RIC_Eien May 28 '13 at 9:01
• And what if $G$ is not a line graph? – RIC_Eien May 28 '13 at 9:05
• $q$ is the number of vertices in $H$, and if $G$ is not a line graph, the procedure will say so. In other words, the problem can be decided in polynomial time. – Suresh Venkat May 28 '13 at 16:11
• I cannot agree. The answer depends on not only $G$, but also $q$. In your procedure, however, only "whether $G$ is a line graph or not" would be considered. – RIC_Eien May 28 '13 at 16:28