2 citations · 4 across the 19 of their papers we have counts for
27 papers
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…
Quadratic Kernel for Cliques or Trees Vertex Deletion
Soh Kumabe
We consider \textsc{Cliques or Trees Vertex Deletion}, which is a hybrid of two fundamental parameterized problems: \textsc{Cluster Vertex Deletion} and \textsc{Feedback Vertex Set…
Courcelle's Theorem for Lipschitz Continuity
Tatsuya Gima, Soh Kumabe, Yuichi Yoshida
Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida (FOCS'23), measures the stability of an algorithm against small input perturbations. Algorithms with small Lips…
Max-Distance Sparsification for Diversification and Clustering
Soh Kumabe
Let be a set family that is the solution domain of some combinatorial problem. The \emph{max-min diversification problem on } is the problem to select $k…
Average sensitivity of the Knapsack Problem
Soh Kumabe, Yuichi Yoshida
In resource allocation, we often require that the output allocation of an algorithm is stable against input perturbation because frequent reallocation is costly and untrustworthy.…
Lipschitz Continuous Allocations for Optimization Games
Soh Kumabe, Yuichi Yoshida
In cooperative game theory, the primary focus is the equitable allocation of payoffs or costs among agents. However, in the practical applications of cooperative games, accurately…
Complexity of graph-state preparation by Clifford circuits
Soh Kumabe, Ryuhei Mori, Yusei Yoshimura
In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford…
Dichotomies for Tree Minor Containment with Structural Parameters
Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita +2
The problem of determining whether a graph contains another graph as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph a…
Lipschitz Continuous Algorithms for Covering Problems
Soh Kumabe, Yuichi Yoshida
Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small pe…
Lipschitz Continuous Algorithms for Graph Problems
Soh Kumabe, Yuichi Yoshida
Graph algorithms are widely used for decision making and knowledge discovery. To ensure their effectiveness, it is essential that their output remains stable even when subjected to…
Learning General Inventory Management Policy for Large Supply Chain Network
Soh Kumabe, Shinya Shiroshita, Takanori Hayashi +1
Inventory management in warehouses directly affects profits made by manufacturers. Particularly, large manufacturers produce a very large variety of products that are handled by a…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
Average Sensitivity of Dynamic Programming
Soh Kumabe, Yuichi Yoshida
When processing data with uncertainty, it is desirable that the output of the algorithm is stable against small perturbations in the input. Varma and Yoshida [SODA'21] recently for…
r-Gathering Problems on Spiders:Hardness, FPT Algorithms, and PTASes
Soh Kumabe, Takanori Maehara
We consider the min-max -gathering problem described as follows: We are given a set of users and facilities in a metric space. We open some of the facilities and assign each use…
Interval Query Problem on Cube-free Median Graphs
Soh Kumabe
In this paper, we introduce the \emph{interval query problem} on cube-free median graphs. Let be a cube-free median graph and be a commutative semigroup. For each…
-Gather Clustering and -Gathering on Spider: FPT Algorithms and Hardness
Soh Kumabe, Takanori Maehara
We consider min-max -gather clustering problem and min-max -gathering problem. In the min-max -gather clustering problem, we are given a set of users and divide them into…