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…

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

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…

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

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 $G$ and two sets of vertices $S$ and $T$ . The question is, what…