(Dinneen [222]) Let γ(G) ≤ p(|G|) map graphs to integers, where
p is some bounding polynomial. Assume Fk = {G | γ(G) ≤ k} is a minor-order
lower ideal. Also let pγ (G,k) denote the corresponding graph problem that determines if γ(G) ≤ k where both G and k are part of the input.
Show that if pγ (G,k) is NP-complete then fk = |O(Fk)| must be superpolynomial else the polynomial-time hierarchy PH collapses to ΣP
3 .
(Hint. Use the Yap Theorem, Theorem 1.2.1.)