Tuukka Korhonen

FOCS Conference 2025 Conference Paper

Dynamic Treewidth in Logarithmic Time

• Tuukka Korhonen

We present a dynamic data structure that maintains a tree decomposition of width at most $9 k+8$ of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{\mathcal{O}(k)} \log n$, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition, providing, for example, a dynamic version of Courcelle’s theorem with ${\mathcal{O}}_{k}(\log n)$ amortized update time; the ${\mathcal{O}}_{k}(\cdot)$ notation hides factors that depend on k. This improves upon a result of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], who gave a similar data structure but with amortized update time $2^{k^{\mathcal{O}(1)}} n^{o(1)}$. Furthermore, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”, which allows us to implement local rotations and analysis similar to those for splay trees.

SODA Conference 2025 Conference Paper

Fixed-Parameter Tractability of Hedge Cut

• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• Daniel Lokshtanov
• Saket Saurabh 0001

STOC Conference 2025 Conference Paper

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More

• Tuukka Korhonen

SODA Conference 2025 Conference Paper

Packing Short Cycles

• Matthias Bentert
• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• William Lochet
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

STOC Conference 2024 Conference Paper

Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth

• Tuukka Korhonen
• Marek Sokolowski 0001

We give an algorithm that given a graph G with n vertices and m edges and an integer k , in time O k ( n 1+ o (1) ) + O ( m ) either outputs a rank decomposition of G of width at most k or determines that the rankwidth of G is larger than k ; the O k (·)-notation hides factors depending on k . Our algorithm returns also a (2 k +1 −1)-expression for cliquewidth, yielding a (2 k +1 −1)-approximation algorithm for cliquewidth with the same running time. This improves upon the O k ( n 2 ) time algorithm of Fomin and Korhonen [STOC 2022]. The main ingredient of our algorithm is a fully dynamic algorithm for maintaining rank decompositions of bounded width: We give a data structure that for a dynamic n -vertex graph G that is updated by edge insertions and deletions maintains a rank decomposition of G of width at most 4 k under the promise that the rankwidth of G never grows above k . The amortized running time of each update is O k (2 √log n loglog n ). The data structure furthermore can maintain whether G satisfies some fixed CMSO 1 property within the same running time. We also give a framework for performing “dense” edge updates inside a given set of vertices X , where the new edges inside X are described by a given CMSO 1 sentence and vertex labels, in amortized O k (| X | · 2 √log n loglog n ) time. Our dynamic algorithm generalizes the dynamic treewidth algorithm of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023].

SODA Conference 2024 Conference Paper

Fully dynamic approximation schemes on planar and apex-minor-free graphs

• Tuukka Korhonen
• Wojciech Nadara
• Michal Pilipczuk
• Marek Sokolowski 0001

SODA Conference 2024 Conference Paper

Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition

• Tuukka Korhonen
• Daniel Lokshtanov

A graph G contains a graph H as an induced minor if H can be obtained from G by vertex deletions and edge contractions. The class of H -induced-minor-free graphs generalizes the class of H -minor-free graphs, but unlike H -minor-free graphs, it can contain dense graphs. We show that if an n -vertex m -edge graph G does not contain a graph H as an induced minor, then it has a balanced vertex separator of size, where the O H (·)-notation hides factors depending on H. More precisely, our upper bound for the size of the balanced separator is. We give an algorithm for finding either an induced minor model of H in G or such a separator in randomized polynomial-time. We apply this to obtain subexponential time algorithms on H -induced-minor-free graphs for a large class of problems including maximum independent set, minimum feedback vertex set, 3-coloring, and planarization. For graphs H where every edge is incident to a vertex of degree at most 2, our results imply a time algorithm for testing if G contains H as an induced minor. Our second main result is that there exists a fixed tree T, so that there is no time algorithm for testing if a given n -vertex graph contains T as an induced minor unless the Exponential Time Hypothesis (ETH) fails. Our reduction also gives NP-hardness, which solves an open problem asked by Fellows, Kratochvíl, Middendorf, and Pfeiffer [Algorithmica, 1995], who asked if there exists a fixed planar graph H so that testing for H as an induced minor is NP-hard. * The research leading to these results has received funding from the Research Council of Norway via the project BWCA (grant no. 314528) and NSF award CCF-2008838.

FOCS Conference 2024 Conference Paper

Minor Containment and Disjoint Paths in Almost-Linear Time

• Tuukka Korhonen
• Michal Pilipczuk
• Giannos Stamoulis

We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time $\mathcal{O}_{H}(\overline{n}^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the $\mathrm{O}_{H}(.)$ -notation hides factors that depend on $H$ and are computable. By the Graph Minor Theorem, this implies the existence of an $n^{1+o(1)}$ -time membership test for every minor-closed class of graphs. More generally, we give an $\mathcal{O}_{H, \vert X\vert} (m^{1+o(1)})$ -time algorithm for the rooted version of the problem, in which $G$ comes with a set of roots $X\subseteq V(G)$ and some of the branch sets of the sought minor model of $H$ are required to contain prescribed subsets of $X$; here, $m$ is the total number of vertices and edges of $G$. This captures the Disjoint Pathsproblem, for which we obtain an $\mathcal{O}_{k}(m^{1+o(1)\backslash }$ -time algorithm, where $k$ is the number of terminal pairs. For all the mentioned problems, the fastest algorithms known before are due to Kawarabayashi, Kobayashi, and Reed [JCTB 2012], and have a time complexity that is quadratic in the number of vertices of $G$. Our algorithm has two main ingredients: First, we show that by using the dynamic treewidth data structure of Korhonen, Majewski, Nadara, Pilipczuk, and Sokolowski [FOCS 2023], the irrelevant vertex technique of Robertson and Seymour can be implemented in almost-linear time on apex-minor-free graphs. Then, we apply the recent advances in almost-linear time flow/cut algorithms to give an almost-linear time implementation of the recursive understanding technique, which effectively reduces the problem to apex-minor-free graphs.

STOC Conference 2023 Conference Paper

An Improved Parameterized Algorithm for Treewidth

• Tuukka Korhonen
• Daniel Lokshtanov

We give an algorithm that takes as input an n -vertex graph G and an integer k , runs in time 2 O ( k 2 ) n O (1) , and outputs a tree decomposition of G of width at most k , if such a decomposition exists. 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, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2 O ( k 3 ) n O (1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991]. We also give an algorithm that given an n -vertex graph G , an integer k , and a rational ε ∈ (0,1), in time k O ( k /ε) n O (1) either outputs a tree decomposition of G of width at most (1+ε) k or determines that the treewidth of G is larger than k . Prior to our work, no approximation algorithms for treewidth with approximation ratio less than 2, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.

FOCS Conference 2023 Conference Paper

Dynamic treewidth

• Tuukka Korhonen
• Konrad Majewski
• Wojciech Nadara
• Michal Pilipczuk
• Marek Sokolowski 0001

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO 2 logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

SODA Conference 2023 Conference Paper

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• Kirill Simonov
• Giannos Stamoulis

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored n -vertex undirected graph, vertices s and t, and an integer k, finds an ( s, t )-path containing at least k different colors in time 2 k n 𝒪(1). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through k specified vertices. It also implies the first 2 k n 𝒪(1) time algorithm for finding an ( s, t )-path of length at least k. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an n -vertex undirected graph G, a matroid M whose elements correspond to the vertices of G and which is represented over a finite field of order q, a positive integer weight function on the vertices of G, two sets of vertices S, T ⊆ V ( G ), and integers p, k, w, and the task is to find p vertex-disjoint paths from S to T so that the union of the vertices of these paths contains an independent set of M of cardinality k and weight w, while minimizing the sum of the lengths of the paths. We give a 2 p +𝒪( k 2 log ( q + k )) n 𝒪(1) w time randomized algorithm for this problem. * The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07449. The research leading to these results has received funding from the Research Council of Norway via the project BWCA (grant no. 314528). Kirill Simonov acknowledges support by DFG Research Group ADYN under grant DFG 411362735. Giannos Stamoulis acknowledges support by the ANR project ESIGMA (ANR-17-CE23-0010) and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

SODA Conference 2023 Conference Paper

Shortest Cycles With Monotone Submodular Costs

• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• Daniel Lokshtanov
• Giannos Stamoulis

We introduce the following submodular generalization of the SHORTEST CYCLE problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f(C). We give an algorithm that given an n -vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n 𝒪(log 1/ε) finds a cycle C in G with f ( C ) ≤ (1 + ε) · OPT. This is in sharp contrast with the non-approximability of the closely related MONOTONE SUBMODULAR SHORTEST ( s, t )-PATH problem, which requires exponentially many queries to the oracle for finding an n 2//3-ε -approximation [Goel et al. , FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every ε > 0, obtaining a (1 + ε)-approximation requires at least n Ω(log 1/ε) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost OPT can be found in time n 𝒪(log OPT). In particular, for OPT = n 𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n 𝒪(log n ) queries are required even when OPT = 𝒪(n).

STOC Conference 2022 Conference Paper

Fast FPT-approximation of branchwidth

• Fedor V. Fomin
• Tuukka Korhonen

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. An algorithm that for a given n -vertex graph G and integer k in time 2 2 O ( k ) n 2 either constructs a rank decomposition of G of width at most 2 k or concludes that the rankwidth of G is more than k . It also yields a (2 2 k +1 −1)-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to f ( k ) n 2 the running times of various algorithms on graphs of cliquewidth k . Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area. An algorithm that for a given n -vertex graph G and integer k in time 2 O ( k ) n either constructs a branch decomposition of G of width at most 2 k or concludes that the branchwidth of G is more than k . This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

FOCS Conference 2021 Conference Paper

A Single-Exponential Time 2-Approximation Algorithm for Treewidth

• Tuukka Korhonen

We give an algorithm, that given an n-vertex graph $G$ and an integer k, in time 2 O(k) n either outputs a tree decomposition of $G$ of width at most 2k + 1 or determines that the treewidth of $G$ is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time 2 O(k) n and the previous best approximation ratio of 3 in time 2 O(k) n O(1), both given by Bodlaender et al. [FOCS 2013, SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].

AAAI Conference 2020 Conference Paper

Finding Most Compatible Phylogenetic Trees over Multi-State Characters

• Tuukka Korhonen
• Matti J„ärvisalo

The reconstruction of the evolutionary tree of a set of species based on qualitative attributes is a central problem in phylogenetics. In the NP-hard perfect phylogeny problem the input is a set of taxa (species) and characters (attributes) on them, and the task is to find an evolutionary tree that describes the evolution of the taxa so that each character state evolves only once. However, in practical situations a perfect phylogeny rarely exists, motivating the maximum compatibility problem of finding the largest subset of characters admitting a perfect phylogeny. Various declarative approaches, based on applying integer programming (IP), answer set programming (ASP) and pseudo-Boolean optimization (PBO) solvers, have been proposed for maximum compatibility. In this work we develop a new hybrid approach to solving maximum compatibility for multi-state characters, making use of both declarative optimization techniques (specifically maximum satisfiability, MaxSAT) and an adaptation of the Bouchitté-Todinca approach to triangulation-based graph optimization problems. Empirically our approach outperforms in scalability the earlier proposed approaches w. r. t. various parameters underlying the problem.

IJCAI Conference 2019 Conference Paper

Enumerating Potential Maximal Cliques via SAT and ASP

• Tuukka Korhonen
• Jeremias Berg
• Matti Järvisalo

The Bouchitté-Todinca algorithm (BT), operating dynamic programming over the so-called potential maximal cliques (PMCs), yields a practically efficient approach to treewidth and generalized hypertreewidth. The enumeration of PMCs is a scalability bottleneck for BT in practice. We propose the use of declarative solvers for PMC enumeration as a substitute for the specialized PMC enumeration algorithms employed in current BT implementations. The presented Boolean satisfiability (SAT) and answer set programming (ASP) based PMC enumeration approaches open up new possibilities for improving the efficiency of BT in practice.

SAT Conference 2017 Conference Paper

MaxPre: An Extended MaxSAT Preprocessor

• Tuukka Korhonen
• Jeremias Berg
• Paul Saikko
• Matti Järvisalo

Abstract We describe MaxPre, an open-source preprocessor for (weighted partial) maximum satisfiability (MaxSAT). MaxPre implements both SAT-based and MaxSAT-specific preprocessing techniques, and offers solution reconstruction, cardinality constraint encoding, and an API for tight integration into SAT-based MaxSAT solvers.