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
Open Access
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.
graph minors, obstruction sets, polynomial hierarchy