FPTAS for Holant Problems with Log-Concave Signatures

For an integer ≥ 0, a -matching in a graph = ( , ) is a set ⊆ such that each vertex ∈ is incident to at most edges in . We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of -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).

However, when becomes larger, many good properties of matchings break down, posing new challenges in algorithm design. The problem was perhaps first studied in the work of [HLZ16], in which the rapid mixing of a particular Markov chain was established for ≤ 7 using the method of canonical paths, and the chain can be used to uniformly sample from -matchings. Recently, using a simple and neat coupling argument, among many other things, the spectral independence property for the uniform distribution of -matching was established in [CG24], which implies the rapid mixing of Glauber dynamics for sampling -matchings. As a result, one obtains a fully polynomial-time randomized approximation scheme (FPRAS) for counting -matchings for any ≥ 0.

In this work, we focus on deterministic approximate counting algorithms. There are a few popular techniques for designing deterministic algorithms for Holant-type problems, including the method of correlation decay [BGK + 07, LWZ14, LLL14, LLZ14] and polynomial interpolation [GLLZ21, BCW22, CFF + 22], which result in fully polynomial-time approximation schemes (FPTAS) for counting problems. Both the methods of correlation decay and polynomial interpolation are successful for counting matchings and many other Holant problems.

However, for larger than 1, the problem of -matching resists both methods: the problem lacks a concise and lossless recursion for computing marginals necessary to apply the correlation decay technique, and it is challenging to determine the location of zeros for the partition function in order to use the polynomial interpolation method (in particular, the -stable property in [GLLZ21] for local polynomials does not hold for a general ).

We design an FPTAS for -matching and more generally Holant problems with log-concave signature by developing the method of linear programming, invented by Moitra in [Moi19], which was previously only applied to counting problems on hypergraphs under Lovász-local-lemma-type conditions [Moi19, GLLZ19, GGGY21, JPV22, WY24]. We will summarize our main results in Section 1.1 and explain our technical contributions in Section 1.2, respectively.

-matchings Given a graph = ( , ), recall that = ∈ : is incident to is the collection of all edges incident to for each ∈ . For a vector = ∈ ∈ ℕ >0 , we say that ⊆ is a -matching of if | ∩ | ≤ for every ∈ . Note that when = for every ∈ we obtain the typical -matchings.

Given any positive integers Δ and , there exists an FPTAS for counting the number of -matchings for any graph with maximum degree Δ and any = ∈ satisfying ≤ for every ∈ .

Closely to -matchings, another problem is counting -edge covers. For an edge subset ⊆ , we say that is a -edge cover of if | ∩ | ≥ for every ∈ . Note that for every -edge cover , its complement forms a ′ -matching where ′ = ′ ∈ is defined as ′ = deg ( ) -. Then one can easily derive the following result for counting -edge covers as an immediate corollary of counting ′ -matchings.

Corollary 2 ( -edge covers). Given any positive integers Δ and ≤ Δ, there exists an FPTAS for counting the number of -edge covers for any graph with maximum degree Δ and any = ∈ satisfying ≥ for every ∈ .

Holant problems with log-concave signatures Beyond counting the number of -matchings, we also consider the family of Holant problems with Boolean domain symmetric log-concave signatures. Recall