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.

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