Parameterized Complexity of Elimination Distance to First-Order Logic Properties

Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

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 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 property P expressible by a first order-logic formula , that is, of the form where is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed , is fixed-parameter tractable parameterized by . Properties of graphs expressible by formulas from 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 , for which computing elimination distance is -hard.

Original languageEnglish (US)
Article number17
JournalACM Transactions on Computational Logic
Volume23
Issue number3
DOIs
StatePublished - Jul 2022

Keywords

  • descriptive complexity
  • elimination distance
  • First-order logic
  • parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Logic
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Parameterized Complexity of Elimination Distance to First-Order Logic Properties'. Together they form a unique fingerprint.

Cite this