Abstract:In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph $H$, and Maker wins if and only if she possesses all the vertices of some edge of $H$. Deciding the outcome (i.e., which player has a winning strategy) is a PSPACE-complete problem even when restricted to 4-uniform hypergraphs [Galliot, 2025]. As for hypergraphs of rank 3, the linear subcase (i.e., any two distinct edges intersect on at most one vertex) has been solved by obtaining a structural characterization of the outcome and a polynomial-time algorithm to decide it [Kutz, 2005]. A conjecture [Rahman and Watson, 2020] implies that the same results can be obtained for general hypergraphs of rank 3, which we confirm in this paper. We provide a structural characterization of the outcome and a description of both players' optimal strategies, all based on intersections of some key subhypergraph collections. From this, we derive a polynomial-time algorithm, thus closing the complexity gap for Maker-Breaker games relative to the size of the edges. Another corollary of our structural result is that, if Maker has a winning strategy on a hypergraph of rank 3, then she can ensure to win the game within a number of rounds that is logarithmic in the number of vertices.
From: Florian Galliot [view email]
[v1]
Mon, 26 Sep 2022 16:26:40 UTC (951 KB)
[v2]
Thu, 10 Nov 2022 16:02:32 UTC (956 KB)
[v3]
Mon, 24 Mar 2025 15:21:40 UTC (968 KB)
[v4]
Sat, 11 Jul 2026 15:41:08 UTC (984 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。