Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912250637320192 |
|---|---|
| author | Koepke, Finn Orson |
| author_facet | Koepke, Finn Orson |
| contents | Let $(X, \mathcal{F})$ be a hypergraph. The Maker-Breaker game on $(X, \mathcal{F})$ is a combinatorial game between two players, Maker and Breaker. Beginning with Maker, the players take turns claiming vertices from $X$ that have not yet been claimed. Maker wins if she manages to claim all vertices of some hyperedge $F \in \mathcal{F}$. Breaker wins if he claims at least one vertex in every hyperedge.
M. L. Rahman and Thomas Watson proved in 2021 that, even when only Maker-Breaker games on 6-uniform hypergraphs are considered, the decision problem of determining which player has a winning strategy is PSPACE-complete. They also showed that the problem is NL-hard when considering hypergraphs of rank 5.
In this paper, we improve the latter result by showing that deciding who wins Maker-Breaker games on 5-uniform hypergraphs is still a PSPACE-complete problem. We achieve this by polynomial transformation from the problem of solving the generalized geography game on bipartite digraphs with vertex degrees 3 or less, which is known to be PSPACE-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20271 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete Koepke, Finn Orson Discrete Mathematics Combinatorics 05C57 G.2.1 Let $(X, \mathcal{F})$ be a hypergraph. The Maker-Breaker game on $(X, \mathcal{F})$ is a combinatorial game between two players, Maker and Breaker. Beginning with Maker, the players take turns claiming vertices from $X$ that have not yet been claimed. Maker wins if she manages to claim all vertices of some hyperedge $F \in \mathcal{F}$. Breaker wins if he claims at least one vertex in every hyperedge. M. L. Rahman and Thomas Watson proved in 2021 that, even when only Maker-Breaker games on 6-uniform hypergraphs are considered, the decision problem of determining which player has a winning strategy is PSPACE-complete. They also showed that the problem is NL-hard when considering hypergraphs of rank 5. In this paper, we improve the latter result by showing that deciding who wins Maker-Breaker games on 5-uniform hypergraphs is still a PSPACE-complete problem. We achieve this by polynomial transformation from the problem of solving the generalized geography game on bipartite digraphs with vertex degrees 3 or less, which is known to be PSPACE-complete. |
| title | Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete |
| topic | Discrete Mathematics Combinatorics 05C57 G.2.1 |
| url | https://arxiv.org/abs/2502.20271 |