Counting weighted independent sets beyond the permanent

DOI10.1137/20M1347747zbMATH Open1467.05124arXiv1909.03414MaRDI QIDQ4997141FDOQ4997141

Authors: Martin Dyer, Haiko Müller, Kristina Vušković, Mark Jerrum 

Publication date: 28 June 2021

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

Abstract: Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs, and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi (1988), Maffray and Reed (1999) and Lozin and Milanic (2008).

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

Recommendations

• Approximating the permanent of graphs with large factors
• Counting independent sets in graphs with bounded bipartite pathwidth
• scientific article; zbMATH DE number 1559584
• On counting perfect matchings in general graphs
• On Counting Independent Sets in Sparse Graphs

zbMATH Keywords

decompositionrandomized algorithmclaw-free graphcountingindependent setFPRASfully polynomial randomized approximation schemefork-free graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Computing well-covered vector spaces of graphs using modular decomposition
• Geometric bounds on the fastest mixing Markov chain
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Counting independent sets in graphs with bounded bipartite pathwidth

This page was built for publication: Counting weighted independent sets beyond the permanent

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