Counting Weighted Independent Sets beyond the Permanent

DOI10.1137/20M1347747zbMath1467.05124arXiv1909.03414MaRDI QIDQ4997141

Haiko Müller, Kristina Vušković, Martin Dyer, Mark R. Jerrum

Publication date: 28 June 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

decompositioncountingrandomized algorithmindependent setclaw-free graphFPRASfully polynomial randomized approximation schemefork-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items

Computing well-covered vector spaces of graphs using modular decomposition, Geometric bounds on the fastest mixing Markov chain

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• The complexity of computing the permanent
• On minimal prime extensions of a four-vertex graph in a prime graph
• The strong perfect graph theorem
• The roots of the independence polynomial of a clawfree graph
• Decomposition by clique separators
• Random generation of combinatorial structures from a uniform distribution
• Recognizing claw-free perfect graphs
• On maximal independent sets of vertices in claw-free graphs
• Geometric algorithms and combinatorial optimization
• A description of claw-free perfect graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The relative complexity of approximate counting problems
• Claw-free graphs. VII. Quasi-line graphs
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• On counting perfect matchings in general graphs
• Counting independent sets in graphs with bounded bipartite pathwidth
• Recognizing Berge graphs
• Graph Theory
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Line perfect graphs
• Graph Classes: A Survey
• Paths, Trees, and Flowers
• The Structure of Claw‐Free Perfect Graphs
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• Transitiv orientierbare Graphen
• Characterizations of derived graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph