2 citations · 4 across the 19 of their papers we have counts for
9 papers · 1 filter
Breaking the barrier for directed hamiltonicity
Tomohiro Koana, Soh Kumabe
We give a randomized algorithm for Directed Hamiltonian Cycle on -vertex directed graphs that runs in 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 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 prescribed links whose total weight is within a gi…
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…
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ord…
Kernelization for -Packing Revisited
Tomohiro Koana, Soh Kumabe
\textsc{-Packing} asks whether a graph contains vertex-disjoint copies of a fixed pattern graph . Via the standard reduction to \textsc{-Set Packing}, one obtains…
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
Soh Kumabe, Yuya Uezato
ReDoS is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust comp…