7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It can probably help somebody to answer you question if you give a link to the proof of #P-completeness for general case. $\endgroup$ Mar 18, 2010 at 23:48
  • $\begingroup$ The proof for the general case is here: cc.gatech.edu/~mihail/www-papers/soda92.pdf $\endgroup$ Mar 19, 2010 at 1:35
  • $\begingroup$ 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. $\endgroup$
    – bandini
    Mar 31, 2010 at 21:42

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2010 at 2:45
  • $\begingroup$ 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). $\endgroup$
    – Igor Pak
    Mar 19, 2010 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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