The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problems fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: for every graph property P expressible by a first order-logic formula phiin Sigma_3, that is, of the form phi=exists x_1exists x_2cdots exists x_r forall y_1forall y_2cdots forall y_s exists z_1exists z_2cdots exists z_t psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma_3 include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: there are formulas phiin Pi_3, for which computing elimination distance is W[2]-hard.
Download