2015/10/14 by Nikhil Balaji, Balaji, Nikhil, Samir Datta +3
Computer Science · #Advanced Graph Theory Research #Data Management and Algorithms #Graph Labeling and Dimension Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1510.04035
17 pages; There was an error in the proof of the GapL upper bound claimed in the previous version which has been subsequently removed
arxiv created 2015/12/12 · arxiv updated 2015/12/15
We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a #SAC1 upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynamic programming on bounded clique-width graphs can be performed efficiently in parallel. Thus we show that the sequential result of Espelage, Gurski and Wanke for efficiently computing Hamiltonian paths in bounded clique-width graphs can be adapted in the parallel setting to count the number of Hamiltonian paths which in turn is a tool for counting the number of Euler tours in bounded tree-width graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in bounded-clique width graphs. While establishing that counting Euler tours in bounded tree-width graphs can be computed by non-uniform monotone arithmetic circuits of polynomial degree (which characterize #SAC1) is relatively easy, establishing a uniform #SAC1 bound needs a careful use of polynomial interpolation.