The tree decomposition problem, also known as the treewidth problem, is a central topic in graph algorithms. Its importance comes from the fact that many graph problems that are NP-hard in general become tractable on graphs of bounded treewidth. This fixed-parameter viewpoint also appears in database theory, conjunctive query evaluation, and constraint satisfaction problems.

In this thesis, we survey major algorithmic developments for computing treewidth. We first define tree decompositions and explain why they support dynamic programming on graphs with tree-like structure. We then review separator-based algorithms, which recursively construct decompositions using small balanced separators. Next, we discuss the compression and improvement paradigm developed in the 1990s, especially in the work of Bodlaender and Kloks, and Bodlaender and Hagerup. This framework reduces the graph, solves the smaller instance, expands the decomposition, and improves it to the desired width, leading to Bodlaender's linear-time exact algorithm for fixed treewidth.

We then briefly discuss modern static and dynamic algorithms. Recent static algorithms often compute constant-factor approximate decompositions with better dependence on the parameter, such as 2^O(k)n or 2^O(k)n log n. Dynamic algorithms instead maintain a bounded-width tree decomposition under edge insertions and deletions.

A main perspective of this thesis is parallelism. Some older methods, such as balancing and improvement-based algorithms, have natural parallel components. In contrast, many modern algorithms rely on sequential local modifications, recursive dependencies, or rotation-based updates, making them difficult to parallelize. This gap motivates studying which parts of existing treewidth algorithms can be adapted to parallel static or batch-dynamic settings.

46 pages

Thesis Committee:
Guy Blelloch (Chair)
William Kuszmaul

Jignesh Patel, Interim Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu