Abstract This article establishes a unified complexity framework for tensor network contraction—a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph’s separator properties, we develop edge separator theorems for finite element graphs and $H$-minor-free graphs (excluding any simple graph $H$ as a minor), and present sub-exponential contraction algorithms for these graph classes. These algorithms, along with the algorithm for contraction on planar graphs are further accelerated by transforming each high-dimensional tensor into a series of low-dimensional tensors. Two methods are involved in this process respectively—the “adder” gadget that can equivalently represent any Boolean symmetric tensor, and the CANDECOMP/PARAFAC decomposition that can express any tensor as vector product sums. In particular, we prove corresponding lower bounds under #ETH, establishing near-optimality of our algorithms. Also, we present a treewidth-parameterized contraction algorithm, and therefore develop a fine-grained dichotomy for tensor network contraction, contingent on the Hadwiger number.

Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article.

In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as #EO. This problem is considered a pivotal scenario in the complexity classification for Holant, a counting framework of great significance. Our results consist of three parts. First, we prove a complexity dichotomy theorem for #EO defined by a set of binary and quaternary signatures, which generalizes the previous dichotomy for the six-vertex model. Second, we prove a dichotomy for #EO defined by a set of so-called pure signatures, which possess the closure property under gadget construction. Finally, we present a polynomial-time algorithm for #EO defined by specific rebalancing signatures, which extends the algorithm for pure signatures to a broader range of problems, including #EO defined by non-pure signatures such as f_40. We also construct a signature f_56 that is not rebalancing, and whether #EO(f_56) is computable in polynomial time remains open.

In this work, we introduce the concept of permutable matchgate signatures and leverage it to establish dichotomy theorems for #CSP and #R_D-CSP (D ≥ 3) on planar graphs without the variable ordering restriction. We also present a complete characterization of permutable matchgate signatures and their relationship to symmetric signatures. Besides, we give a sufficient and necessary condition for determining whether a matchgate signature retains its property under a certain variable permutation, which can be checked in polynomial time. In addition, we prove a dichotomy for Pl-#R_D-CSP (D ≥ 3), where the variable ordering restriction exists.