  For intractable problems on graphs of bounded treewidth, two graph parameters
treedepth and vertex cover number have been used to obtain fine-grained
complexity results. Although the studies in this direction are successful, we
still need a systematic way for further investigations because the graphs of
bounded vertex cover number form a rather small subclass of the graphs of
bounded treedepth. To fill this gap, we use vertex integrity, which is placed
between the two parameters mentioned above. For several graph problems, we
generalize fixed-parameter tractability results parameterized by vertex cover
number to the ones parameterized by vertex integrity. We also show some finer
complexity contrasts by showing hardness with respect to vertex integrity or
treedepth.
