Y. Otachi

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…

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 $k$ . For I…

cs.DM2026

3-packings in Triangulations: Algorithms, bounds, and Complexity

Prosenjit Bose, Anil Maheshwari, Bobby Miraftab +1

We study $H$ -packings in plane triangulations for the three-vertex graphs $H \in {P_{3}, K_{3}, P_{2} \cup P_{1}}$ . For a graph $H$ , let $λ_{H} (G)$ denote the maximum size of an $H$ -packing in…

math.CO2026

Treewidth of the $n \times n$ toroidal grid

Tatsuya Gima, Hiraku Morimoto, Yuto Okada +1

In this paper, we show that the treewidth of the $n \times n$ toroidal grid is $2 n - 1$ for all $n \geq 5$ . This closes the gap between the previously known upper bound of $2 n - 1$ (Ell…

Biclique Reconfiguration in Bipartite Graphs

Yota Otachi, Emi Toyoda

We prove that Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete. This implies the PSPACE-completeness of the spanning variant of Subgraph Reconfiguration und…

Spanning tree congestion of proper interval graphs

Yota Otachi

We show that the spanning tree congestion problem is NP-complete even on proper interval graphs with linear clique-width at most 4 and diameter 3. By slightly modifying the reducti…

math.CO2026

On Edge-Disjoint Maximal Outerplanar Graphs

Yuto Okada, Yota Otachi, Lena Volk

We provide two constructions for $t$ edge-disjoint maximal outerplanar graphs on every number of $n \geq 4 t$ vertices. The bound on the minimum number of vertices is tight. These c…

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited

Tesshu Hanaka, Yuto Okada, Yota Otachi +1

We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete proble…

Forcing a unique minimum spanning tree and a unique shortest path

Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +7

A forcing set $S$ in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in $S$ . 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 $G = (V, E)$ , a set $T$ of vertex pairs, and an integer $k$ , Hitting Geodesic Intervals asks whether there is a set $S \subseteq V$ of size at most $k$ such that for e…

Finding Order-Preserving Subgraphs

Haruya Imamura, Yasuaki Kobayashi, Yota Otachi +5

(Induced) Subgraph Isomorphism and Maximum Common (Induced) Subgraph are fundamental problems in graph pattern matching and similarity computation. In graphs derived from time-seri…

Broadcasting under Structural Restrictions

Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7

In the Telephone Broadcast problem we are given a graph $G = (V, E)$ with a designated source vertex $s \in V$ . Our goal is to transmit a message, which is initially known only to $s$ ,…

math.CO2025

Interval Graphs are Reconstructible

Irene Heinrich, Masashi Kiyomi, Yota Otachi +1

A graph is reconstructible if it is determined up to isomorphism by the multiset of its proper induced subgraphs. The reconstruction conjecture postulates that every graph of order…

cs.DS2024

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…

cs.DS2024

Parameterized Spanning Tree Congestion

Michael Lampis, Valia Mitsou, Edouard Nemery +3

In this paper we study the Spanning Tree Congestion problem, where we are given a graph $G = (V, E)$ and are asked to find a spanning tree $T$ of minimum maximum congestion. Here, the…

cs.DS2024

Finding Induced Subgraphs from Graphs with Small Mim-Width

Yota Otachi, Akira Suzuki, Yuma Tamura

In the last decade, algorithmic frameworks based on a structural graph parameter called mim-width have been developed to solve generally NP-hard problems. However, it is known that…

math.CO2024

An improved spectral lower bound of treewidth

Tatsuya Gima, Tesshu Hanaka, Kohei Noro +2

We show that for every $n$ -vertex graph with at least one edge, its treewidth is greater than or equal to $n λ_{2} / (Δ + λ_{2}) - 1$ , where $Δ$ and $λ_{2}$ are the maximum degree a…

On the complexity of list $H$ -packing for sparse graph classes

Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +5

The problem of packing as many subgraphs isomorphic to $H \in H$ as possible in a graph for a class $H$ 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 $G$ contains another graph $H$ 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…

Finding a reconfiguration sequence between longest increasing subsequences

Yuuki Aoike, Masashi Kiyomi, Yasuaki Kobayashi +1

In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely Longest Increasing Subsequence Reco…

Minimum Consistent Subset for Trees Revisited

Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi +2

In a vertex-colored graph $G = (V, E)$ , a subset $S \subseteq V$ is said to be consistent if every vertex has a nearest neighbor in $S$ with the same color. The problem of computin…