FPTAS for Holant Problems with Log-Concave Signatures
<|reference_start|>FPTAS for Holant Problems with Log-Concave Signatures: For an integer $b\ge 0$, a $b$-matching in a graph $G=(V,E)$ is a set $S\subseteq E$ such that each vertex $v\in 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).<|reference_end|>
@article{he2024fptas,
    title={FPTAS for Holant Problems with Log-Concave Signatures},
    author={Kun He, Zhidan Li, Guoliang Qiu and Chihao Zhang},
    journal={arXiv preprint arXiv:2407.04989},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04989},
    primaryClass={cs.DS}
}