Paper: Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes (at LICS 2026)

Authors: Ignasi Sau Nicole Schirrmacher Sebastian Siebertz Giannos Stamoulis Dimitrios M. Thilikos Alexandre Vigny

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.80

Abstract

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

BibTeX

  @InProceedings{SauSchirrmacherSieb-ModelCheckingforLow,
    author = 	 {Ignasi Sau and Nicole Schirrmacher and Sebastian Siebertz and Giannos Stamoulis and Dimitrios M. Thilikos and Alexandre Vigny},
    title = 	 {Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {80:1--80:27},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.80}
  }