From the 1 of 11 linked papers with an AI index.
11 papers
Complexity of induced subgraph isomorphism and maximum common induced subgraph parameterized by cluster vertex deletion number
Tomohiro Koana, Soh Kumabe, Yota Otachi
We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number . For I…
A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
Tomohiro Koana, Soh Kumabe
We study restricted-link augmentation to -vertex-connectivity. An instance consists of a graph , possibly disconnected, a set of admissible links on its vertices, integer…
Kernelization for -Packing Revisited
Tomohiro Koana, Soh Kumabe
The paper investigates kernelization for the H‑Packing problem, providing improved polynomial kernels for various subdivided‑star patterns and proving compression lower bounds for…
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Lawler-Moore Speedups via Additive Combinatorics
Karl Bringmann, Danny Hermelin, Tomohiro Koana +1
The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion tim…
Determinantal Sieving
Eduard Eiben, Tomohiro Koana, Magnus Wahlström
We introduce determinantal sieving, a new, remarkably powerful tool in the toolbox of algebraic FPT algorithms. Given a polynomial on a set of variables $X=\{x_1,\ldots,x_n\…