Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917452262146048 |
|---|---|
| author | Sau, Ignasi Schirrmacher, Nicole Siebertz, Sebastian Stamoulis, Giannos Thilikos, Dimitrios M. Vigny, Alexandre |
| author_facet | Sau, Ignasi Schirrmacher, Nicole Siebertz, Sebastian Stamoulis, Giannos Thilikos, Dimitrios M. Vigny, Alexandre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00192 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes Sau, Ignasi Schirrmacher, Nicole Siebertz, Sebastian Stamoulis, Giannos Thilikos, Dimitrios M. Vigny, Alexandre Logic in Computer Science Combinatorics 68R10, 05C75, 05C83, 05C85 F.4.1; F.2.2; G.2.2 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. |
| title | Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes |
| topic | Logic in Computer Science Combinatorics 68R10, 05C75, 05C83, 05C85 F.4.1; F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2605.00192 |