Two Problems at the Second Level of the Polynomial Hierarchy
Few natural problems are found in the second level of the polynomial hierarchy. In this thesis we examine k-choosability, a graph theory problem which is known to be Π2-complete; and transversal contraction, a matroid theory problem in Σ2. We obtain a classification of the 2-connected graphs with maximal local edge-connectivity k that are not k-choosable. This classification gives rise to a polynomial-time algorithm for recognising k-choosability among such graphs. We then show that when the input graph need not be 2-connected the problem becomes Π2-complete. We also obtain a polynomial-time algorithm to determine whether a 1-element contraction from a transversal matroid remains transversal. If the contraction is transversal our algorithm provides a representation.
