Faster exponential-time algorithms for approximately counting independent sets

DOI10.1016/J.TCS.2021.09.009MaRDI QIDQ2235762zbMATH OpenOpenAlexWikidataFDO

Authors Leslie Ann Goldberg, John Lapinskas, David Richerby

Publication date 21 October 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximate countingexponential algorithmsindependent sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Exponential Time Complexity of Weighted Counting of Independent Sets
• A Worst-Case Time Upper Bound for Counting the Number of Independent Sets
• Finding Large Independent Sets in Polynomial Expected Time
• scientific article; zbMATH DE number 1962840
• On the complexity of approximating the independent set problem
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• On the complexity of approximating the independent set problem (extended abstract)
• Fast algorithms for max independent set
• Graph-Theoretic Concepts in Computer Science
• Exact algorithms for maximum independent set

Cites work

• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithm 457: finding all cliques of an undirected graph
• Algorithms for #BIS-hard problems on expander graphs
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Computational complexity of counting problems on 3-regular planar graphs
• Counting independent sets up to the tree threshold
• Counting models for 2SAT and 3SAT formulae
• Counting the number of solutions for instances of satisfiability
• Exact exponential algorithms.
• Faster graph coloring in polynomial space
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• FPTAS for \#BIS with degree bounds on one side
• scientific article; zbMATH DE number 2090009 (Why is no real title available?)
• Matchings and walks in graphs
• Number of models and satisfiability of sets of clauses
• Spatial mixing and the connective constant: optimal bounds
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• The relative complexity of approximate counting problems

Cited in

(7)

• A graph polynomial for independent sets of bipartite graphs
• FPTAS for \#BIS with degree bounds on one side
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Irredundant Set Faster Than O(2 n )
• scientific article; zbMATH DE number 1559584 (Why is no real title available?)
• Approximately counting independent sets in bipartite graphs via graph containers
• A spectral approach to approximately counting independent sets in dense bipartite graphs

This page was built for publication: Faster exponential-time algorithms for approximately counting independent sets

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