From Polynomial Time Queries to Graph Structure Theory

摘要

We give a logical characterization of the polynomial-time properties of graphs with excluded minors: For every class C of graphs such that some graph H is not a minor of any graph in C, a property V of graphs in C is decidable in polynomial time if and only if it is definable in fixed-point logic with counting. Furthermore, we prove that for every class C of graphs with excluded minors there is a k such that a simple combinatorial algorithm, namely "the k-dimensional Weisfeiler-Lehman algorithm," decides isomorphism of graphs in C in polynomial time.