Output details

Exact counting of Euler tours for generalized series-parallel graphs

<12>Originality: This paper presents the first polynomial-time algorithm to exactly count Euler tours in any class of graphs: specifically, the class of (generalized) series-parallel graphs.

Significance: The problem of counting/sampling Euler tours is #P-complete, meaning an exact polynomial-time algorithm is unlikely for general graphs. This problem has been of interest for decades: it is presented as an open problem in the "Approximation Algorithms" textbook by Vijay Vazirani (2001). Neither exact, nor even approximation algorithms, existed for any class of graphs before our result.

Rigour: The paper includes a proof of correctness and of the (polynomially-bounded) running time of the algorithm.