Name
Abstract | ||
|---|---|---|
We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a GapL upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. 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 #SAC^1) is relatively easy, establishing a uniform #SAC^1 bound needs a careful use of polynomial interpolation. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.FSTTCS.2015.246 | foundations of software technology and theoretical computer science |
DocType | Volume | Citations |
Journal | abs/1510.04035 | 3 |
PageRank | References | Authors |
0.43 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Balaji | 1 | 9 | 4.24 |
| Samir Datta | 2 | 200 | 19.82 |
| Venkatesh Ganesan | 3 | 3 | 0.43 |