# zbMATH — the first resource for mathematics

On polynomial time decidability of induced-minor-closed classes. (English) Zbl 0668.68048
It follows from recent results of Robertson and Seymour that for any minor-closed class of graphs $${\mathcal F}$$ (i.e. $$G\in {\mathcal F}$$ and H minor of G implies $$H\in {\mathcal F})$$ there is a polynomially (in fact $$O(| V(G)|^ 3))$$ bounded algorithm for the membership problem of $${\mathcal F}$$. We investigate this property for a weaker notion of induced-minor- closed classes. There is a linear algorithm if the class $${\mathcal F}$$ consists of series-parallel graphs (i.e., those which contain no subdivision of $$K_ 4)$$. However, for induced minor-closed classes in general this problem may be NP-hard or even algorithmically undercidable.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 05C99 Graph theory