Parallel Algorithms with Optimal Speedup for Bounded Treewidth

Reviewer: Abraham Kandel

The concept of treewidth has proven to be a useful tool in the design of graph algorithms: many important classes of graphs have bounded treewidth, and many important graph problems that are otherwise quite hard can be solved efficiently on graphs of bounded treewidth. A tree decomposition of an undirected graph G= V,E is a pair T,U , where T= X,F is a tree and U= U x &vbm0;xX is a family of subsets of V called bags. The width of a tree decomposition T, U x &vbm0;xX is max xX U x -1 . The treewidth of a graph G is the smallest treewidth of any tree composition of G . Path decompositions and pathwidth can be defined analogously, with the tree T restricted to be a path. The authors discuss a parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n -vertex input graphs, the algorithm works in O log 2 n time using O n operations on the exclusive-read exclusive-write parallel random access machine (EREW PRAM). Related faster parallel algorithms are also discussed; they have optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On n -vertex input graphs, the algorithms use O n operations together with O log n log * n time on the EREW PRAM, or O log n time on the concurrent-read concurrent-write (CRCW) PRAM.