Determining a Slater Winner Is Complete for Parallel Access to NP

We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament T = (V,A), where the vertices of V represent candidates and the direction of each arc indicates which of the two endpoints is preferable for the majority of voters. The Slater score of a vertex v ? V is defined as the minimum number of arcs that need to be reversed so that T becomes acyclic and v becomes the winner. We say that v is a Slater winner in T if v has minimum Slater score in T. Deciding if a vertex is a Slater winner in a tournament has long been known to be NP-hard. However, the best known complexity upper bound for this problem is the class ??^p, which corresponds to polynomial-time Turing machines with parallel access to an NP oracle. In this paper we close this gap by showing that the problem is ??^p-complete, and that this hardness applies to instances constructible by aggregating the preferences of 7 voters