On the Parameterized Complexity of Graph Modification to First-Order Logic Properties

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula φ, 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 φ. We provide sufficient and necessary conditions on the structure of the prefix of φ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.