Connection matrices of finite rank instead of definability in Monadic Second Order Logic

ABSTRACT. Connection matrices for graphs and hypergraphs are a generalization of Hankel matrices for words. They were used by L. Lovasz and A. Schrijver and their collaborators to characterize which graph parameters arise from partition functions. Lovasz also noted that they can be used to make Courcelle's Theorem, which shows that graph properties definable in Monadic Second Order Logic (MSOL) are in FPT on graph classes of bounded tree-width, logic-free by replacing MSOL-definability by a finiteness condition on the rank of connection matrices and allowing graph parameters with values in a field. In this paper we extend this to graph parameters with values in a tropical semi-rings rather than a field, and graph classes of bounded clique-width.