[Solved]: How to partition a set into a given number of disjoint subsets subject to some conditions?

Problem Detail: 

I am given a set $A\triangleq\{1,\ldots,k\}$, an integer $s\leqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of $\{1,\ldots,k\}$ such that:

1. $\bigcup_{j=1}^s S_j=A$; and
2. $|S_j|\leqslant a_{ij}$ for all $i\in S_j$ and $j=1,\ldots,s$.

How to solve this problem? Is it hard to find a feasible solution?

I think it is not easy to solve the problem because I tried some procedure that starts by some $j\in\{1,\ldots,n\}$ and assigns $i\in\{1,\ldots,k\}$ until the number of $i$ assigned to $j$ are greater than $a_{ij}$ for some $i$ assigned. But this is not correct because I could be left of some $i$ that could not be assigned to any $j$ (because of their $a_{ij}$ which could be not satisfied).

The brute force method, when I have to generate all subsets of $A$ and test each one, works for me ($k=8,n=3$) but very inefficient.

Asked By : Azzo

Answered By : j_random_hacker

This problem is NP-hard by reduction from Vertex Cover.

In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$. (Equivalently: Is it possible to kill every edge in $G$ by deleting at most $r$ vertices?)

First, partitioning $A$ into $s$ disjoint subsets is equivalent to assigning each element in $A$ exactly one of $s$ possible labels. The basic idea of the reduction is to create a label $S_j$ for each vertex $v_j$ in $V$, and to "allow" each edge to be assigned only one of the two labels corresponding to its endpoints, in the following sense: assigning an edge a corresponding label introduces no (genuine) constraint on what other edges can be assigned the same label, while assigning an edge to a non-corresponding label prevents any other edge being assigned the same label -- which of course has the effect of pushing up the number of distinct labels required.

To construct an instance $(A, a, s)$ of your problem from an instance $(G, r)$ of Vertex Cover:

1. Set $k$ to $|E|$, and create an element $(i, j)$ in $A$ for each edge $v_iv_j$ in $E$. (These pairs can be thought of as the integers $1, \dots, k$; any bijection between them will do.)
2. Set $a_{(b, c), d}$ to $|E|$ if $d=b$ or $d=c$; otherwise, set $a_{(b, c), d}$ to 1.
3. Set $s=r$.

If $(G, r)$ is a YES-instance of Vertex Cover, then it's easy to see that the just-constructed instance of your problem is also a YES-instance: just pick the labels $S_j$ corresponding to the vertices $v_j$ in any solution $U$, and for each edge $v_bv_c \in E$ assign the corresponding element $(b, c) \in A$ whichever one of the labels $S_b$ or $S_c$ was picked (choose arbitrarily if both labels were picked). This solution uses $s$ subsets, and is valid because the only $a_{ij}$ in force are those for corresponding labels, which have the (non-) effect of preventing more than $|E|$ edges being assigned the same label.

It remains to show that a YES-instance $X=(A, a, s)$ of your problem implies that the original $(G, r)$ is a YES-instance of Vertex Cover. This is slightly more complicated, since a valid solution $Y$ to $X$ may in general assign an edge $(i, j)$ a non-corresponding label $S_m$, i.e., $m \notin \{i, j\}$, meaning that we can't necessarily "read off" a valid vertex cover $U$ from a valid solution $Y$.

However, assigning a non-corresponding label has a high cost that severely limits the structure of the solution: whenever an edge $(i, j)$ is assigned such a label $S_m$, with $m \notin \{i, j\}$, the fact that $a_{(i, j), m} = 1$ ensures that it must be the only edge assigned this label. So, in any solution $Y$ containing such a non-correspondingly-labelled edge $(i, j) \mapsto S_m$, we could construct an alternative solution $Y'$ as follows:

1. Arbitrarily choose the new label $S_z$ for $(i, j)$ to be either $S_i$ or $S_j$.
2. Assign $(i, j)$ this new label. If this results in an invalid solution, it must be because exactly one other edge $(i', j')$, $z \notin \{i', j'\}$ had already been assigned the label $S_z$. In that case, set $(i, j) = (i', j')$ and go to step 1.

The above algorithm must terminate in one of two ways: either a new label $S_z$ is found that introduces no contradiction, or a complete cycle of vertices is found. In the former case, a valid new solution with $s-1$ sets is found, while in the latter case a valid new solution with $s$ sets is found; either way, we have constructed a valid new solution with at least one more edge assigned to a corresponding label. After repeating this entire process at most $|E|$ times, we will have produced a valid solution $Y''$ from which a solution to the original Vertex Cover problem can be read off.

This construction is clearly polynomial time, so it follows that your problem is NP-hard.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65233

 Ask a Question

 Download Related Notes/Documents