Compound Logics for Modification Problems

Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply.

Original languageEnglish (US)
Title of host publication50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
EditorsKousha Etessami, Uriel Feige, Gabriele Puppis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772785
StatePublished - Jul 2023
Event50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany
Duration: Jul 10 2023Jul 14 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023


  • Algorithmic meta-theorems
  • First-order logic
  • Flat Wall theorem
  • Graph minors
  • Graph modification problems
  • Irrelevant vertex technique
  • Model-checking
  • Monadic second-order logic

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Compound Logics for Modification Problems'. Together they form a unique fingerprint.

Cite this