<p>If I'm not mistaken, the case you specify (with $k =2$, $k_i = 3$) is in P. </p>

<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 <a href="http://en.wikipedia.org/wiki/Line_graph" rel="noreferrer">line graph</a> of $H$. </p>

<p>Verifying that $G$ is indeed a line graph and then finding $H$ can be done in <a href="http://en.wikipedia.org/wiki/Line_graph#CITEREFRoussopoulos1973" rel="noreferrer">linear time</a>. </p>

CC BY-SA 3.0
2013-05-28T08:45:31.123Z
I'm sorry that I did not really get the point. Where is $q$ in the reduced problem? Thank you.
RIC_Eien
CC BY-SA 3.0
2013-05-28T09:01:07.467Z
Is that Vertex Number of $H$?
RIC_Eien
CC BY-SA 3.0
2013-05-28T09:05:12.063Z
And what if $G$ is not a line graph?
RIC_Eien
CC BY-SA 3.0
2013-05-28T16:11:22.620Z
$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
CC BY-SA 3.0
2013-05-28T16:28:01.520Z
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
CC BY-SA 3.0
2013-05-28T16:47:13.523Z
For instance, the minimal non-line graph, $K_{1,3}$. The corresponding $\left | \bigcup_{i}^{4}S_{i} \right |_{max}=5$, instead of "no answer".
RIC_Eien
CC BY-SA 3.0
2013-05-28T17:00:18.887Z
Not sure I understand. why does the procedure return "no answer". in this case, what is the $q$ specified as part of the input ?
Suresh Venkat
CC BY-SA 3.0
2013-05-29T01:44:38.287Z
Sorry for my bad expression. In the case above, if $q=2,3,4,5$, the answer is "yes"(such sets do exist), and if $q=6$ or more, the answer is "no". But in your procedure, the answer is "$K_{1,3}$ is not a line graph", instead of "yes or no".
RIC_Eien
CC BY-SA 3.0
2013-05-29T08:36:48.243Z
Maybe I'm misunderstanding. Fix $q$=5. How do you get a solution if the induced graph is $K_{1,3}$ ?
Suresh Venkat
CC BY-SA 3.0
2013-05-29T13:28:11.740Z
$S_{1}$ is the center of $K_{1,3}$, others are $S_{2},S_{3}$ and $S_{4}$. $S_{1}=\{1,2\},S_{2}=\{1,3\},S_{3}=\{1,4\},S_{4}=\{1,5\}$. $\left| \bigcup_{i}^{4}S_{i} \right |=\{1,2,3,4,5\}=5$. Are there any mistakes?
RIC_Eien
CC BY-SA 3.0
2013-05-29T16:23:30.897Z
The graph induced by these sets (viewing each $S_i$ as an edge) is $K_{1,4}$, not $K_{1,3}$.
Suresh Venkat
CC BY-SA 3.0
2013-05-28T07:16:02.713Z
2013-05-28T07:16:02.713Z
Suresh Venkat
<p>I came up with a problem below, which looks like a linear programming problem:<br/></p>

<blockquote>
  <p>Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :<br/>
  $$
\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$. <br/>$k,k_{1},k_{2},...,k_{m}$ are constant positive integers. <br/>
  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$?</p>
</blockquote>

<p>I came up with this problem in order to judge complexity of <a href="https://cstheory.stackexchange.com/questions/17412">another graph problem</a>. 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.<br/>
By the way, what if $k=2,k_{1}=k_{2}=...=k_{m}=3$?</p>

<set-theory><cc.complexity-theory><np-complete>
What's complexity of this set problem which looks like "Linear Programming"?
RIC_Eien
# What's complexity of this set problem which looks like "Linear Programming"?

(Asked by: username_0 on 2013-05-27)

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](https://cstheory.stackexchange.com/questions/17412). 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$?

**Tags:** set-theory, cc.complexity-theory, np-complete


---

## 1 answers

### Answer by username_1 on 2013-05-28. Score: 5

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](http://en.wikipedia.org/wiki/Line_graph) of $H$.

Verifying that $G$ is indeed a line graph and then finding $H$ can be done in [linear time](http://en.wikipedia.org/wiki/Line_graph#CITEREFRoussopoulos1973).

> **Comments:**
> **username_0**: I'm sorry that I did not really get the point. Where is $q$ in the reduced problem? Thank you.  
> **username_0**: Is that Vertex Number of $H$?  
> **username_0**: And what if $G$ is not a line graph?  
> **username_1**: $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.  
> **username_0**: 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.  
> **username_0**: For instance, the minimal non-line graph, $K_{1,3}$. The corresponding $\left | \bigcup_{i}^{4}S_{i} \right |_{max}=5$, instead of "no answer".  
> **username_1**: Not sure I understand. why does the procedure return "no answer". in this case, what is the $q$ specified as part of the input ?  
> **username_0**: Sorry for my bad expression. In the case above, if $q=2,3,4,5$, the answer is "yes"(such sets do exist), and if $q=6$ or more, the answer is "no". But in your procedure, the answer is "$K_{1,3}$ is not a line graph", instead of "yes or no".  
> **username_1**: Maybe I'm misunderstanding. Fix $q$=5. How do you get a solution if the induced graph is $K_{1,3}$ ?  
> **username_0**: $S_{1}$ is the center of $K_{1,3}$, others are $S_{2},S_{3}$ and $S_{4}$. $S_{1}=\{1,2\},S_{2}=\{1,3\},S_{3}=\{1,4\},S_{4}=\{1,5\}$. $\left| \bigcup_{i}^{4}S_{i} \right |=\{1,2,3,4,5\}=5$. Are there any mistakes?  
> **username_1**: The graph induced by these sets (viewing each $S_i$ as an edge) is $K_{1,4}$, not $K_{1,3}$.  

---

