A simple FPTAS for counting edge covers

DOI10.1137/1.9781611973402.25MaRDI QIDQ5383984zbMATH OpenOpenAlexFDO

Authors Jing-Cheng Liu, Pinyan Lu, Chengyu Lin

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: An edge cover of a graph is a set of edges such that every vertex has at least an adjacent edge in it. Previously, approximation algorithm for counting edge covers is only known for 3 regular graphs and it is randomized. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of edge covers for any graph. Our main technique is correlation decay, which is a powerful tool to design FPTAS for counting problems. In order to get FPTAS for general graphs without degree bound, we make use of a stronger notion called computationally efficient correlation decay, which is introduced in [Li, Lu, Yin SODA 2012].

Recommendations

• FPTAS for counting weighted edge covers
• Approximate counting via correlation decay in spin systems
• FPTAS for counting monotone CNF
• Approximate counting via correlation decay on planar graphs
• Sampling Edge Covers in 3-Regular Graphs

Cited in

(14)

• The complexity of Bayesian networks specified by propositional and relational languages
• Counting hypergraph matchings up to uniqueness threshold
• Zero-freeness and approximation of real Boolean Holant problems
• Some applications of Wagner's weighted subgraph counting polynomial
• FPTAS for counting weighted edge covers
• Sampling Edge Covers in 3-Regular Graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
• On the Complexity of Holant Problems
• Absence of zeros implies strong spatial mixing
• Spectral independence via stability and applications to Holant-type problems
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• Sink-free orientations: a local sampler with applications
• An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

This page was built for publication: A simple FPTAS for counting edge covers

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