6-uniform Maker-Breaker game is PSPACE-complete

DOI10.1007/S00493-023-00026-7MaRDI QIDQ6081384zbMATH OpenFDO

Authors

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00493-023-00026-7

zbMATH Keywords

complexitygameMaker-BreakerNL-hardPSPACE-completereduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The paper deals with the problem of determining the winner of a Maker-Breaker game. In this kind of game, a set of subsets is given, which elements all belong to a finite universe set. At each turn, one player seizes one element among those that were not selected in previous steps. The Maker wins if he is able to select every element of at least one subset. The Breaker wins if he can select at least one element for each subset. \par The winner individuation problem was proved PSPACE-complete in a 1976 paper by Schaefer for games in which subsets are bound to have size not exceeding 11. In this paper the authors significantly improve the result by proving the PSPACE-completeness of the problem when the maximum subset size is limited to 6. Moreover, the authors also provide NL-hardness results for some simpler game cases.\par The paper basically consists of the results, proofs, it is opened by a very nice introduction where the problem is stated and some relevant literature is referred to and is closed by a brief section restating the problem resulting state of the art so that open cases are clearly pinpointed.\par Overall, a paper certainly worth reading.

Recommendations

• Maker-Breaker domination game
• On the complexity of chooser-picker positional games
• scientific article; zbMATH DE number 7650369
• Phutball is PSPACE-hard
• The set coincidence game: Complexity, attainability, and symmetric strategies
• On two theorems of positional games
• On chooser-picker positional games
• Multivision: An Intractable Impartial Game with a Linear Winning Strategy

Cited in

(12)

• The maker-maker domination game in forests
• The cordiality game and the game cordiality number
• Complexity of maker-breaker games on edge sets of graphs
• Solving Maker-Breaker games on 5-uniform hypergraphs is PSPACE-complete
• Maker-breaker resolving game played on corona products of graphs
• Maker-Breaker domination game played on corona products of graphs
• Maker-Breaker domination game critical graphs
• Poset positional games
• Tic-Tac-Toe on designs
• The Avoider-Enforcer game in hypergraphs of rank 3
• Maker-breaker total domination number
• On Maker-Breaker domination game critical graphs

This page was built for publication: 6-uniform Maker-Breaker game is PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081384)