We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP‐hardness of this problem, and we prove fixed‐parameter tractability of the problem with non‐standard parameterization, where the parameter is the difference |V(G)|−|V(H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as ‘cleaning’ the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]‐hardness for the standard parameterization where the parameter is |V(H)|.
