Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem?

It seems like there should be a relatively straightforward approach, but a construction of the optimization problem isn't obvious to me.

  • 2
    $\begingroup$ Something's wrong here; acyclic graphs don't have a cycle of any kind, and thus not a Eulerian one either. Other than that, sure you can do it with LP (LP is P-complete, ILP is NP-complete), but why would you? $\endgroup$ – G. Bach May 18 '16 at 13:40
  • $\begingroup$ @G.Bach it's more about the interest in a construction than any kind of practicality, but yes, just edited the question. $\endgroup$ – Guillermo Angeris May 18 '16 at 15:38
  • 1
    $\begingroup$ The answer to your question, as @G. Bach said: yes. Maybe you should reformulate your question so that it asks for a reduction, instead of just bein a yes/no question. Of course, it is appreciated if you state your attempt on the reduction so we can think about it with you from there. $\endgroup$ – Auberon May 19 '16 at 7:36
  • 2
    $\begingroup$ What kind of directed, acyclic graphs contain Eulerian paths? Suppose G is a dag that contains an Eulerian path. Once you leave a node, you can't return, so every node in G should have out-degree <= 1. Doesn't this mean that G itself is just a (directed) path? $\endgroup$ – mhum May 19 '16 at 23:28

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.