# Counting Eulerian Orientation in a 4-regular undirected graph

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-edges.

It is known that counting Eulerian orientation in undirected graphs are #P-complete. We have tried to construct some gadget to reduce the general case to 4-regular case, but did not succeed. Any idea about that?

Thank you.

-
It can probably help somebody to answer you question if you give a link to the proof of #P-completeness for general case. – Grigory Yaroslavtsev Mar 18 '10 at 23:48
The proof for the general case is here: cc.gatech.edu/~mihail/www-papers/soda92.pdf – Sangxia Huang Mar 19 '10 at 1:35
Here are two ideas that spring to mind. 1) Reduce from degree 3 bipartite matching icsi.berkeley.edu/~luby/PAPERS/permfactor.ps. Applying the reduction from Mihail & Winkler's paper to a degree 3 bipartite graph gives a graph that is almost 4-regular. Maybe there is some way to adapt it by adding more vertices between A and s, and B and t. 2) Use a gadget like the one used in cs.rhul.ac.uk/home/paidi/papers/CreedJDA.pdf to simulate each vertex with degree > 4. – bandini Mar 31 '10 at 21:42

Let $G$ be a planar graph. Consider a medial graph $H=H(G)$, which is always $4$-regular. Often, problems about $G$ can be translated into the language of $H$ and vice versa. Closer to your question, the number of Eulerian orientations of $H$ is "almost" an evaluation of the Tutte polynomial: $$(\ast) \qquad \sum_{O} 2^{\alpha(O)} = 2\cdot T_G(3,3),$$ where the summation is over all Eulerian orientations $O$ of $H$, and $\alpha(O)$ is the number of saddle vertices (i.e. where the orientation is in-out-in-out in cyclic order). This is due to Las Vergnas (JCTB 45, 1988). My former student Mike Korn and I generalized this here.
Of course, evaluations of the Tutte polynomial of planar graphs, including at ($3,3)$, are pretty much all #P-hard (with a few known exceptions), see D.J.A. Welsh, Complexity: knots, colourings and counting book (1993). Now, there is a bijective proof of $(\ast)$, which maps orientations $O$ into certain subsets of edges of $G$. It is possible that when you map the number of orientations without weight you still get a hard-to-compute stat. sum, which will prove what you want.