CS Paper Radar

Nim heaps in the Game of Cycles: the parity conjecture fails on trees

Muchen Xu

cs.DM math.CO ·submitted 2026-10-10 19:44 UTC · v1
theory

Abstract

The Game of Cycles, invented by Francis Su, is a two-player game in which the players take turns drawing arrows on the edges of a plane graph, never creating a sink or a source. On a tree only the sink-source rule matters, and the player who makes the last move wins. Several authors conjectured that on a tree the second player wins exactly when the number of markable edges is even. We show that this parity conjecture is false, and we explain why. The explanation is a hidden game of Nim: a path segment that is blocked by an arrow at one end and free at the other behaves exactly like a nim heap whose size is its length. Combined with a calculus for cutting and gluing trees at vertices next to leaves, this shows that the conjecture fails as soon as a single tree has Grundy value at least 2. The smallest counterexamples have 15 vertices. Trees with Grundy values 2 and 4 first appear at 17 vertices, and every value up to 63 occurs, which answers a question of Fokkink and Zandee. We also refute a related conjecture of Zandee. We then look closely at spiders. The spiders S(2,3,z) violate the conjecture for every z >= 14. The Grundy values of S(1,2j,z) are given by an exact formula governed by binary carries. For 99 pairs (x,y), the value of S(x,y,z) is eventually the parity of z. On the positive side, the conjecture holds for all trees in which every thread has at most two edges, and this bound is sharp. Along the way we prove a twin-branch reduction, give an algorithm that is polynomial for spiders with a fixed number of legs, and collect the questions that we could not answer. The boldest asks whether every non-negative integer is the Grundy value of some tree.

Comment
35 pages, 3 figures, 7 tables. Ancillary files contain all programs and data

Closest papers

Nearest neighbours by meaning across the whole index.

Solving Streett and Emerson-Lei Games with Universal Trees

cs.GT cs.LO ·2026-08-17 ·Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
similarity 0.67
Abstract

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

0.18

Removing $m$ from $m$-pile Divisor Nim

cs.DM math.CO ·2026-10-03 ·Satyam Tyagi
theory similarity 0.66
Abstract · 23 pages, 15 tables

In Divisor Nim, a player removes from one heap a positive number of stones that divides the size of every other heap. We prove that the Sprague--Grundy (SG) value satisfies $g(P)\le 2h_{\min}+\lfloor\log_2h_{\min}\rfloor$, where $h_{\min}$ is the smallest nonempty heap, independently of the number and sizes of the other heaps. The proof starts with odd heaps and classifies removals by their factors of $2$. The largest heap in a starting board then supplies an SG bound valid throughout every successor chain. When one heap varies, we sharpen Morisawa's eventual-period bound: the smallest fixed heap controls the SG value range, the number of consecutive values compared, and an increase in the varying heap that repeats legal moves. The remaining dependence on the fixed board lies in the SG periods of direct successors. Using the largest fixed heap, we derive an explicit common period for all these recursive layers. Its possible prime divisors belong to a fixed finite set, independent of heap count; their exponents remain controlled by the total fixed stones. Finally, joining boards under one shared divisor rule preserves and can tighten the SG ceiling. Minimum 2-adic depth and its count parity determine every joined outcome, and a join with at least two odd heaps has exact SG value $0$ or $1$. We close with two conjectures: $g(P)\le2h_{\min}$, and that the least eventual SG period, when one heap varies, divides $2\operatorname{lcm}(1,\ldots,h_{\max})$. Here $h_{\max}$ is the largest fixed heap, excluding the varying heap. The second claim would remove heap-count dependence from the period bound as well.

0.30

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.64
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

Hull Games of Induced Path Convexities in Graphs

cs.DM math.CO ·2026-09-21 ·Eurinardo Costa, Leon Almeida, Rudini Sampaio
theory similarity 0.64
Abstract

In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_k}$ in the path $P_n$ if and only if $n$ is odd and she wins in the cycle $C_n$ if and only if $n=3$ or $n=α\cdot (k+1)-1$ with $α\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_k}$ in $P_n$ and in $C_n$ are periodic and Alice loses (resp. wins) in $P_n$ (resp. $C_n$) with $n>k$ only when $n=3k+4$ (resp. $n\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_2}$ in paths $P_n$ is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of $n$ up to $150$ million.

0.12

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.62
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15

The Complexity of Undirected Partizan Edge Geography

cs.DS math.CO ·2026-09-16 ·Yuto Okada
similarity 0.61
Abstract · 9 pages, 6 figures

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

0.53

Directed Cut-Query Complexity of Finding a King

cs.CC math.CO ·2026-10-29 ·Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
theory similarity 0.60
Abstract

A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is $Θ(n)$ for $n$-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.

0.34

Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number

cs.DM math.CO ·2026-09-18 ·Pierre Charbit, Samuel Coulomb
theory similarity 0.60
Abstract

In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

0.07