5th Year Master's Thesis Presentation - Taekseung Kim
April 24, 2026 3:00PM—4:30PM
Location:
In Person
-
Traffic21 Classroom, Gates Hillman 6501
Speaker:
TAEKSEUNG KIM,
Master's Student
Computer Science Department
Carnegie Mellon University
The tree decomposition problem, also known as the treewidth problem, is a central topic in graph algorithms that has been studied extensively over the past 30 years. Its importance comes from the fact that treewidth serves as a parameter under which many otherwise intractable problems become algorithmically tractable. As a result, the study of treewidth has played a major role in the development of fixed-parameter tractability and has also influenced related areas such as database theory and constraint satisfaction.
In this talk, we survey previous results on treewidth computation, ranging from work by Bodlaender in the 1990s to more recent developments by Korhonen. We begin by defining the problem and reviewing the separator-based algorithms that were prominent until the early 1980s, developed by Robertson and Seymour. This line of research led to Reed’s work, which established an nlogn bound for computing treewidth. We then turn to algorithms from the 1990s, mainly due to Bodlaender and colleagues, who used compression and improvement techniques to obtain better bounds. With further development of these ideas, Bodlaender proved the existence of a linear-time algorithm for computing treewidth, and also showed that a parallel version of this algorithm exists. We then briefly discuss algorithms developed after the 2010s, including approximation algorithms obtained by Bodlaender and later improved by Korhonen in 2021. We also briefly cover the dynamic algorithm proposed by Korhonen in 2023.
In addition, we consider these results from the perspective of parallel algorithms, where some approaches appear parallelizable while others remain difficult to parallelize. We discuss the intuition and overall paradigms underlying treewidth algorithms, and examine them through a parallel lens, asking why some techniques can be parallelized and others can not. Although there has been earlier research in this direction, the parallel study of treewidth has been limited since the 1990s, especially after the paper by Bodlaender and Hagerup. At the same time, several modern techniques have been developed since then. While further progress is needed on parallel static algorithms for computing treewidth, parallel batch dynamic computation for treewidth also remains open. While Korhonen’s 2023 paper suggests an amortized dynamic algorithm for treewidth computation, this method is not suitable for parallelization since it uses splay tree style rotation, and parallel batch dynamic computation for treewidth has not yet been solved.
Finally, we suggest future directions in which this line of work could lead to parallel static and batch dynamic algorithms, which we hope to establish.
For More Information:
amalloy@cs.cmu.edu