<p>The problem is NP-complete. The reduction is from the <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">Set cover problem</a>. Let one user has all the files $F$. Then our only hope is to achieve $\mathcal{F}(G_2)= \mathcal{F}(G_1)$. So the question is, from given $2k-1$ sets, are there $k$ that cover the ground set? This easily reduces to the decision version of the Set cover problem after adding a few dummy users/files.</p>

<p>My old answer, which gives a polytime algorithm if we do not allow $\mathcal{F}(G_2)= \mathcal{F}(G_1)$:
Yes, you can check this in P. Your condition is equivalent to that there is an $f_i$ and $f_j$ such that $f_i\in \mathcal{F}(G_1)\setminus \mathcal{F}(G_2)$ and $f_j\in \mathcal{F}(G_2)\setminus \mathcal{F}(G_1)$. So all you have to do is for each pair, $f_i, f_j$, you check whether you can divide the users appropriately. This can be done if no user has both files and at most $k$ users have any of the files. The total running time is $O(n^2k)$ (if the info is stored appropriately) which can be easily improved.</p>

CC BY-SA 3.0
2013-11-24T10:14:34.207Z
domotrop: Thanks a lot!. Your solution is pretty elegant.
Vivek Bagaria
CC BY-SA 3.0
2013-11-24T10:33:10.570Z
But you have not considered the case when $\mathcal{F}(G1) = \mathcal{F}(G2) = \mathcal{F}$.
Vivek Bagaria
CC BY-SA 3.0
2013-11-28T21:35:25.850Z
Oops, you are right, this changes the answer! I have updated by answer.
domotorp
CC BY-SA 3.0
2013-12-02T18:08:00.080Z
Wow! Nice reduction domotorp. I wish i could upvote your answer more than once. Thanks again
Vivek Bagaria
CC BY-SA 3.0
2013-11-24T09:50:24.187Z
2013-11-24T14:01:49.370Z
2013-11-24T14:01:49.370Z
domotorp
<p>I am framing a particular combinatorial question using users and files for better understanding.</p>

<p>Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, u_{2k}\}$. Each user $u_i$ has a set of files denoted by $F(u_i) \subseteq F$. </p>

<p>Can the users be divided (whenever possible) into two equal sized group $G_1$ and $G_2$ in polynomial time in $n$, such that   $\mathcal{F}(G_1) = \bigcup_{u_i \in G_1} F(u_i)$ and similarly let 
$\mathcal{F}(G_2) = \bigcup_{u_j \in G_2} F(u_j)$ satisfy the following conditions:</p>

<p>$$\mathcal{F}(G_1)\not\subset \mathcal{F}(G_2) \text{ and } \mathcal{F}(G_2)\not\subset \mathcal{F}(G_1), $$
where $\not \subset$ means "not a strict subset".</p>

<p><strong>EDIT 1</strong>: The algorithm must to be polynomial time in $k$ and $n$.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2013-11-24T09:41:53.813Z
And I suppose also poly time in k, right?
domotorp
CC BY-SA 3.0
2013-11-24T10:08:04.623Z
domotorp: Yes poly time in k is needed.
Vivek Bagaria
<reference-request><co.combinatorics><np>
Dividing users with certain files into 2 equal groups
Vivek Bagaria
# Dividing users with certain files into 2 equal groups

(Asked by: username_0 on 2013-11-23)

I am framing a particular combinatorial question using users and files for better understanding.

Let there be a universe of files $F$ = $\{f\_1, f\_2,\ldots,f\_n\}$ and $2k$ users $\{u\_1, u\_2,\ldots, u\_{2k}\}$. Each user $u\_i$ has a set of files denoted by $F(u\_i) \subseteq F$.

Can the users be divided (whenever possible) into two equal sized group $G\_1$ and $G\_2$ in polynomial time in $n$, such that $\mathcal{F}(G\_1) = \bigcup\_{u\_i \in G\_1} F(u\_i)$ and similarly let
$\mathcal{F}(G\_2) = \bigcup\_{u\_j \in G\_2} F(u\_j)$ satisfy the following conditions:

$$\mathcal{F}(G\_1)\not\subset \mathcal{F}(G\_2) \text{ and } \mathcal{F}(G\_2)\not\subset \mathcal{F}(G\_1), $$
where $\not \subset$ means "not a strict subset".

**EDIT 1**: The algorithm must to be polynomial time in $k$ and $n$.

Thanks in advance.

**Tags:** reference-request, co.combinatorics, np
> **Comments:**
> **username_1**: And I suppose also poly time in k, right?  
> **username_0**: domotorp: Yes poly time in k is needed.  

---

## 1 answers

### Answer by username_1 on 2013-11-24. Score: 2 | Accepted answer

The problem is NP-complete. The reduction is from the [Set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem). Let one user has all the files $F$. Then our only hope is to achieve $\mathcal{F}(G\_2)= \mathcal{F}(G\_1)$. So the question is, from given $2k-1$ sets, are there $k$ that cover the ground set? This easily reduces to the decision version of the Set cover problem after adding a few dummy users/files.

My old answer, which gives a polytime algorithm if we do not allow $\mathcal{F}(G\_2)= \mathcal{F}(G\_1)$:
Yes, you can check this in P. Your condition is equivalent to that there is an $f\_i$ and $f\_j$ such that $f\_i\in \mathcal{F}(G\_1)\setminus \mathcal{F}(G\_2)$ and $f\_j\in \mathcal{F}(G\_2)\setminus \mathcal{F}(G\_1)$. So all you have to do is for each pair, $f\_i, f\_j$, you check whether you can divide the users appropriately. This can be done if no user has both files and at most $k$ users have any of the files. The total running time is $O(n^2k)$ (if the info is stored appropriately) which can be easily improved.

> **Comments:**
> **username_0**: domotrop: Thanks a lot!. Your solution is pretty elegant.  
> **username_0**: But you have not considered the case when $\mathcal{F}(G1) = \mathcal{F}(G2) = \mathcal{F}$.  
> **username_1**: Oops, you are right, this changes the answer! I have updated by answer.  
> **username_0**: Wow! Nice reduction domotorp. I wish i could upvote your answer more than once. Thanks again  

---

