Compact Labelings For Efficient First-Order Model-Checking

Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checki…