Deletion problems are those where given a graph $G$ and a graph property $\pi$, the goal is to find a subset of vertices (or edges) such that after its removal the graph $G$ will satisfy the property $\pi$. Typically, we want to minimize the number of elements removed. In fair deletion problems we change the objective: we minimize the maximum number of deletions in a neighborhood of a single vertex.

We study the parameterized complexity of fair deletion metatheorems, where a graph property is expressed in a certain graph logic, with respect to several structural parameters of the graph.

The list of our results for the Vertex Deletion problem: The problem is $\mathrm{W}[1]$-hard on tree-depth for any logic that can express the edgeless graph. The problem has an FPT algorithm for $\mathrm{MSO}_1$ logic on graphs with bounded neighborhood diversity, or bounded twin cover.

The list of our results for the Edge Deletion problem: The problem is $\mathrm{W}[1]$-hard on tree-depth for First order logic. The problem has an FPT algorithm for $\mathrm{MSO}_2$ logic on graphs with bounded vertex cover.

This is joint work with Dušan Knop and Tomáš Toufar. Research partly supported by the CE-ITI grant project P202/12/G061 of GA ČR and by GAUK project 1784214.