Tomohiro Koana

Breaking the $2^{n}$ barrier for directed hamiltonicity

Tomohiro Koana, Soh Kumabe

We give a randomized algorithm for Directed Hamiltonian Cycle on $n$ -vertex directed graphs that runs in $O^{*} (1.913 3^{n})$ time. For general directed graphs, this is the first improv…

A Deterministic Polynomial Kernel for Odd Cycle Transversal

Tomohiro Koana, Soh Kumabe

We give a deterministic polynomial kernel for Odd Cycle Transversal, derandomizing the randomized kernel of Kratsch and Wahlström (TALG 2014). Our algorithm uses a deterministic po…

High-Multiplicity Bin Packing is FPT

Tomohiro Koana, Soh Kumabe

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct it…

Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation

Tomohiro Koana, Soh Kumabe

Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a gi…

cs.GT2026

Graph Coloring with Color Preferences

Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the colo…

Approximate Counting of $k$ -Paths in $O^{*} (2^{k})$ Time

Tomohiro Koana

We resolve the conjecture of Koutis and Williams that $k$ -paths can be approximately counted in $O^{*} (2^{k})$ time. For a simple directed graph with $n$ vertices and $m$ arcs, our ran…

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 $k$ . For I…

A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation

Tomohiro Koana, Soh Kumabe

We study restricted-link augmentation to $2$ -vertex-connectivity. An instance consists of a graph $G$ , possibly disconnected, a set $L$ of admissible links on its vertices, integer…

Kernelization for $H$ -Packing Revisited

Tomohiro Koana, Soh Kumabe

\textsc{ $H$ -Packing} asks whether a graph $G$ contains $k$ vertex-disjoint copies of a fixed pattern graph $H$ . Via the standard reduction to \textsc{ $d$ -Set Packing}, one obtains…

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…

Graph Coloring Below Guarantees via Co-Triangle Packing

Shyan Akmal, Tomohiro Koana

In the $ℓ$ -Coloring Problem, we are given a graph on $n$ nodes, and tasked with determining if its vertices can be properly colored using $ℓ$ colors. In this paper we study b…

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

Andreas Björklund, Petteri Kaski, Tomohiro Koana +1

We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_{d} (x, y, z) = \sum_{A, B, C \in (d [ 3 d ]) : A \cup B \cup C = [3 d]} x_{A} y_{B} z_{C}$ for a large enough constan…

FPT algorithms over linear delta-matroids with applications

Eduard Eiben, Tomohiro Koana, Magnus Wahlström

Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta…

Faster Minimization of Total Weighted Completion Time on Parallel Machines

Danny Hermelin, Tomohiro Koana, Dvir Shabtay

We study the classical problem of minimizing the total weighted completion time on a fixed set of $m$ identical machines working in parallel, the $P m ∣∣ \sum w_{j} C_{j}$ problem in the s…

Faster Edge Coloring by Partition Sieving

Shyan Akmal, Tomohiro Koana

In the Edge Coloring problem, we are given an undirected graph $G$ with $n$ vertices and $m$ edges, and are tasked with finding the smallest positive integer $k$ so that the edges…

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_{4}$ -Minor

Carla Groenland, Jesper Nederlof, Tomohiro Koana

We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a termi…

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs

Tomohiro Koana, Nidhi Purohit, Kirill Simonov

In Clique Cover, given a graph $G$ and an integer $k$ , the task is to partition the vertices of $G$ into $k$ cliques. Clique Cover on unit ball graphs has a natural interpretation…

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Matthias Bentert, Klaus Heeger, Tomohiro Koana

We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal i…