1 citations · 1 across the 26 of their papers we have counts for
33 papers · 1 filter
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 . For I…
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…
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 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…