A Simple FPTAS for Counting Edge Covers
arXiv:1309.6115 · doi:10.1137/1.9781611973402.25
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].
To appear in SODA 2014
References in corpus (5)
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- The computational hardness of counting in two-spin models on d-regular graphs
- Approximating Holant problems by winding
- A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
- Approximate Counting via Correlation Decay on Planar Graphs