10 citations · 30 across the 24 of their papers we have counts for
29 papers
Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi +2
In this paper, we present the first study of the computational complexity of converting an automata-based text index structure, called the Compact Directed Acyclic Word Graph (CDAW…
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann +2
In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay…
Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Finding a maximum cardinality common independent set in two matroids (also known as \textsc{Matroid Intersection}) is a classical combinatorial optimization problem, which generali…
Minimum Consistent Subset for Trees Revisited
Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi +2
In a vertex-colored graph , a subset is said to be consistent if every vertex has a nearest neighbor in with the same color. The problem of computin…
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi +1
Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescri…
Independent set reconfiguration on directed graphs
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +4
\textsc{Directed Token Sliding} asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a…
Finding shortest non-separating and non-disconnecting paths
Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi
For a connected graph and , a non-separating - path is a path between and such that the set of vertices of does not separate , tha…
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +2
Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study…
Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +3
In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arbo…
Polynomial-Delay Enumeration of Large Maximal Matchings
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Enumerating matchings is a classical problem in the field of enumeration algorithms. There are polynomial-delay enumeration algorithms for several settings, such as enumerating per…
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi +2
For intractable problems on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained complexity results. Although t…
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka +5
A cactus is a connected graph that does not contain as a minor. Given a graph and integer , Cactus Vertex Deletion (also known as Diamond Hitting Se…
Linear-Delay Enumeration for Minimal Steiner Problems
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Kimelfeld and Sagiv [Kimelfeld and Sagiv, PODS 2006], [Kimelfeld and Sagiv, Inf. Syst. 2008] pointed out the problem of enumerating -fragments is of great importance in a keywor…
A Note on Exponential-Time Algorithms for Linearwidth
Yasuaki Kobayashi, Yu Nakahata
In this note, we give an algorithm that computes the linearwidth of input -vertex graphs in time , which improves a trivial -time algorithm, where and $m…
Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi +1
We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this…
Finding Diverse Trees, Paths, and More
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +1
Mathematical modeling is a standard approach to solve many real-world problems and {\em diversity} of solutions is an important issue, emerging in applying solutions obtained from…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
Parameterized Complexity of Graph Burning
Yasuaki Kobayashi, Yota Otachi
Graph Burning asks, given a graph and an integer , whether there exists such that every vertex in has distance at most from…
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Kazuhiro Kurita, Yasuaki Kobayashi
Let be an undirected graph and let be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of whose removal destroy…
Metric Learning for Ordered Labeled Trees with pq-grams
Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi +1
Computing the similarity between two data points plays a vital role in many machine learning algorithms. Metric learning has the aim of learning a good metric automatically from da…
On Structural Parameterizations of Node Kayles
Yasuaki Kobayashi
Node Kayles is a well-known two-player impartial game on graphs: Given an undirected graph, each player alternately chooses a vertex not adjacent to previously chosen vertices, and…
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the tot…
Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara +2
The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph whose vertices are colored by red or…
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1
We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted…