Balaji, Nikhil ;
Datta, Samir ;
Ganesan, Venkatesh
Counting Euler Tours in Undirected Bounded Treewidth Graphs
Abstract
We show that counting Euler tours in undirected bounded treewidth graphs is tractable even in parallel  by proving a GapL upper bound. This is in stark contrast to #Pcompleteness of the same problem in general graphs.
Our main technical contribution is to show how (an instance of) dynamic programming on bounded cliquewidth 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 cliquewidth 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 treewidth graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in boundedclique width graphs.
While establishing that counting Euler tours in bounded treewidth graphs can be computed by nonuniform monotone arithmetic circuits of polynomial degree (which characterize #SAC^1) is relatively easy, establishing a uniform #SAC^1 bound needs a careful use of polynomial interpolation.
BibTeX  Entry
@InProceedings{balaji_et_al:LIPIcs:2015:5649,
author = {Nikhil Balaji and Samir Datta and Venkatesh Ganesan},
title = {{Counting Euler Tours in Undirected Bounded Treewidth Graphs}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {246260},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5649},
URN = {urn:nbn:de:0030drops56493},
doi = {10.4230/LIPIcs.FSTTCS.2015.246},
annote = {Keywords: Euler Tours, Bounded Treewidth, Bounded cliquewidth, Hamiltonian cycles, Parallel algorithms}
}
2015
Keywords: 

Euler Tours, Bounded Treewidth, Bounded cliquewidth, Hamiltonian cycles, Parallel algorithms 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

2015 