Tuukka Korhonen

I am a postdoc at BARC at the University of Copenhagen. I defended my PhD on 15th of May 2024 at the University of Bergen. My supervisor was Fedor V. Fomin. I got my master's degree at the University of Helsinki, where I did research in the Constraint Reasoning and Optimization group.

My research interests are in algorithms and graph theory. More precisely, I am interested in designing efficient graph algorithms, mostly from the viewpoint of parameterized algorithms, as well as in structural graph theory. My main focus is in the intersection of these two areas.

Research

Publications

• Packing Short Cycles. with Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Kirill Simonov. SODA 2025.
• Fixed-Parameter Tractability of Hedge Cut. with Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. SODA 2025.
• Minor Containment and Disjoint Paths in almost-linear time. with Michał Pilipczuk and Giannos Stamoulis. FOCS 2024.
• Two-sets cut-uncut on planar graphs. with Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. ICALP 2024.
• Computing Tree Decompositions with Small Independence Number. with Clément Dallard, Fedor V. Fomin, Petr A. Golovach, and Martin Milanič. ICALP 2024.
• Stability in Graphs with Matroid Constraints. with Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh. SWAT 2024.
• Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth. with Marek Sokołowski. STOC 2024.
• Structural perspective on constraint-based learning of Markov networks. with Fedor V. Fomin and Pekka Parviainen. AISTATS 2024.
• Fully dynamic approximation schemes on planar and apex-minor-free graphs. with Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski. SODA 2024.
• Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition. with Daniel Lokshtanov. SODA 2024.
• Computing paths of large rank in planar frameworks deterministically. with Fedor V. Fomin, Petr A. Golovach, and Giannos Stamoulis. ISAAC 2023.
• Dynamic treewidth. with Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski. FOCS 2023. Invited to HALG 2024.
• Polynomial-time Approximation of Independent Set Parameterized by Treewidth. with Parinya Chalermsook, Fedor V. Fomin, Thekla Hamm, Jesper Nederlof, and Ly Orgo. ESA 2023.
• New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth. with Benjamin Bergougnoux and Igor Razgon. WG 2023.
• An Improved Parameterized Algorithm for Treewidth. with Daniel Lokshtanov. STOC 2023. To appear in SIAM Journal on Computing special issue for STOC 2023.
• Grid Induced Minor Theorem for Graphs of Small Degree. Journal of Combinatorial Theory, Series B, 160:206-214, 2023.
• Tight Lower Bounds for Problems Parameterized by Rank-width. with Benjamin Bergougnoux and Jesper Nederlof. STACS 2023.
• Shortest Cycles With Monotone Submodular Costs. with Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Giannos Stamoulis. SODA 2023 and ACM Transactions on Algorithms, 20:2:1-22, 2024.
• Fixed-Parameter Tractability of Maximum Colored Path and Beyond. with Fedor V. Fomin, Petr A. Golovach, Kirill Simonov, and Giannos Stamoulis. SODA 2023, to appear in ACM Transactions on Algorithms.
• Fast FPT-Approximation of Branchwidth. with Fedor V. Fomin. STOC 2022 and SIAM Journal on Computing, 53(4):1085-1131, 2024.
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth. FOCS 2021. To appear in SIAM Journal on Computing special issue for FOCS 2021.
• Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters. with Matti Järvisalo. CP 2021.
• Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. ICALP 2021.
• Finding Optimal Triangulations Parameterized by Edge Clique Cover. IPEC 2020 (Best Paper Award) and Algorithmica, 84:2242-2270, 2022, special issue for IPEC 2020.
• PACE solver description: SMS. IPEC 2020.
• Finding Most Compatible Phylogenetic Trees over Multi-State Characters. with Matti Järvisalo. AAAI 2020.
• Enumerating Potential Maximal Cliques via SAT and ASP. with Jeremias Berg and Matti Järvisalo. IJCAI 2019.
• Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm. with Jeremias Berg and Matti Järvisalo. ACM Journal of Experimental Algorithmics, 24:1.9, 2019.
• MaxPre: An Extended MaxSAT Preprocessor. with Jeremias Berg, Paul Saikko, and Matti Järvisalo. SAT 2017.

Preprints and manuscripts

• Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More. 2024.
• Unavoidable induced subgraphs in graphs with complete bipartite induced minors. with Maria Chudnovsky, Meike Hatzel, Nicolas Trotignon, and Sebastian Wiederrecht. 2024.
• Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor. with Édouard Bonnet, Jędrzej Hodor, and Tomáš Masařík. 2023.
• On Induced Versions of Menger's Theorem on Sparse Graphs. with Peter Gartland and Daniel Lokshtanov. 2023.
• SharpSAT-TD in Model Counting Competitions 2021-2023. with Matti Järvisalo. 2023.
• Listing Small Minimal Separators of a Graph. 2020.
• Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover. 2020.

Theses

• PhD thesis. Computing Width Parameters of Graphs. University of Bergen, 2024. (official version)
• MSc thesis. Finding Optimal Tree Decompositions. University of Helsinki, 2020.

Talks

• Minor Containment and Disjoint Paths in almost-linear time.
• AlgPiE by IGAFIT 2024 (slides)
• Helsinki Algorithms & Theory Days 2024 (slides)
• LIRMM (slides)
• Stability in Graphs with Matroid Constraints. (slides) at SWAT 2024.
• Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition.
• SODA 2024 (slides)
• University of Warsaw Algorithms seminar (slides)
• Invited tutorial: New algorithms for computing treewidth. (slides) at STWOR 2023.
• Invited tutorial: New methods in FPT algorithms for treewidth. (slides) at IPEC 2023.
• Computing treewidth. (slides) at FPT Fest 2023 in the honor of Mike Fellows.
• Dynamic treewidth.
• HALG 2024 (invited talk) (slides)
• BARC Talk (slides)
• FPT Fest 2023 in the honor of Mike Fellows (slides)
• Two-sets cut-uncut on planar graphs. (slides) at University of Warsaw Algorithms seminar.
• Shortest Cycles With Monotone Submodular Costs. (slides) at SODA 2023.
• An Improved Parameterized Algorithm for Treewidth.
• STOC 2023 (slides, video)
• Princeton Discrete Mathematics Seminar (slides)
• Jagiellonian University TCS seminar (slides, video)
• Helsinki CS Theory Seminar (slides)
• UCSB CS Theory Colloquium (slides)
• Graph Decompositions: Small Width, Big Challenges (slides)
• Computing Tree Decompositions with Small Independence Number.
• ICALP 2024 (slides)
• Dagstuhl Seminar: Vertex Partitioning in Graphs: From Structure to Algorithms (slides)
• GROW 2022 (slides)
• Fixed-Parameter Tractability of Maximum Colored Path and Beyond.
• SODA 2023 (slides)
• Helsinki CS Theory Seminar (slides)
• Grid Induced Minor Theorem for Graphs of Small Degree. (slides) at CSGT 2022.
• Fast FPT 2-Approximation Algorithms for Width Parameters. (slides) at PAAW 2022.
• Fast FPT-Approximation of Branchwidth.
• STOC 2022 (slides, video, poster)
• APGA 2022 (slides)
• Workshop on Parametrized complexity and discrete optimization at Hausdorff Research Institute for Mathematics, 12/2021, (slides, video)
• IBS Virtual Discrete Math Colloquium, 11/2021, (slides)
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth.
• FOCS 2021, (slides, video)
• seminar of AlGCo, 1/2022, (slides)
• Frontiers of Parameterized Complexity, 5/2021, (slides, video)
• Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters. (slides, video) at CP 2021.
• Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. (slides, video) at ICALP 2021.
• SharpSAT-TD: Improving SharpSAT by Exploiting Tree Decompositions. (slides, video) at Workshop on Model Counting 2021.
• Finding Optimal Triangulations Parameterized by Edge Clique Cover. (slides, video) at IPEC 2020.
• PACE solver description: SMS. (slides) at IPEC 2020.
• Finding Most Compatible Phylogenetic Trees over Multi-State Characters. (slides, poster) at AAAI 2020.
• Enumerating Potential Maximal Cliques via SAT and ASP. (slides, poster) at IJCAI 2019.

Software

• SharpSAT-TD - #SAT-solver that utilizes tree decompositions.
• SMS - Exact algorithm for computing treedepth using small minimal separators.
• Triangulator - Implementation of the Bouchitté-Todinca algorithm for exact computing of optimal triangulations with various notions of "optimal".
• MaxPre - MaxSAT preprocessor.

Competitions

• Model Counting Competition with solver SharpSAT-TD:
  • 2023: first places on tracks 1 and 2
  • 2022: first place on track 2, second place on track 1
  • 2021: first places on tracks 1, 2, and 4
• 2nd place in PACE 2020, exact treedepth track.
• 2nd place in PACE 2017, exact minimum fill-in track.

Reviewing

• Conference PC member: STACS 2025, IPEC 2024
• Conference reviewer: SOFSEM 2025, SODA 2025, ESA 2024, FOCS 2024, IWOCA 2024, ICALP 2024, SWAT 2024, SOCG 2024, STOC 2024, ALENEX 2024, SODA 2024, ISAAC 2023, COCOON 2023, ESA 2023, MFCS 2023, ICALP 2023, STOC 2023, LATIN 2022, ESA 2022, MFCS 2022, WG 2022, SWAT 2022, ICALP 2022, STOC 2022, AAAI 2022, SAT 2021, ICALP 2021, AAAI 2021, MFCS 2020, SAT 2020
• Journal reviewer: SIAM Journal on Computing, Journal of Combinatorial Theory Series B, Combinatorica, SIAM Journal on Discrete Mathematics, Electronic Journal of Combinatorics, Journal of Graph Theory, Discrete Applied Mathematics, Theoretical Computer Science

Awards

• VCLA International Student Awards 2021 Outstanding Master Thesis Award
• Finnish Society for Computer Science Master's thesis award - the best computer science Master's thesis in Finland in the academic year 2019-2020
• IPEC 2020 Best Paper Award and Best Student Paper Award

Open problems

An incomplete list of open problems that I like.

Other

Education

• PhD, University of Bergen, 5/2024.
• Master of Science, Computer Science, University of Helsinki, 7/2020.
• Bachelor of Science, Computer Science, University of Helsinki, 9/2019.

Experience

• 8/2020-7/2021. Mandatory (non)-military service as research assistant at University of Helsinki.
• 6/2016-6/2017, 10/2017-5/2018, 2/2019-7/2020. Research assistant in Constraint Reasoning and Optimization group at University of Helsinki.
• 6/2018-12/2018. Software engineering intern at Google Zürich.
• 7/2017-9/2017. Software developer intern at Jane Street London.

Programming contests

• My profiles at online programming contest sites: Codeforces, Topcoder, Atcoder.
• Results in ICPC: 13th in finals 2017, 14th in finals 2016, 2nd in NWERC 2016, 1st in NWERC 2015, 1st in NCPC 2016, 2nd in NCPC 2015.
• Results in high school contests: bronze medal in IOI 2015, silver medal in BOI 2015, first place in Finnish olympiad in informatics 2015.