Tuukka Korhonen

The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...

Congratulations to all authors!

Branch-width of connectivity functions is fixed-parameter tractable A connectivity function on a finite set $V$ is a symmetric submodular function $f \colon 2^V \to \mathbb{Z}$ with $f(\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ fo...

#New_arXiv_paper
Tuukka Korhonen and *Sang-il Oum*,
Branch-width of connectivity functions is fixed-parameter tractable, 2026.
arxiv.org/abs/2601.04756

Stoked about the new work with Édouard Bonnet, Tuukka Korhonen, Jason Li, and Tomáš Masařík: a simple linear time algorithm to find a balanced separator in minor-free graphs.

A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/

Paper: arxiv.org/abs/2512.01587

\'Edouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tom\'a\v{s} Masa\v{r}\'ik
Separator Theorem for Minor-Free Graphs in Linear Time
https://arxiv.org/abs/2512.01587

Want to join the ambitious, creative, collaborative, and fun environment at BARC? Our annual call for PhD or integrated MSc + PhD fellowship in Algorithms has been posted! Apply by January 10. employment.ku.dk/phd/?show=15...

Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, Tuukka Korhonen
Dynamic Meta-Kernelization
https://arxiv.org/abs/2511.03461

The list of accepted papers at #FOCS2025 is up!

focs.computer.org/2025/accepte...

Tuukka Korhonen
Dynamic Treewidth in Logarithmic Time
https://arxiv.org/abs/2504.02790

Good stuff! One of my biggest pet peeves with the applied algorithms academia is that the goal is to improve running times, but these improvements should be achieved by fancy new high-level ideas instead of low-level improvements to known approaches.