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

Discrete Mathematics

Summary

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.

What this means in practice

  • For network algorithm designers: Enable efficient algorithms to quickly determine winning strategies in network edge-selection games involving claw structures.
  • For combinatorial game developers: Design game AI that computes moves faster by exploiting structures in graphs with bounded maximum degree to decide outcomes of edge-claiming games.

Authors

Julian Christoph Brinkmann

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.