2022/08/13 by Tillmann Miltzow, Miltzow, Tillmann, Miloš Stojaković +1
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2208.06687
openalex publication_date 2022/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforcer wins if Avoider claims all vertices of an edge; Avoider wins otherwise. We show that it is NP-hard to decide if Avoider has a winning strategy.