Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Ross, that doesn't work since the $k$-sets in $M$ are required to be picked from $F$. –  Srivatsan Jul 23 '11 at 23:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.