Equivalence of independent set and set packing

Question

According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent.

The Independent Set search problem is: given a graph $G(V,E)$ and an integer $n$, find $n$ vertices no two of which are adjacent.

The Set Packing search problem is: given a finite collection $C$ of finite sets and an integer $n$, find $n$ sets that are pairwise disjoint.

I think they are equivalent based on the following bidirectional reduction:

→: Given an independent set problem on a graph $G(V,E)$, create a collection of $C$ of sets, where for each vertex $v \in V$ there is a set $S_v \in C$ containing all edges adjacent to $v$. Now, every set packing in $C$ corresponds to a set of vertices no two of which have an edge in common, i.e., this is an independent set in $G$ of the same size.

←: Given a set packing problem on a collection $C$, create a graph $G(V,E)$ where for every set $S \in C$ there is a vertex $v_S \in V$, and there is an edge between $v_{S_1}$ and $v_{S_2}$ iff the sets $S_1$ and $S_2$ intersect. Now, every independent vertex set in $G$ corresponds to a set of sets from $C$ no two of which intersect, i.e., this is a set packing in $C$ of the same size.

My question is: is my reduction correct? If so, are these problem equivalent? Is it possible to use approximation algorithms for one problem on the other problem?

Answer 1

The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems.

You've demonstrated what's known as a parsimonious reduction between the two problems. Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property that problem A has a solution if, and only if, problem B has a solution. For example, when you reduce 3SAT to 3-Colourability, you produce a graph $G$ that is 3-colourable if, and only if, the original formula $\varphi$ is satisfiable. However, if $\varphi$ has $N$ variables, the number of satisfying assignments could be anything between zero and $2^N$, inclusive, whereas the number of 3-colourings of any graph is a multiple of six because of permutations of the set of colours.

The point about parsimonious reductions is that they're one-to-one. Your reduction sets up a bijection between solutions of the independent set problem and solutions of the corresponding set packing problem. Parsimonious reductions are useful because they preserve optimization and (approximate) counting versions of the problem. So your reduction also shows that the problem of finding the biggest independent set is as hard as finding the set packing using the most sets and that the problem of counting all the independent sets is as hard as to counting all the set packings.

There is a wider class of reductions that also preserve counting and approximate counting. These are the approximation-preserving reductions of Dyer et al. [1]. These are oracle reductions and relax the one-to-one requirement of parsimonious reductions to what is, essentially, "If you know (an approximation of) one, you can easily compute (an approximation of) the other." In particular, AP reductions can easily deal with the factor of $q!$ that's inherent in any reduction to the $q$-colouring problem. As the name suggests, AP reductions preserve approximability, in the sense that, if there's an AP-reduction from A to B and there's an FPRAS for B, then there's an FPRAS for A, too.

---

[1] Dyer, Goldberg, Greenhill, Jerrum. The relative complexity of approximate counting problems. Algorithmica 38(3):471–500, 2003. DOI; free PDF

Answer 2

Both problems are NP-complete, so even without checking your reductions, they are equivalent in that sense.

However, your reduction does seem okay. Technically for approximation results you want to verify some additional properties of the reduction (not necessarily hard to do, e.g. in this case PTAS reductions are of interest). You also have to talk about the optimization versions of the problems, rather than the decision versions (i.e. asking for the max/min answer, rather than for the existence of one of a certain size or more/less).

In fact it is already known that they do have related approximability. Unfortunately, they generally don't have good approximations. For both problems (and Maximum Clique, which is also closely related) there are inapproximability results, the primary being inapproximability with $|V|^{1-\varepsilon}$ for any $\varepsilon > 0$ (unless NP=ZPP), which is about as bad as it gets.

If you're looking at restricted classes of graphs, you might be able to find something interesting. For further reading, I refer you to the inestimably useful compendium of Viggo Kann:

1. Max Set Packing
2. Max Independent Set
3. Max Clique