Fixed-point definability and polynomial time on graphs with excluded minors
Martin Grohe · Journal of the ACM · 2012
We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surfaceS, a property P of graphs embeddable inSis decidable in polynomial time if and only if it is definable in fixed-point logic with counting. It is a consequence of this result that for every surfaceSthere is aksuch that a simple combinatorial algorithm, namely “thek-dimensional Weisfeiler-Lehman algorithm”, decides isomorphism of graphs embeddable inSin polynomial time. We also present (without proof) generalizations of these results to arbitrary classes of graphs with excluded minors.