BARC talk by Tuukka Korhonen

Thursday, February 27, 2025, Tuukka Korhonen, PostDoc at BARC, University of Copenhagen, will give a talk on "Computing Treewidth".

Abstract:
Treewidth, defined by Robertson and Seymour in their Graph Minors series and introduced independently by various authors in the 70s and 80s, measures how tree-like a graph is. Informally speaking, trees can be decomposed using separators of size one, while graphs of treewidth k can be decomposed using separators of size k. Over the past 40 years, treewidth has played a fundamental role in algorithms and graph theory.

In this talk, Tuukka will first give a gentle introduction to treewidth and its applications in computer science. He will then discuss his recent contributions to the problem of computing treewidth, which is a central challenge in all applications of it.

Bio:
Tuukka Korhonen joined BARC on the 1st of September as a postdoc, working with Mikkel Thorup. He completed his PhD at the University of Bergen in May 2024, supervised by Fedor V. Fomin, and got his MSc from the University of Helsinki in 2020.
Tuukka's primary research focus is on parameterized graph algorithms and structural graph theory. Particularly, he focuses on developing efficient algorithms for exploiting structure of graphs such as bounded treewidth or excluded minor. He has also worked on topics such as algebraic techniques for FPT algorithms, lower bounds for tropical circuits, and practical solvers for #SAT and MaxSAT.

Tuukka's personal website is https://tuukkakorhonen.com/