6
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm sorry that I did not really get the point. Where is $q$ in the reduced problem? Thank you. $\endgroup$ – RIC_Eien May 28 '13 at 8:45
  • $\begingroup$ Is that Vertex Number of $H$? $\endgroup$ – RIC_Eien May 28 '13 at 9:01
  • $\begingroup$ And what if $G$ is not a line graph? $\endgroup$ – RIC_Eien May 28 '13 at 9:05
  • 1
    $\begingroup$ $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. $\endgroup$ – Suresh Venkat May 28 '13 at 16:11
  • $\begingroup$ 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. $\endgroup$ – RIC_Eien May 28 '13 at 16:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.