Reducing CMSO to unbreakable graphs cannot be computable

Prelegent(ci)

Colin Geniet

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

14 października 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Reducing CMSO to unbreakable graphs cannot be computable

Seminarium

Seminarium „Teoria automatów”

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.