An LP Algorithm for Counting Eulerian Orientations Through the Lens of Quasi-polymorphism

Abstract

The weighted Eulerian orientation counting problem ($\#\mathrm{EO}$) plays a key role in the complexity classification program for Holant problems. A recent result established an ${\mathrm{FP}}^{\mathrm{NP}}$ versus $\#\mathrm{P}$-hard dichotomy for $\#\mathrm{EO}$ problems. The tractable side of this dichotomy can be characterized by functions admitting quasi-polymorphisms of the ternary XOR operation, leaving open whether these cases on the ${\mathrm{FP}}^{\mathrm{NP}}$ side are in fact in FP. In this paper, we settle this question by giving a polynomial-time algorithm for all cases on the ${\mathrm{FP}}^{\mathrm{NP}}$ side. Consequently, we obtain a complete FP versus $\#\mathrm{P}$ dichotomy for counting weighted Eulerian orientations, and further for complex-valued Holant problems with an odd-arity signature. Our algorithm is based on a linear programming relaxation, but we use it in a nonstandard way. Instead of proving that the relaxation is integral and solving the problem directly from an optimal LP solution, we use the relaxation as a structural tool to lift the quasi-polymorphism condition to an ordinary polymorphism condition. This reveals an affine local structure of the constraint functions, which leads to tractability.

14 pages

Topics & keywords