A Simple FPTAS for Counting Edge Covers

Chengyu Lin, Jingcheng Liu, Pinyan Lu

Introduction

In graph theory, an edge cover of a graph $G = (V, E)$ is a subset of edges $E' \subseteq E$ such that every vertex in $V$ is incident to at least one edge in $E'$. While finding a minimum-sized edge cover is a classic problem solvable in polynomial time, counting the total number of edge covers is significantly more challenging. This task is known to be #P-complete, placing it in a complexity class where exact solutions are computationally intractable for large-scale instances.

To address this, researchers have sought a Fully Polynomial-Time Approximation Scheme (FPTAS)—an algorithm that provides an estimate within a $(1 \pm \epsilon)$ factor of the true count in time polynomial to the graph size and $1/\epsilon$. Previously, such schemes were limited to specific graph classes (like 3-regular graphs) or relied on randomized sampling (FPRAS). A recent breakthrough by researchers from Shanghai Jiao Tong University and Microsoft Research presents the first deterministic FPTAS for counting edge covers in any general graph.

The Correlation Decay Framework

The proposed algorithm is built upon the principle of Correlation Decay. This approach estimates the total count of edge covers by calculating the marginal probability that a given edge is included in a randomly selected cover.

The fundamental assumption of correlation decay is that the status of an edge (whether it belongs to a cover) is primarily influenced by its immediate local neighborhood. As one moves further away from the edge in the graph, this influence "decays." This allows the algorithm to approximate global properties by performing local computations on a "computation tree" rooted at the edge of interest.

Overcoming the Degree-Bound Hurdle

Traditionally, correlation decay algorithms struggle with high-degree vertices because the local neighborhood grows exponentially, making computation expensive. The key innovation in this work is the use of computationally efficient correlation decay. The authors demonstrate a counter-intuitive property: in the context of edge covers, high-degree vertices actually accelerate the decay of correlation. This "trade-off" ensures that even as the neighborhood expands, the required depth of the search remains manageable, allowing the algorithm to handle graphs of any degree while maintaining polynomial runtime.

The Recursive Algorithm

Despite the sophisticated mathematical proofs underpinning it, the resulting algorithm is remarkably simple. It employs a recursive calculation on a truncated tree structure derived from the original graph.

Figure 5: Illustration of the graph transformations used in the recursive counting algorithm. (a) Original graph G, (b) and (c) represent modified structures used to build the recurrence relation.

By breaking down the graph into smaller components—as illustrated in the recursive steps shown above—the algorithm builds up an estimate of the total count. Specifically, for any graph $G$ and error tolerance $\epsilon$, the algorithm outputs a value $\hat{N}$ such that $(1-\epsilon)N \le \hat{N} \le (1+\epsilon)N$, where $N$ is the true number of edge covers. The total running time is $O(n^2 \cdot 6^L)$, where $L$ is a logarithmic depth related to the desired precision.

Beyond its practical algorithmic contributions, the paper establishes a deep link between graph theory and Boolean logic. The authors show that counting edge covers is mathematically equivalent to counting satisfying assignments for Read-Twice Monotone CNF formulas (Rtw-Mon-CNF). This connection suggests that the techniques developed here might have broader applications in the field of approximate counting for logical formulas.

Conclusion and Future Directions

This work provides a definitive answer for the deterministic approximate counting of edge covers in general graphs. However, several open questions remain. The current method focuses on the unweighted count. Extending this to weighted edge covers (the partition function $Z_G(\lambda)$) is a natural next step. While the authors suggest their approach may work for weights $\lambda > 4/9$, the behavior for smaller weights—and the potential existence of a "phase transition" where approximation becomes impossible—remains an area for future exploration. Additionally, extending these results to more complex logical structures, such as Read-Thrice formulas, presents a significant ongoing challenge in theoretical computer science.

Summary updated

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},
}
Figure