Parameterized graph cleaning problems

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)||V(G)|−|V(H)| with HH and GG being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph GG, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph HH representing the original pattern. We show fixed-parameter tractability of the cases where both HH and GG are planar and HH is 3-connected, or HH is a tree and GG is arbitrary. We also prove that the problem when HH and GG are both 3-connected planar graphs is NP-complete without parameterization.