Determining a Slater Winner Is Complete for Parallel Access to NP
Lampis, Michael (2022), Determining a Slater Winner Is Complete for Parallel Access to NP, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 45:1–45:14. 10.4230/LIPIcs.STACS.2022.45
TypeCommunication / Conférence
External document linkhttps://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15855
Book title39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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.
Subjects / KeywordsSlater winner; Feedback Arc Set; Tournaments
Showing items related by title and author.