FPTAS for Holant Problems with Log-Concave Signatures

For an integer b≥ 0, a b-matching in a graph $G=(V,E)$ is a set S⊆ E such that each vertex v∈ V is incident to at most b edges in S. We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of b-matchings in graphs with bounded degrees. Our FPTAS also applies to a broader family of counting problems, namely Holant problems with log-concave signatures. Our algorithm is based on Moitra's linear programming approach (JACM'19). Using a novel construction called the extended coupling tree, we derandomize the coupling designed by Chen and Gu (SODA'24).