2026/08/04 by Tomohiro Koana, Soh Kumabe, Yota Otachi
Computer Science · #cs.DS
arxiv created 2026/08/04 · arxiv updated 2026/08/05
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 ISI, we give a randomized O^*(kO(k))-time algorithm, showing that ISI is fixed-parameter tractable under this parameter and resolving an open question of Hanaka et al. [WALCOM 2026]. Our algorithm is optimal under the Exponential Time Hypothesis (ETH), and is based on a reduction to Exact Multicolored Matching solvable via algebraic techniques. For MCIS, we present a randomized O^*(2O(k2))-time algorithm via a reduction to a weighted variant of Exact Multicolored Matching, and we prove a matching ETH-based lower bound by showing that a k-by-k binary matrix feasibility problem with list-constrained rows and columns admits no O^*(2o(k2))-time algorithm, which may be of independent interest. These results reveal that, in this setting, MCIS is strictly harder than ISI. Finally, for the three-graph variant 3-MCIS, we show that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.