Dividing users with certain files into 2 equal groups

Question

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.

Answer 1

The problem is NP-complete. The reduction is from the 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.