一句话：刻画了到一阶逻辑可定义图性质的消除距离问题的固定参数可解性边界：Σ3 公式可 FPT，Π3 公式则 W[2]-难。
本文研究图到目标图性质 P 的消除距离这一图修改参数的参数化复杂度，其中 P 由一阶逻辑公式定义。作者通过分析一阶逻辑公式量词前缀的结构，给出了判定消除距离是否不超过 k 的固定参数可解性的充分必要条件。主结果是元定理：若 P 可由 Σ3 公式表达，即形如 ∃*∀*∃* 且无量词体，则到 P 的消除距离问题以 k 为参数是固定参数可解的；该结果涵盖有界度、禁用子图和有界支配集等性质。作为补充，作者证明存在 Π3 公式使该问题 W[2]-难，表明量词前缀稍强即会破坏一般 FPT 性。
The elimination distance to some target graph propertyPis 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 problem's 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 propertyPexpressible by a first order-logic formula φ ∈ Σ3, that is, of the form φ = ∃x1∃x2⋯∃xr∀y1∀y2⋯∀ys∃z1∃z2⋯∃ztψ, where ψ is a quantifier-free first-order formula, checking whether the elimination distance of a graph toPdoes not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Σ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 φ ∈ Π3, for which computing elimination distance is W[2]-hard.
@inproceedings{paperbot6188,
title = {Parameterized Complexity of Elimination Distance to First-Order Logic Properties},
author = {Fedor V. Fomin and Petr A. Golovach and Dimitrios M. Thilikos},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470540}
}