b'Yota Otachi'

research

∙ 05/12/2023

Minimum Consistent Subset for Trees Revisited

In a vertex-colored graph G = (V, E), a subset S ⊆ V is said to be consi...

0 Hiroki Arimura, et al. ∙

research

∙ 02/14/2023

Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

A dominating set S of graph G is called an r-grouped dominating set if S...

0 Tesshu Hanaka, et al. ∙

research

∙ 10/06/2022

Sequentially Swapping Tokens: Further on Graph Classes

We study the following variant of the 15 puzzle. Given a graph and two t...

0 Hironori Kiya, et al. ∙

research

∙ 07/03/2022

Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited

Given a graph and two vertex sets satisfying a certain feasibility condi...

0 Tatsuya Gima, et al. ∙

research

∙ 03/25/2022

Independent set reconfiguration on directed graphs

Directed Token Sliding asks, given a directed graph and two sets of pair...

0 Takehiro Ito, et al. ∙

research

∙ 02/20/2022

Finding shortest non-separating and non-disconnecting paths

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path...

0 Yasuaki Kobayashi, et al. ∙

research

∙ 02/19/2022

Sorting Balls and Water: Equivalence and Computational Complexity

Various forms of sorting problems have been studied over the years. Rece...

0 Takehiro Ito, et al. ∙

research

∙ 02/17/2022

Extended MSO Model Checking via Small Vertex Integrity

We study the model checking problem of an extended 𝖬𝖲𝖮 with local and gl...

0 Tatsuya Gima, et al. ∙

research

∙ 01/22/2022

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

Finding a single best solution is the most common objective in combinato...

0 Tesshu Hanaka, et al. ∙

research

∙ 12/10/2021

Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

Finding diverse solutions in combinatorial problems recently has receive...

0 Tesshu Hanaka, et al. ∙

research

∙ 11/26/2021

Reconfiguration of Regular Induced Subgraphs

We study the problem of checking the existence of a step-by-step transfo...

0 Hiroshi Eto, et al. ∙

research

∙ 09/06/2021

Computational Complexity of Jumping Block Puzzles

In combinatorial reconfiguration, the reconfiguration problems on a vert...

0 Masaaki Kanzaki, et al. ∙

research

∙ 07/07/2021

Reconfiguring Directed Trees in a Digraph

In this paper, we investigate the computational complexity of subgraph r...

0 Takehiro Ito, et al. ∙

research

∙ 01/23/2021

Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity

For intractable problems on graphs of bounded treewidth, two graph param...

0 Tatsuya Gima, et al. ∙

research

∙ 12/09/2020

An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

A cactus is a connected graph that does not contain K_4 - e as a minor. ...

0 Yuuki Aoike, et al. ∙

research

∙ 09/18/2020

Longest Common Subsequence in Sublinear Space

We present the first o(n)-space polynomial-time algorithm for computing ...

0 Masashi Kiyomi, et al. ∙

research

∙ 09/08/2020

Finding Diverse Trees, Paths, and More

Mathematical modeling is a standard approach to solve many real-world pr...

0 Tesshu Hanaka, et al. ∙

research

∙ 08/17/2020

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-wi...

0 Rémy Belmonte, et al. ∙

research

∙ 08/08/2020

Parameterized Complexity of (A,ℓ)-Path Packing

Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...

0 Rémy Belmonte, et al. ∙

research

∙ 07/17/2020

Parameterized Complexity of Graph Burning

Graph Burning asks, given a graph G = (V,E) and an integer k, whether th...

0 Yasuaki Kobayashi, et al. ∙

research

∙ 02/25/2020

Hedonic Seat Arrangement Problems

In this paper, we study a variant of hedonic games, called Seat Arrangem...

0 Hans L. Bodlaender, et al. ∙

research

∙ 09/20/2019

Linear-Time Recognition of Double-Threshold Graphs

A graph G = (V,E) is a double-threshold graph if there exist a vertex-we...

0 Yusuke Kobayashi, et al. ∙

research

∙ 08/26/2019

Low-Congestion Shortcut and Graph Parameters

The concept of low-congestion shortcuts is initiated by Ghaffari and Hae...

0 Naoki Kitamura, et al. ∙

research

∙ 05/25/2019

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

We study Subgraph Isomorphism on graph classes defined by a fixed forbid...

0 Hans L. Bodlaender, et al. ∙

research

∙ 05/01/2019

Independent Set Reconfiguration Parameterized by Modular-Width

Independent Set Reconfiguration is one of the most well-studied problems...

0 Rémy Belmonte, et al. ∙

research

∙ 01/27/2019

Parameterized Complexity of Safe Set

In this paper we study the problem of finding a small safe set S in a gr...

0 Rémy Belmonte, et al. ∙

research

∙ 07/30/2018

Parameterized Orientable Deletion

A graph is d-orientable if its edges can be oriented so that the maximum...

0 Tesshu Hanaka, et al. ∙

research

∙ 07/14/2018

Token Sliding on Split Graphs

We show that the independent set reconfiguration problem on split graphs...

0 Rémy Belmonte, et al. ∙

research

∙ 04/23/2018

How Bad is the Freedom to Flood-It?

Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs th...

0 Rémy Belmonte, et al. ∙

research

∙ 03/19/2018

Swapping Colored Tokens on Graphs

We investigate the computational complexity of the following problem. We...

0 Katsuhisa Yamanaka, et al. ∙

research

∙ 02/19/2018

Reconfiguration of Colorable Sets in Classes of Perfect Graphs

A set of vertices in a graph is c-colorable if the subgraph induced by t...

0 Takehiro Ito, et al. ∙

research

∙ 12/26/2017

Space-Efficient Algorithms for Longest Increasing Subsequence

Given a sequence of integers, we want to find a longest increasing subse...

0 Masashi Kiyomi, et al. ∙

Yota Otachi

Featured Co-authors