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?
Asked By : Erel Segal-Halevi
Answered By : David Richerby
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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18736
0 comments:
Post a Comment
Let us know your responses and feedback