Computer Science – Computational Complexity
Scientific paper
2010-07-07
Computer Science
Computational Complexity
Introduction revised, differences between versions of counting independent sets stated more precisely, minor improvements. 14
Scientific paper
We consider weighted counting of independent sets using a rational weight x: Given a graph with n vertices, count its independent sets such that each set of size k contributes x^k. This is equivalent to computation of the partition function of the lattice gas with hard-core self-repulsion and hard-core pair interaction. We show the following conditional lower bounds: If counting the satisfying assignments of a 3-CNF formula in n variables (#3SAT) needs time 2^{\Omega(n)} (i.e. there is a c>0 such that no algorithm can solve #3SAT in time 2^{cn}), counting the independent sets of size n/3 of an n-vertex graph needs time 2^{\Omega(n)} and weighted counting of independent sets needs time 2^{\Omega(n/log^3 n)} for all rational weights x\neq 0. We have two technical ingredients: The first is a reduction from 3SAT to independent sets that preserves the number of solutions and increases the instance size only by a constant factor. Second, we devise a combination of vertex cloning and path addition. This graph transformation allows us to adapt a recent technique by Dell, Husfeldt, and Wahlen which enables interpolation by a family of reductions, each of which increases the instance size only polylogarithmically.
No associations
LandOfFree
Exponential Time Complexity of Weighted Counting of Independent Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exponential Time Complexity of Weighted Counting of Independent Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential Time Complexity of Weighted Counting of Independent Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345534