### Fixed-point definability and polynomial time on graphs with excluded minorsFixed-point definability and polynomial time on graphs with excluded minors

Access Restriction
Subscribed

 Author Grohe, Martin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2012 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Descriptive complexity ♦ Fixed-point logics ♦ Graph isomorphism ♦ Graph minors Abstract We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface $\textit{S},$ a property P of graphs embeddable in $\textit{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 $\textit{S}$ there is a $\textit{k}$ such that a simple combinatorial algorithm, namely “the $\textit{k}-dimensional$ Weisfeiler-Lehman algorithm”, decides isomorphism of graphs embeddable in $\textit{S}$ in polynomial time. We also present (without proof) generalizations of these results to arbitrary classes of graphs with excluded minors. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2012-11-05 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 59 Issue Number 5 Page Count 64 Starting Page 1 Ending Page 64

#### Open content in new tab

Source: ACM Digital Library