Hardness of monadic second-order formulae over succinct graphs

Logical Methods in Computer Science 2026 Open access

Read full text
Authors: Guilhem Gamard, Aliénor Goubault–Larrecq, P. Guillon, Pierre Ohlmann, Kévin Perrot, Guillaume Theyssier
DOI: 10.46298/lmcs-22(1:3)2026
Cited by: 0
References: 22

Abstract

Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.

Fields of Study & Subjects

Graph theory and applications Graph Labeling and Dimension Problems Advanced Graph Theory Research

Publication details

Journal / source
Logical Methods in Computer Science
Publisher
Centre pour la Communication Scientifique Directe (CCSD)
Volume
Volume 22, Issue 1
Publication date
6 January 2026
Language
EN