{"id":"arxiv/2608.03144","url":"https://arxiv.org/abs/2608.03144","tags":["cs.DM","cs.CC","cs.LO","math.CO"],"score":0,"title":"Reducing CMSO to Unbreakable Graphs Cannot be Computable","domain":"cs.DM","source":"arxiv","authors":["Colin Geniet","Roohani Sharma"],"reviews":0,"subject":"cs.DM","summary":"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 $φ$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-04","reactions":{}}