2026-08-15T14:06:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5649 2024-03-06T10:36:44Z ddc:004 open_access

Counting Euler Tours in Undirected Bounded Treewidth Graphs Balaji, Nikhil Datta, Samir Ganesan, Venkatesh Euler Tours Bounded Treewidth Bounded clique-width Hamiltonian cycles Parallel algorithms 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. 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 #SAC^1) is relatively easy, establishing a uniform #SAC^1 bound needs a careful use of polynomial interpolation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Balaji and Samir Datta and Venkatesh Ganesan 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.246 urn:nbn:de:0030-drops-56493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.246 eng https://creativecommons.org/licenses/by/3.0/legalcode