NC-Algorithms for Graphs with Small Treewidth

In this paper we give a parallel algorithm for recognizing graphs with treewidth ≤ k, for constant k, and building the corresponding tree-decomposition, that uses O(log n) time and O(n^3k+4) processors on a CRCW PRAM. Also, we give a parallel algorithm that transforms a given tree-decomposition of a graph G with treewidth k to another tree-decomposition of G with treewidth ≤ 3k+2, such that the tree in this tree-decomposition is binary and has logarithmic depth. The algorithm uses a linear number of processors and O(log n) time. Many NP-complete graph problems are known to be solvable in polynomial time, when restricted to graphs with treewidth ≤ k, k constant. From the results in this paper, it follows that most of these problems are also in NC, when restricted to graphs with treewidth bounded by a constant.