论文标题
制造商破坏者在等级3的多项式时间内解决
Maker-Breaker is solved in polynomial time on hypergraphs of rank 3
论文作者
论文摘要
在制造商的位置游戏中，制造商和Breaker轮流选择了HyperGraph $ h $的顶点，并且当她拥有$ H $的所有边缘的所有顶点时，制造商才能获胜。决定结果（即哪个球员具有获胜策略），即使仅限于5均匀的超图（Koepke，2025年），也是Pspace的完整。在等级3的超图上，对结果和多项式时间算法的结构表征已经获得了两个子案例：一个由Kutz（2005）由Rahman and Watson（2020）撰写的，另一个由Rahman和Watson（2020）猜测，他们的结果应推广到该级别的所有高度绘制的策略。某些关键的亚液质收集的相交，我们从中得出了多项式时间算法。我们结构性结果的另一个推论是，如果Maker在排名第3的超图中具有获胜的策略，那么她可以确保以对数角度对数的许多回合赢得比赛。注意：本文提供了与类似结果的反例，该结果被错误地宣称（ARXIV：2209.11202，定理22）。
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 PSPACE-complete even when restricted to 5-uniform hypergraphs (Koepke, 2025). On hypergraphs of rank 3, a structural characterization of the outcome and a polynomial-time algorithm have been obtained for two subcases: one by Kutz (2005), the other by Rahman and Watson (2020) who conjectured that their result should generalize to all hypergraphs of rank 3. We prove this conjecture through a structural characterization of the outcome and a description of both players' optimal strategies, all based on intersections of some key subhypergraph collections, from which we derive a polynomial-time algorithm. 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 in a number of rounds that is logarithmic in the number of vertices. Note: This paper provides a counterexample to a similar result which was incorrectly claimed (arXiv:2209.11202, Theorem 22).
