FPTAS for Holant problems with log-concave signatures

K He, Z Li, G Qiu, C Zhang - Proceedings of the 2025 Annual ACM-SIAM …, 2025 - SIAM
For an integer b≥ 0, ab-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 …

Dichotomy for Non-negative Valued Holant Problems on 3-Regular Bipartite Graphs

J Li, Y Huang, Y Zheng - Theory of Computing Systems, 2025 - Springer
Holant problems are an important framework to study counting problems. In the present
paper, we give a complexity dichotomy theorem for Holant problems on 3-regular bipartite …

The computational complexity of Holant problems on 3-regular graphs

P Yang, Y Huang, Z Fu - Theoretical Computer Science, 2024 - Elsevier
Holant problem is a framework to study counting problems, which is expressive enough to
contain Counting Graph Homomorphisms (# GH) and Counting Constraint Satisfaction …

P-time Algorithms for Typical# EO Problems

B Meng, J Wang, M Xia - arXiv preprint arXiv:2410.11557, 2024 - arxiv.org
We study the computational complexity of counting weighted Eulerian orientations, denoted
as# EO problems. We prove a complexity dichotomy theorem for# EO defined by a set of …

The Converse of the Real Orthogonal Holant Theorem

B Young - arXiv preprint arXiv:2409.06911, 2024 - arxiv.org
The Holant theorem is a powerful tool for studying the computational complexity of counting
problems in the Holant framework. Due to the great expressiveness of the Holant framework …

Local holographic transformations: tractability and hardness

P Yang, Z Fu - Frontiers of Computer Science, 2023 - Springer
Local holographic transformations were introduced by Cai et al., and local affine functions,
an extra tractable class, were derived by it in# CSP2. In the present paper, we not only …

Approximability of the complementarily symmetric Holant problems on cubic graphs

Y He, G Qiu, C Zhang - Theoretical Computer Science, 2023 - Elsevier
We study the approximability of boolean Holant problems with complementarily symmetric
constraint functions on cubic graphs. We identify a regime in which the problem admits an …

Eulerian orientations and Hadamard codes: A novel connection via counting

S Shao, Z Tang - arXiv preprint arXiv:2411.02612, 2024 - arxiv.org
We discover a novel connection between two classical mathematical notions, Eulerian
orientations and Hadamard codes by studying the counting problem of Eulerian orientations …

New planar P-time computable six-vertex models and a complete complexity classification

JY Cai, Z Fu, S Shao - Proceedings of the 2021 ACM-SIAM Symposium on …, 2021 - SIAM
We discover new P-time computable six-vertex models on planar graphs beyond
Kasteleyn's algorithm for counting planar perfect matchings.∗ We further prove that there are …

Beyond# CSP: A dichotomy for counting weighted Eulerian orientations with ARS

JY Cai, Z Fu, S Shao - Information and Computation, 2020 - Elsevier
We define and explore a notion of unique prime factorization for constraint functions, and
use this as a new tool to prove a complexity classification for counting weighted Eulerian …