11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Check whether the edit corresponds to the question you want to ask. Also, where does $a_\text{max}$ come from? Is that a fixed constant (not part of the input, but fixed for all time), or is it part of the input? Finally, are you looking for a practical solution? or are you looking for the theoretical complexity of this problem? If the former, have you tried using integer linear programming? $\endgroup$ – D.W. Nov 1 '16 at 16:36
10
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your help. Do you have any idea how can one solve (approximatively) this problem? (Like, for example, can I use techniques for the vertex cover problem to solve it?) I tried some greedy approach but, sometimes, it fails to output a feasible solution. (The way I choose the $S_j$ makes the greedy approach fails where a solution could exist.) $\endgroup$ – drzbir Nov 1 '16 at 16:27
  • $\begingroup$ Well, it's expected that a greedy approach will sometimes fail to output a feasible solution, since if it always did, you would be solving an NP-hard problem in poly-time ;-) Remember that it's not necessarily wrong if it can't find a solution: it may well be that no feasible solution exists. $\endgroup$ – j_random_hacker Nov 1 '16 at 16:34
  • $\begingroup$ Regarding solution techniques, one that I like is called beam search. This is basically a kind of branch-and-bound that "forgets" sufficiently bad partial solutions in order to limit its memory usage. (B&B is itself a very good approach, and sometimes solves problems quickly, and it's slightly simpler than beam search so it's worth a shot -- but since it's an exact method, it can of course take millennia on some instances.) $\endgroup$ – j_random_hacker Nov 1 '16 at 16:36
  • $\begingroup$ (All of the below applies also to beam search as well as B&B.) B&B is a very general technique. The key thing with it is to exploit the specifics of the problem to organise the decisions you make so that, as much as possible, bad decisions (that is, decisions that do not lead to feasible solutions) are made early in the search tree. (These decisions will be made somewhere, and each level deeper that they get made doubles the number of times that they get made.) For your problem, I would suggest first ranking the elements in $A$ in decreasing order of "badness", where ... $\endgroup$ – j_random_hacker Nov 1 '16 at 16:44
  • $\begingroup$ ... the badness of element $i$ could be, e.g., the minimum of $a_{ij}$ over all $j$, breaking ties by second-minimum, then third-minimum, etc. Roughly speaking, the "worst" element will be the element that most severely constrains any set that it is added to. At each node at depth $d$ in the search tree, you will have a partial solution in which the first (and thus "worst") $d$ elements have already been assigned to sets; you will need to choose which of the $n$ sets to assign the $(d+1)$th element to: that is, you'll need up to $n$ recursive calls. ("Up to" because hopefully we have, ... $\endgroup$ – j_random_hacker Nov 1 '16 at 16:53

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.