T. Korhonen

Courcelle's Theorem in Truly Linear FPT

Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh

Recently, Bumpus, Downey, Eagling-Vose, Enright, Fellows, Kutner, Larios-Jones, Martin, Rosamond, and Yates defined Truly Linear FPT (TLFPT) to be the class of parameterized proble…

Connectivity augmentation is fixed-parameter tractable

Tuukka Korhonen, Mikkel Thorup

In the vertex connectivity augmentation problem, we are given an undirected $n$ -vertex graph $G$ , a set of links $L \subseteq (2 V ( G )) ∖ E (G)$ , and integers $λ$ and…

Branch-width of represented matroids in matrix multiplication time

Mujin Choi, Tuukka Korhonen, Sang-il Oum

For an $n$ -element matroid $M$ given by an $n \times n$ matrix representation over a finite field $F$ and an integer $k$ , we present an algorithm with running time $O_{k,\m…

Branch-width of connectivity functions is fixed-parameter tractable

Tuukka Korhonen, Sang-il Oum

A connectivity function on a finite set $V$ is a symmetric submodular function $f : 2^{V} \to Z$ with $f (\emptyset) = 0$ . We prove that finding a branch-decomposition of…

Separator Theorem for Minor-Free Graphs in Linear Time

Édouard Bonnet, Tuukka Korhonen, Hung Le +2

The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with $n$ vertices has a balanced separator of siz…

Dynamic Meta-Kernelization

Christian Bertram, Deborah Haun, Mads Vestergaard Jensen +1

Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-…

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth

Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen

The induced matching width of a tree decomposition of a graph $G$ is the cardinality of a largest induced matching $M$ of $G$ , such that there exists a bag that intersects every ed…

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 a…

cs.DS2024★ 1 cited

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

Tuukka Korhonen

We present $k^{O (k^{2})} m$ time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size $< k$ into parts that are ``well-…

cs.DS2024

Packing Short Cycles

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…

cs.DS2024

Fixed-Parameter Tractability of Hedge Cut

Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph…

math.CO2024

Unavoidable induced subgraphs in graphs with complete bipartite induced minors

Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2

We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…

cs.DS2024

Stability in Graphs with Matroid Constraints

Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +1

We study the following Independent Stable Set problem. Let G be an undirected graph and M = (V(G),I) be a matroid whose elements are the vertices of G. For an integer k\geq 1, the…

cs.DS2024★ 2 cited

Minor Containment and Disjoint Paths in almost-linear time

Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis

We give an algorithm that, given graphs $G$ and $H$ , tests whether $H$ is a minor of $G$ in time $O_{H} (n^{1 + o (1)})$ ; here, $n$ is the number of vertices of $G$ and the ${\cal…

cs.LG2024

Structural perspective on constraint-based learning of Markov networks

Tuukka Korhonen, Fedor V. Fomin, Pekka Parviainen

Markov networks are probabilistic graphical models that employ undirected graphs to depict conditional independence relationships among variables. Our focus lies in constraint-base…

cs.DS2024★ 1 cited

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth

Tuukka Korhonen, Marek Sokołowski

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…

math.CO2023★ 1 cited

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 $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$ -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…

math.CO2023

On Induced Versions of Menger's Theorem on Sparse Graphs

Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov

Let $A$ and $B$ be sets of vertices in a graph $G$ . Menger's theorem states that for every positive integer $k$ , either there exists a collection of $k$ vertex-disjoint paths betwe…

cs.AI2023★ 2 cited

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 $6$ first places in different t…

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 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 $G$ and a matroid $M$ whose elements correspond to the vertices of $G$ . Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023]…