Extensions of Courcelle's Theorem without Logic

Abstract

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t(G)$, graph properties $\mathcal{P}$ definable in Monadic Second Order Logic can be checked in linear time in the size of $t(G)$. Inspired by L. Lovász' work using connection matrices instead of logic, we give a generalized version of Courcelle's theorem which replaces the definability hypothesis by a purely combinatorial hypothesis using a generalization of connection matrices. This paper clarifies the role of logic in such theorems and displays their purely combinatorial assumption.

17 pages. This is an expanded and improved version of arXiv:2505.02771