|
Too Many Minor Order Obstructions (For Parameterized Lower Ideals)
Michael J. Dinneen (Department of Computer Science, University of Auckland, New Zealand)
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
Categories: F.4, F.m, G.2
|
