On polynomial time decidability of induced-minor-closed classes
Jiřı́ Matoušek, Jaroslav Nešetřil, Robin D. Thomas · Czech digital mathematics library · 1988
It follows from recent results of Robertson and Seymour that for any minor-closed class of graphs &" (i.e.G e *& and H minor of G implies H € ^ ) there is a polynomially (in fact 0(|V(G)| )) bounded algorithm for the membership problem of ^.We investigate this property for a weaker notion of induced-minor-closed classes.There is a linear algorithm if the class f£ consists of series-parallel graphs (i.e.those which contain no subdivision of K,).However, for induced minor-closed classes in general this problem may be NP-hard or even algorithmically undecidable.