Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations?

An Eulerian orientaiton of an (undirected simple) graph $G$ is an orientation of $G$ such that every vertex has in-degree equal to out-degree. Obviously, a graph must be an even regular graph to admit an Eulerian orientation. Also, one can find an Eulerian orientation of an even regular graph by taking a directed Euler tour and orienting the edges in the direction of the tour.

The problem of counting Eulerian orientations of a 4-regular graph is studied in graph polynomials context [equivalent to evaluating the Tutte polynomial at the point (0, -2)], flow theory (equivalent to counting the number of maximum flows around a network) and in statistical physics (ice-type models). The counting problem is hard (#P-complete), but there are efficent approximation algorithms.

Naturally, listing all Euler orienations is hard. I have a problem which could be solved if we have the list of all Eulerian orienations (there is a one-one map from a set of objects I study to the set of Eulerian orienations of a fixed graph $G$). If it matters, we know that (i) $G$ can be decomposed into cycles of length divisible by three and (ii) $G$ is (diamond,$K_4$)-free.

I wonder whether there is a subclass of regular graphs in which the listing problem is polynomial time solvable. I would expect this class to be small (but it should be non-trivial to be of interest).

Is there a paper that deal with listing Eulerian orientaitons?

Thank you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.