1
$\begingroup$

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.

$\endgroup$

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.