A Simple FPTAS for Counting Edge Covers

Chengyu Lin, Jingcheng Liu, Pinyan Lu

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].
BibTeX
@inproceedings{lin2014simple,
  author = {Chengyu Lin and Jingcheng Liu and Pinyan Lu},
  title = {{A Simple FPTAS for Counting Edge Covers}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.25},
}

Loading related content...

Figure