Counting weighted independent sets beyond the permanent
From MaRDI portal
(Redirected from Publication:4997141)
decompositionrandomized algorithmclaw-free graphcountingindependent setFPRASfully polynomial randomized approximation schemefork-free graph
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)
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).
Recommendations
Cites work
- scientific article; zbMATH DE number 3914376 (Why is no real title available?)
- scientific article; zbMATH DE number 1820633 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- A description of claw-free perfect 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
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A survey of the algorithmic aspects of modular decomposition
- A translation of Gallai's paper: `Transitiv orientierbare Graphen'
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
- Approximating the Permanent
- Characterizations of derived graphs
- Claw-free graphs. VII. Quasi-line graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Counting independent sets in graphs with bounded bipartite pathwidth
- Decomposition by clique separators
- Geometric algorithms and combinatorial optimization
- Graph Classes: A Survey
- Graph theory
- Line perfect graphs
- On counting perfect matchings in general graphs
- On maximal independent sets of vertices in claw-free graphs
- On minimal prime extensions of a four-vertex graph in a prime graph
- Paths, Trees, and Flowers
- Random generation of combinatorial structures from a uniform distribution
- Recognizing Berge graphs
- Recognizing claw-free perfect graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Solving the weighted stable set problem in claw-free graphs via decomposition
- The complexity of computing the permanent
- The relative complexity of approximate counting problems
- The roots of the independence polynomial of a clawfree graph
- The strong perfect graph theorem
- The structure of claw-free perfect graphs
- Transitiv orientierbare Graphen
Cited in
(6)- Computing well-covered vector spaces of graphs using modular decomposition
- Thick forests
- Geometric bounds on the fastest mixing Markov chain
- Glauber dynamics for the hard-core model on bounded-degree H-free graphs
- 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)
