Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
    
Thanks for pointing to your results. Could you provide some more details about mapping the number of orientations without weight? I am not quite sure whether hardness of computing unweighted version could follow directly from the weighted version. –  Sangxia Huang Mar 19 '10 at 2:45
    
The bijection is well explained on my paper (see link above). The problem with saddle vertices is that you have two ways to "resolve" them. These ways correspond to either taking or not taking the edge - so to count orientations without weighting you need to decide, say, to never take such edges in your subsets. But really, I don't mean to suggest I know the solution or have worked with the unweighted stat sum - this is just an idea (as requested). –  Igor Pak Mar 19 '10 at 6:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.