Exponential Time Complexity of Weighted Counting of Independent Sets

DOI10.1007/978-3-642-17493-3_18MaRDI QIDQ3058702zbMATH OpenOpenAlexFDO

Authors Christian Hoffmann

Publication date 7 December 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1146

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 eq 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.

Recommendations

• Faster exponential-time algorithms for approximately counting independent sets
• A Worst-Case Time Upper Bound for Counting the Number of Independent Sets
• The relative exponential time complexity of approximate counting satisfying assignments
• The relative exponential time complexity of approximate counting satisfying assignments
• Counting weighted independent sets beyond the permanent
• scientific article; zbMATH DE number 2119675
• Finding Large Independent Sets in Polynomial Expected Time
• scientific article; zbMATH DE number 1962840
• Exponential-time approximation of weighted set cover
• On the complexity of approximating the independent set problem

Cites work

• A bottom-up method and fast algorithms for Max Independent Set
• A fine-grained analysis of a simple independent set algorithm
• A measure \& conquer approach for the analysis of exact algorithms
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• A note on the Glauber dynamics for sampling independent sets
• A two-variable interlace polynomial
• Algorithms for maximum independent sets
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Chromatic Roots are Dense in the Whole Complex Plane
• Clique polynomials and independent set polynomials of graphs
• Counting independent sets up to the tree threshold
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559584 (Why is no real title available?)
• scientific article; zbMATH DE number 2119675 (Why is no real title available?)
• Introduction to algorithms
• On Markov Chains for Independent Sets
• On the Complexity of the Interlace Polynomial
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Enumeration and Reliability Problems
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Which problems have strongly exponential complexity?

Cited in

(4)

• Faster exponential-time algorithms for approximately counting independent sets
• The exponential time complexity of computing the probability that a graph is connected
• Counting solutions to polynomial systems via reductions
• Lower bounds on dynamic programming for maximum weight independent set

This page was built for publication: Exponential Time Complexity of Weighted Counting of Independent Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058702)