5 citations · 14 across the 32 of their papers we have counts for
Showing 2026 · cs.DSShow all
3 papers · 2 filters
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
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…