Set graphs are not definable in MSO1

• Bruno Bandeira UFRJ
• Márcia R. Cerioli UFRJ
• Petrucio Viana UFF

DOI: https://doi.org/10.5753/etc.2026.21684

Resumo

We prove that the property of being a set graph cannot be expressed in MSO₁, the language of Monadic Second Order Logic with quantification over sets of vertices, but not sets of edges. Hence, Courcelle’s Theorem relating MSO₁ and clique-width cannot be applied to the set graph recognition problem.

Referências

Courcelle, B. (1990). Graph rewriting: An algebraic and logic approach. In van Leeuwen, J., editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 193–242. Elsevier and MIT Press.

Courcelle, B. and Engelfriet, J. (2012). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press.

Courcelle, B., Makowsky, J. A., and Rotics, U. (2000). Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125–150.

Milanič, M. and Tomescu, A. I. (2013). Set graphs. I. Hereditarily finite sets and extensional acyclic orientations. Discrete Applied Mathematics, 161(4-5):677–690.

Milanič, M., Rizzi, R., and Tomescu, A. I. (2014). Set graphs. II. Complexity of set graph recognition and similar problems. Theoretical Computer Science, 547:70–81.

Monteiro, B. B. (2022). On the complexity of the set graph recognition problem restricted to cographs and split graphs. Master’s thesis, UFRJ.

Tomescu, A. I. (2011). Sets as Graphs. PhD thesis, Università degli Studi di Udine, Italy.