Reducing CMSO to unbreakable graphs cannot be computable

Speaker(s)

Colin Geniet

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 14, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Reducing CMSO to unbreakable graphs cannot be computable

Seminar

Seminar Automata Theory

In groundbreaking work, Lokshtanov, Ramanujan, Saurabh, and Zehavi
[ICALP '18] proved that for any fixed Counting MSO formula φ, testing φ on arbitrary graphs can be reduced to testing φ on highly-connected graphs, in the sense of unbreakability.

We prove that the unbreakability parameters in this theorem are
unfortunately inherently uncomputable. But this is mostly an excuse to
present the LRSZ result.

This is joint work with Roohani Sharma.