Soh Kumabe

TCS Journal 2025 Journal Article

Dichotomies for tree minor containment with structural parameters

• Tatsuya Gima
• Soh Kumabe
• Kazuhiro Kurita
• Yuto Okada
• Yota Otachi

The problem of determining whether a graph G contains another graph H as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph algorithms. While the problem is NP -complete in general, it can be tractable on some restricted graph classes. This study focuses on the case where both G and H are trees, known as the tree minor containment problem. Even in this case, the problem is known to be NP -complete. In contrast, polynomial-time algorithms are known for the case when both trees are caterpillars or when the maximum degree of H is a constant. Our research aims to clarify the boundary of tractability and intractability for the tree minor containment problem. Specifically, we provide complexity dichotomies for the problem based on three structural parameters: diameter, pathwidth, and path eccentricity.

SODA Conference 2025 Conference Paper

Lipschitz Continuous Algorithms for Covering Problems

• Soh Kumabe
• Yuichi Yoshida

FOCS Conference 2023 Conference Paper

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 small perturbations to the input because frequent output changes can result in costly decisions, reduced user trust, potential security concerns, and lack of replicability. In this study, we consider the Lipschitz continuity of algorithms as a stability measure and initiate a systematic study of the Lipschitz continuity of algorithms for (weighted) graph problems. Depending on how we embed the output solution to a metric space, we can think of several Lipschitzness notions. We mainly consider the one that is invariant under scaling of weights, and we provide Lipschitz continuous algorithms and lower bounds for the minimum spanning tree problem, the shortest path problem, and the maximum weight matching problem. In particular, our shortest path algorithm is obtained by first designing an algorithm for unweighted graphs that are robust against edge contractions and then applying it to the unweighted graph constructed from the original weighted graph. Then, we consider another Lipschitzness notion induced by a natural mapping from the output solution to its characteristic vector. It turns out that no Lipschitz continuous algorithm exists for this Lipschitz notion, and we instead design algorithms with bounded pointwise Lipschitz constants for the minimum spanning tree problem and the maximum weight bipartite matching problem. Our algorithm for the latter problem is based on an LP relaxation with entropy regularization.

SODA Conference 2022 Conference Paper

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 formalized this idea and proposed the notion of average sensitivity of algorithms, which is roughly speaking, the average Hamming distance between solutions for the original input and that obtained by deleting one element from the input, where the average is taken over the deleted element. In this work, we consider average sensitivity of algorithms for problems that can be solved by dynamic programming. We first present a (1– δ )-approximation algorithm for finding a maximum weight chain (MWC) in a transitive directed acyclic graph with average sensitivity O ( δ –1 log 3 n ), where n is the number of vertices in the graph. We then show algorithms with small average sensitivity for various dynamic programming problems by reducing them to the MWC problem while preserving average sensitivity, including the longest increasing subsequence problem, the interval scheduling problem, the longest common subsequence problem, the longest palindromic subsequence problem, the knapsack problem with integral weight, and the RNA folding problem. For the RNA folding problem, our reduction is highly nontrivial because a naive reduction generates an exponentially large graph, which only provides a trivial average sensitivity bound.

IJCAI Conference 2020 Conference Paper

Convexity of b-matching Games

• Soh Kumabe
• Takanori Maehara

The b-matching game is a cooperative game defined on a graph. The game generalizes the matching game to allow each individual to have more than one partner. The game has several applications, such as the roommate assignment, the multi-item version of the seller-buyer assignment, and the international kidney exchange. Compared with the standard matching game, the b-matching game is computationally hard. In particular, the core non-emptiness problem and the core membership problem are co-NP-hard. Therefore, we focus on the convexity of the game, which is a sufficient condition of the core non-emptiness and often more tractable concept than the core non-emptiness. It also has several additional benefits. In this study, we give a necessary and sufficient condition of the convexity of the b-matching game. This condition also gives an O(n log n + m α(n)) time algorithm to determine whether a given game is convex or not, where n and m are the number of vertices and edges of a given graph, respectively, and α(・) is the inverse-Ackermann function. Using our characterization, we also give a polynomial-time algorithm to compute the Shapley value of a convex b-matching game.