P-time Algorithms for Typical #EO Problems

In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as #$\mathsf{\text{EO}}$. This problem is considered a pivotal scenario in the complexity classification for $\mathsf{\text{Holant}}$, a counting framework of great significance. Our results consist of three parts. First, we prove a complexity dichotomy theorem for #$\mathsf{\text{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 #$\mathsf{\text{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 #$\mathsf{\text{EO}}$ defined by specific rebalancing signatures, which extends the algorithm for pure signatures to a broader range of problems, including #$\mathsf{\text{EO}}$ defined by non-pure signatures such as $f_{40}$. We also construct a signature $f_{56}$ that is not rebalancing, and whether $\mathrm{\#}\mathsf{\text{EO}}(f_{56})$ is computable in polynomial time remains open.