An LP Algorithm for Counting Eulerian Orientations Through the Lens of Promise PolymorphismsResearch Paper
A finite graph can be oriented so that each vertex has equally many incoming and outgoing edges precisely when every vertex has even degree. Counting the orientations subject to local restrictions is a different computational problem. A vertex can favor some local arrangements, forbid others, or attach complex weights to them. The resulting weighted sum…