On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos · arXiv (Cornell University) · 2018
We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula \\phi for the problem to be fixed-parameter tractable or to admit a polynomial kernel.