CS Special Seminar: Tuukka Korhonen "How Graph Structure Makes Hard Problems Tractable"
How Graph Structure Makes Hard Problems Tractable
Tuukka Korhonen
University of Copenhagen
Abstract: Many algorithmic problems are infeasible to solve in the worst case. Despite this, we solve them daily in practice, on inputs much larger than worst-case theory would suggest. This includes problems such as route planning, software verification, and frequency allocation in mobile networks.
A key reason for this phenomenon is that real-world inputs have structure that algorithms can exploit. In this talk, I will discuss how graph-theoretic structure can be used to make hard algorithmic problems tractable across computer science. I will also show how it helps us understand which instances of hard problems are easy and which remain intrinsically intractable.
Bio: Tuukka Korhonen is a postdoctoral fellow at the University of Copenhagen. He obtained his PhD from the University of Bergen in 2024 and received the EATCS Distinguished Dissertation Award. His research focuses on algorithms and graph theory, especially on the connections between structural graph theory and various areas of algorithms.
Department of Computer Science
We are an internationally-oriented community and home to world-class research in modern computer science.