Reducing CMSO to Unbreakable Graphs Cannot be Computable

2026/08/04 by Colin Geniet, Roohani Sharma
Computer Science · Mathematics · #cs.DM #cs.CC #cs.LO #math.CO

paper · pdf

7 pages to appear at ESA 26

arxiv created 2026/08/04 · arxiv updated 2026/08/05

Abstract

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula ϕ, testing ϕ on arbitrary graphs can be reduced to testing it on (q,k)-unbreakable graphs for appropriate parameters. Their proof is non-constructive, and they ask whether it can be made constructive. We prove that this is impossible: specifically, the parameter q cannot be a computable function of ϕ.

Citations

• H-Planarity and Parametric Extensions: when Modulators Act Globally
• FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
• Deletion to Scattered Graph Classes I -- case of finite number of graph classes
• Reducing CMSO Model Checking to Highly Connected Graphs
• Path-contractions, edge deletions and connectivity preservation
• Designing FPT algorithms for cut problems using randomized contractions
• Minimum k-way cut of bounded size is fixed-parameter tractable
• Finding topological subgraphs is fixed-parameter tractable