Access Restriction

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

   Open content in new tab
Source: ACM Digital Library