Counting independent sets in graphs with bounded bipartite pathwidth

DOI10.1002/rsa.21003zbMath1522.05202MaRDI QIDQ6074656

Catherine Greenhill, Haiko Müller, Martin Dyer

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://eprints.whiterose.ac.uk/174580/1/1812.03195v4.pdf

zbMATH Keywords

independent sets; pathwidth; approximate counting

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C30: Enumeration in graph theory

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorics and complexity of partition functions
• Geometric bounds for eigenvalues of Markov chains
• The roots of the independence polynomial of a clawfree graph
• Graph minors. I. Excluding a forest
• Random generation of combinatorial structures from a uniform distribution
• On maximal independent sets of vertices in claw-free graphs
• A partial k-arboretum of graphs with bounded treewidth
• Comparison theorems for reversible Markov chains
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Counting independent sets in cocomparability graphs
• On the numbers of independent \(k\)-sets in a claw free graph
• The relative complexity of approximate counting problems
• Counting independent sets in graphs with bounded bipartite pathwidth
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Counting independent sets up to the tree threshold
• Unimodality, log-concavity, real-rootedness and beyond
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Reconfiguring Independent Sets in Claw-Free Graphs
• Approximating the Permanent
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Shorter Notes: The Roots of a Polynomial Vary Continuously as a Function of the Coefficients
• Graph Classes: A Survey
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Computing the Partition Function of a Polynomial on the Boolean Cube
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• On the Switch Markov Chain for Perfect Matchings
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• On Markov Chains for Independent Sets
• Counting Matchings of Size k Is $\sharp$ W[1-Hard]
• Paths, Trees, and Flowers
• Characterizations of derived graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth