| Abstract: |
In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as #EO. This problem is considered as a pivotal scenario in the complexity classification for Holant, a counting framework of great significance. Our result consists of three parts. Firstly, 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. Secondly, we prove a dichotomy for #EO defined by a set of so-called pure signatures, which possesses the closure property under gadget construction. Finally, we present a polynomial-time algorithm for #EO problems 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 f40. We also construct a signature f56 that is not rebalancing, and whether #EO(f56) is computable in polynomial time remains unsettled. |
下载中心
会议室预定
电子邮箱