Avoider-Enforcer Game is NP-hard

August 13, 2022 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Tillmann Miltzow, Miloลก Stojakoviฤ‡ arXiv ID 2208.06687 Category cs.CC: Computational Complexity Cross-listed cs.DM, cs.DS, cs.GT, math.CO Citations 3 Venue arXiv.org Last Checked 2 months ago
Abstract
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.
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity