Abstract
We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula $\varphi$, we consider the problem of deciding whether an input graph can be modified by removing/adding at most $k$ vertices/edges such that the resulting modification has the property expressible by $\varphi$. We provide sufficient and necessary conditions on the structure of the prefix of $\varphi$ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by $k$) and when it admits a polynomial kernel.