Avoider-Enforcer Game is NP-hard

Till Miltzow; Milos Stojakovic

doi:10.48550/arXiv.2208.06687

Avoider-Enforcer Game is NP-hard

Till Miltzow, Milos Stojakovic

Research output: Working paper › Preprint › Academic

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.

Original language	English
Publisher	arXiv
Pages	1-8
DOIs	https://doi.org/10.48550/arXiv.2208.06687
Publication status	Published - 2022

Access to Document

10.48550/arXiv.2208.06687Licence: CC BY

2208.06687Submitted manuscript, 518 KBLicence: CC BY

Cite this

@techreport{0dd9ac07a5b44c619eebaf9d2cec03d6,

title = "Avoider-Enforcer Game is NP-hard",

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.",

author = "Till Miltzow and Milos Stojakovic",

year = "2022",

doi = "10.48550/arXiv.2208.06687",

language = "English",

pages = "1--8",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Avoider-Enforcer Game is NP-hard

AU - Miltzow, Till

AU - Stojakovic, Milos

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

U2 - 10.48550/arXiv.2208.06687

DO - 10.48550/arXiv.2208.06687

M3 - Preprint

SP - 1

EP - 8

BT - Avoider-Enforcer Game is NP-hard

PB - arXiv

ER -

Avoider-Enforcer Game is NP-hard

Abstract

Access to Document

Fingerprint

Cite this