UCSB CS Theory Colloquium Series
Fall 2022
|
Wednesday, November 9th, 3:30pm HFH 1132 Speaker: Tuukka Korhonen (Bergen) Title: Improved Parameterized Algorithm and Approximation Scheme for Treewidth Abstract: Treewidth is a graph parameter that, informally, characterizes how tree-like a graph is. Treewidth plays an important role in many areas of computer science and graph theory, in particular generalizing results on trees to graphs of small treewidth. We give a 2^O(k^2) n^O(1) time algorithm for determining if the treewidth of a given n-vertex graph is at most k and outputting the corresponding tree decomposition. This resolves the long-standing open problem of whether there is a 2^o(k^3) n^O(1) time algorithm for treewidth. In particular, this is the first improvement on the dependency on k in fixed-parameter algorithms for treewidth since the 2^O(k^3) n^O(1) time algorithm given in 1991 by Bodlaender and Kloks, and independently, by Lagergren and Arnborg. We also give a k^O(k/eps) n^O(1) time (1+eps)-approximation algorithm for treewidth. Prior to our work, no approximation algorithms with approximation ratio less than 2 other than the exact algorithms were known. This is joint work with Daniel Lokshtanov. Bio: Tuukka Korhonen is a PhD student at the University of Bergen, advised by Fedor V. Fomin. His research interests are parameterized algorithms and algorithmic graph theory, in particular topics related to the structure of graphs. Before coming to Bergen, he received his master's degree from the University of Helsinki. |