2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And I suppose also poly time in k, right? $\endgroup$ – domotorp Nov 24 '13 at 9:41
  • $\begingroup$ domotorp: Yes poly time in k is needed. $\endgroup$ – Vivek Bagaria Nov 24 '13 at 10:08
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ domotrop: Thanks a lot!. Your solution is pretty elegant. $\endgroup$ – Vivek Bagaria Nov 24 '13 at 10:14
  • $\begingroup$ But you have not considered the case when $\mathcal{F}(G1) = \mathcal{F}(G2) = \mathcal{F}$. $\endgroup$ – Vivek Bagaria Nov 24 '13 at 10:33
  • 1
    $\begingroup$ Oops, you are right, this changes the answer! I have updated by answer. $\endgroup$ – domotorp Nov 28 '13 at 21:35
  • $\begingroup$ Wow! Nice reduction domotorp. I wish i could upvote your answer more than once. Thanks again $\endgroup$ – Vivek Bagaria Dec 2 '13 at 18:08

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.