4
$\begingroup$

I am trying to solve the following problem. Let $S$ be a set and $F \subset {S \choose k}$ that is $F$ is a subset of the set of all $k$-sets of $S$.

A set $M \subset F$ such that no two elements of $M$ intersect is called a solution for the problem.

I am looking for an algorithm $A$ that finds a solution to the above problem such that if the given solution is a set $M$ and the largest set that is a solution for the same instance is $M^*$ then

$\frac{|M|}{|M^*|} \geq \frac1{k}\qquad (1) $

The only algorithm I can see for the above problem is to pick an element $P$ from $F$, remove all the elements in $F$ that intersect with $P$ and continue.

However I am not able to analyze the above procedure to obtain the given bound (if even attainable).

Any hints on this problem?

2 Answers 2

3

This problem is usually called the unweighted set-packing problem. As a side-note, this problem is NP-complete; in fact, as I came to know only today (thanks, OP!), it is one of Karp's gang of 21!

Here's a simple proof that the heuristic sketched in the question gives a set $M$ that is at most a factor $k$ from the optimum, call this $M^*$. Create a bipartite graph with the sets in $M$ as the left vertices, and the sets in $M^*$ as the right vertices. Add an edge between $A \in M$ and $B \in M^*$ iff $A$ intersects $B$. Here are some basic observations:

  • Every right vertex has at least one left neighbor. Otherwise, we could add this set safely to $M$ to get a bigger family, contradicting the maximality of $M$.
  • Every left vertex has at most $k$ right neighbors. Otherwise two of the right neighbors will be forced to "share" a common element, contradicting the assumption that $M^*$ is a disjoint family of sets.

Putting these two together, you should be able to deduce that $|M^*| \leq |M|/k$. (Note that we do not have strict inequality.) Btw, the set-packing problem for the case $k=2$ is the well-known maximum matching problem. If you have seen matchings before, I encourage you to work out the proof for this specific case; it's quite illuminating.

This bound is tight, as seen from the following example: let $S$ be the set of $k^2$ points arranged as a $k \times k$ grid. Define $M$ to be just the leftmost column. Define $M^*$ to be the family of $k$ rows, each of which contains $k$ points. Take $F$ to be $M \cup M^*$. Clearly $|M| =1$ and $|M^*|=k$.

Better heuristics. Apparently, better local-heuristics heuristics are known for this problem, achieving a factor $k/2+\epsilon$ approximation. See e.g.: "Approximating Discrete Collections via Local Improvements" by Halldorsson.

0

What is wrong with partitioning $S$ into $k$ element disjoint sets?

  • 0
    Ross, that doesn't work since the $k$-sets in $M$ are required to be picked from $F$.2011-07-23