JUCS - Journal of Universal Computer Science 3(11): 1199-1206, doi: 10.3217/jucs-003-11-1199
Too Many Minor Order Obstructions (For Parameterized Lower Ideals)
expand article infoMichael J. Dinneen‡
‡ Department of Computer Science, University of Auckland, Auckland, New Zealand

Corresponding author: Michael Dinneen ( mjd@cs.auckland.ac.nz )

© Michael Dinneen.
This article is freely available under the J.UCS Open Content License.
Citation: Dinneen MJ (1997) Too Many Minor Order Obstructions (For Parameterized Lower Ideals). JUCS - Journal of Universal Computer Science 3(11): 1199-1206. https://doi.org/10.3217/jucs-003-11-1199
Open Access
Abstract
We study the growth rate on the number obstructions (forbidden minors) for families of graphs that are based on parameterized graph problems. Our main result shows that if the defining graph problem is NP-complete then the growth rate on the number of obstructions must be super-polynomial or else the polynomial-time hierarchy must collapse to . We illustrate the rapid growth rate of parameterized lower ideals by computing (and counting) the obstructions for the graph families with independence plus size at most . 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
Keywords
graph minors, obstruction sets, polynomial hierarchy