Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors
We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface S, a property P of graphs embeddable in S is 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 surface S there is a k such that a simple combinatorial algorithm, namely "the k-dimensional Weisfeiler-Lehman algorithm", decides isomorphism of graphs embeddable in S in polynomial time. We also present (without proof) generalizations of these results to arbitrary classes of graphs with excluded minors.
fixed-point logics algorithms theory descriptive complexity graph minors graph isomorphism