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 P of graphs in C is decidable in polynomial time if and only if it is definable in fixed-point logic wi...
| Publicado en: | Communications of the ACM Vol. 54; no. 6; pp. 104 - 113 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Jun2011
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | 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 P 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 κ such that a simple combinatorial algorithm, namely "the κ-dimensional Weisfeiler--Lehman algorithm," decides isomorphism of graphs in C in polynomial time. |
|---|