Too Many Minor Order Obstructions (For Parameterized Lower Ideals)
Дата
Авторы
Dinneen,Michael
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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