5 citations · 5 across the 15 of their papers we have counts for
20 papers
On the Complexity of Forcing and Anti-Forcing Minimum Cuts
Tatsuya Gima, Yasuaki Kobayashi, Hiraku Morimoto +1
For an instance of a combinatorial optimization problem, a \emph{forcing set} is a set of elements such that there is a unique optimal solution including it. Symmetrically, an \emp…
Extending Courcelle's Theorem with Optimality Predicates
Tatsuya Gima
Courcelle's theorem and its optimization variants yield fixed-parameter tractable algorithms for a wide range of graph problems on graphs of bounded treewidth or clique-width. Howe…
Treewidth of the toroidal grid
Tatsuya Gima, Hiraku Morimoto, Yuto Okada +1
In this paper, we show that the treewidth of the toroidal grid is for all . This closes the gap between the previously known upper bound of (Ell…
Forcing a unique minimum spanning tree and a unique shortest path
Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +7
A forcing set in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in . An anti-forcing set is the symmetric c…
Hitting Geodesic Intervals in Structurally Restricted Graphs
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada +2
Given a graph , a set of vertex pairs, and an integer , Hitting Geodesic Intervals asks whether there is a set of size at most such that for e…
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…
Structural Parameterizations of -Planarity
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada
The concept of -planarity is extensively studied in the context of Beyond Planarity. A graph is -planar if it admits a drawing in the plane in which each edge is crossed at m…
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
Computing diverse pair of solutions for tractable SAT
Tatsuya Gima, Yuni Iwamasa, Yasuaki Kobayashi +3
In many decision-making processes, one may prefer multiple solutions to a single solution, which allows us to choose an appropriate solution from the set of promising solutions tha…
An improved spectral lower bound of treewidth
Tatsuya Gima, Tesshu Hanaka, Kohei Noro +2
We show that for every -vertex graph with at least one edge, its treewidth is greater than or equal to , where and are the maximum degree a…
On the complexity of list -packing for sparse graph classes
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +5
The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-d…
Orientable Burning Number of Graphs
Julien Courtiel, Paul Dorbec, Tatsuya Gima +2
In this paper, we introduce the problem of finding an orientation of a given undirected graph that maximizes the burning number of the resulting directed graph. We show that the pr…
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…
Structural Parameterizations of Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +3
The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a sma…
Bandwidth Parameterized by Cluster Vertex Deletion Number
Tatsuya Gima, Eun Jung Kim, Noleen Köhler +2
Given a graph and an integer , Bandwidth asks whether there exists a bijection from to such that $\max_{\{u, v \} \in E(G)} | π(u) - π(v)…
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…
Extended MSO Model Checking via Small Vertex Integrity
Tatsuya Gima, Yota Otachi
We study the model checking problem of an extended with local and global cardinality constraints, called , introduced rece…
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…