Papers for

combinatorial game developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Fast method solves edge-claiming claw game on graphs with degree 4

A Linear-Time Algorithm for the Unbiased Claw Game on Graphs with Maximum Degree 4

Abstract: We study the unbiased Maker-Breaker $K_{1,3}$-game, the unbiased claw game, played on the edge set of a general graph $G$. In this game, Maker and Breaker alternatingly claim edges of $G$, and Maker wins if his claimed edges contain a claw once no more edges are available. Graphs with maximum degree at least 5 are Maker's win. A graph $G$ is claw-connected if the hypergraph modeling the unbiased claw game played on $G$ is connected. We characterize Maker's win in the unbiased claw game on every claw-connected graph whose maximum degree is different from 3. Our main structural result is a complete characterization of Maker's win for claw-connected graphs with exactly one vertex of degree 4. The analysis is based on the fact that vertices of degree 4 act as forcing structures. Our characterization results in a linear-time algorithm for the unbiased claw game on claw-connected graphs with maximum degree different from 3. We also obtain a linear-time decomposition algorithm reducing the game on general graphs to a collection of pairwise edge-disjoint claw-connected subgraphs of maximum degree exactly 3, thereby isolating the only remaining case. This decomposition yields an $\mathcal{O}(|V(G)|^3)$-time algorithm for the unbiased claw game on general graphs, improving on the $\mathcal{O}(|V(G)|^7)$-time algorithm implied by the work of Galliot, Gravier and Sivignon (arXiv 2026). For a lower bound on the decision complexity, we prove that any agent deciding the game in the adjacency-array model makes at least $Ω(|V(G)|)$ queries in the worst case, indicating the optimality of our linear-time algorithm.

Thu 15 OctDiscrete Mathematics
The gist
This work studies a game played on a network where two players alternately claim connections (edges). One player wins if they can form a specific small shape resembling a claw. The authors fully describe when this player can win on networks with nodes connecting up to four edges, focusing especially on networks with just one node connected to four others. They provide a quick, step-by-step method to decide the winner in these cases, and a way to break down any network into smaller parts so the problem can be solved more easily. They also show their method is as efficient as possible, needing only a number of checks proportional to the size of the network.
Open → 2610.21878v1