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 phi, 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 phi. We provide sufficient and necessary conditions on the structure of the prefix of phi specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.