28 citations · 44 across the 32 of their papers we have counts for
10 papers · 1 filter
Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen +1
A graph contains a graph as an induced minor if can be obtained from after vertex deletions and edge contractions. We show that for every -vertex planar graph $H…
Fully dynamic approximation schemes on planar and apex-minor-free graphs
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk +1
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and…
On Induced Versions of Menger's Theorem on Sparse Graphs
Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov
Let and be sets of vertices in a graph . Menger's theorem states that for every positive integer , either there exists a collection of vertex-disjoint paths betwe…
SharpSAT-TD in Model Counting Competitions 2021-2023
Tuukka Korhonen, Matti Järvisalo
We describe SharpSAT-TD, our submission to the unweighted and weighted tracks of the Model Counting Competition in 2021-2023, which has won in total first places in different t…
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
Tuukka Korhonen, Daniel Lokshtanov
A graph contains a graph as an induced minor if can be obtained from by vertex deletions and edge contractions. The class of -induced-minor-free graphs generaliz…
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…
Computing paths of large rank in planar frameworks deterministically
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +1
A framework consists of an undirected graph and a matroid whose elements correspond to the vertices of . Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023]…
Two-sets cut-uncut on planar graphs
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin +2
We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph and two sets of vertices and . The question is, what…
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara +2
We present a data structure that for a dynamic graph that is updated by edge insertions and deletions, maintains a tree decomposition of of width at most under the p…
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
We study the tractability of the maximum independent set problem from the viewpoint of graph width parameters, with the goal of defining a width parameter that is as general as pos…