2
$\begingroup$
  • I would like to find all Euler PATHs in a directed graph.
  • Counting (instead of finding) all the Euler PATHs is sufficient.
  • Circuits are not good for me, only Paths.

I am doing a problem, that I have derived to a point, where knowing the number of paths fast would help. Currently, I have written (in c++) a recursive function that finds all of them, but it complexity grows quickly, so my algorithm gets slow fast. My algorithm is ~O(2^n). I would like a faster one for counting, if possible.

I have researched the topic, but I can only find proofs (for being NP complete, or polynomial) and algorithms for Euler Circuits in directed and undirected graphs. But again, I am looking for Euler Paths in directed graphs.

My graphs have only two nodes, but a lot of edges, that should be touched only once, like in an Euler Path.

So in summary:

  1. Euler Path.
  2. Directed Graph.
  3. Only two nodes.
  4. High edge count.
  5. Edge costs are the same.

Here is an image to illustrate a possible set up.

enter image description here

$\endgroup$
  • $\begingroup$ This seems like, at worst, a straight-forward dynamic programming exercise. ​ Are you hoping to parallelize it or use less memory? ​ ​ ​ ​ $\endgroup$ – user12859 Jan 30 '16 at 8:11
  • $\begingroup$ For general graphs and Eulerian circuits this is #P-complete: cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf. $\endgroup$ – Yuval Filmus Jan 30 '16 at 8:22
1
$\begingroup$

You can actually come up with a formula for this. Let $\ell_0,\ell_1$ be the number of self-loops at $0,1$, and let $e_{01},e_{10}$ be the edges from $0$ to $1$ and in the other direction. We must have $|e_{01}-e_{10}| \leq 1$. If $e_{01} = e_{10}+1$ then the path must start at $0$; if $e_{10} = e_{01}+1$ then it must start at $1$; if $e_{01} = e_{10}$ then both are possible. We will count paths starting at $0$.

Given an Eulerian path starting at $0$, we can write it as $$ L_0 E_1 L_1 E_2 \cdots E_m L_m, $$ where $L_0,L_2,\ldots$ are collections of self-loops at $0$, $L_1,L_3,\ldots$ are collections of self-loops at $1$, $E_1,E_3,\ldots$ are $0\to 1$ edges, and $E_2,E_4,\ldots$ are $1\to 0$ edges. We can decompose this path into three components: $$ E_1 E_2 \ldots E_m \\ L_0 L_2 \ldots \\ L_1 L_3 \ldots $$ We can choose the first component in $e_{01}! e_{10}!$ ways, the second component in $\ell_0!$ ways, and the third component is $\ell_1!$ ways. It remains to choose a way of partitioning the latter two strings into their components. In order to count this, assume that $m$ is even (the case $m$ odd is very similar) and divide the original path differently: $$ L_0 E_1 L_2 E_3 L_4 \ldots E_{m-1} L_m \\ L_1 E_2 L_3 E_4 L_5 \ldots E_{m-2} L_{m-1} E_m $$ The first line contains $m/2$ "breakpoints" out of $\ell_0 + m/2$ symbols in total, so the number of ways of breaking $L_0L_2\ldots L_m$ into its $m/2+1$ parts is $\binom{\ell_0+m/2}{m/2}$. The computation is similar for the second line, once we remove the $E_m$ which must appear at the end; we get $\binom{\ell_1+m/2-1}{m/2-1}$.

I'll leave you the task of bringing everything together to one formula.

$\endgroup$
  • $\begingroup$ Could you elaborate more on the "It remains to choose the positions of the edges" part? $\endgroup$ – Snowman Jan 30 '16 at 13:04
  • $\begingroup$ If you prefer, choose instead the lengths of the $L_i$. $\endgroup$ – Yuval Filmus Jan 30 '16 at 13:06
  • $\begingroup$ Alternatively, choose the decomposition of $L_0L_2\ldots$ (a permutation) to $L_0,L_2,\ldots$ (strings partitioning the permutation). $\endgroup$ – Yuval Filmus Jan 30 '16 at 13:15
  • $\begingroup$ I understand the permutation part. The two position formulas are difficult to understand for me. I would like to get a bit more details about them, if possible. Thank you for you quick replies, and detailed answer, it already helps a lot. $\endgroup$ – Snowman Jan 30 '16 at 13:18
  • 1
    $\begingroup$ Ok, I rewrote the explanation. I still encourage you to enumerate a few small examples by hand, and see how it compares to the description in the answer. $\endgroup$ – Yuval Filmus Jan 30 '16 at 13:49

Your Answer

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

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