Two Problems at the Second Level of the Polynomial Hierarchy

<p dir="ltr">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 Π₂-complete; and transversal contraction, a matroid theory problem in Σ₂. 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 Π₂-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.</p>