Hull Games of Induced Path Convexities in Graphs

Eurinardo Costa; Leon Almeida; Rudini Sampaio

Source-linked AI summary

Hull Games of Induced Path Convexities in Graphs

Eurinardo Costa, Leon Almeida, Rudini Sampaio

arXiv:2609.30302v3Sep 21, 2026cs.DMmath.CO

TL;DR

The paper investigates hull games on induced-path convexities, focusing on their complexity and winner determination. It combines complexity results with Sprague-Grundy analysis, proving hardness at diameter at most 3 and identifying tractable graph families and special parameter cases.

Problem
The paper investigates hull games on induced-path convexities, asking about their computational complexity and winner determination.
Source: §1 · p. 2
Method
The paper studies monophonic and ℓ_k hull games and applies Sprague-Grundy theory to analyze winner determination on paths, cycles, and their disjoint unions.
Source: §1 · p. 2
Results
The games are PSPACE-complete at diameter at most 3, while ℓ2 path nimbers match shifted Couples-are-Forever sequences with 99.9727% agreement across 100 million positions.
Source: §1 · pp. 2–3
Takeaways & Limitations
Polynomial-time winner decisions hold for disjoint unions of paths and cycles, with exact criteria for odd k and periodicity results for selected even k.
Source: §1 · p. 2
Whether the ℓ2 path nimber sequence is eventually periodic and whether its 12 losing positions can be characterized without exhaustive search remain open.
Source: §8 · p. 21

Abstract

from arXiv · show

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\'ujo 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\`ere 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=\alpha\cdot (k+1)-1$ with $\alpha\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 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 $100$ million.

1 Introduction

The paper extends hull-game research from geodesic convexity to induced-path convexities, establishing complexity and tractability results alongside nimber classifications for paths and cycles. It also connects the ℓ2 path game to Couples-are-Forever, whose periodicity remains open.

1 Introduction

The hull games CHGm, CHGℓk, and their misère variants are PSPACE-complete for every k ≥2, with the normal games remaining hard at diameter at most three.Source: §1 · p. 2
Sprague-Grundy Theory yields polynomial-time winner decisions for CHGm and CHGℓk on disjoint unions of paths and cycles; CHGm is won by Alice exactly when the number of odd paths and triangles is odd.Source: §1 · p. 2
For odd k ≥3, Alice wins CHGℓk on Pn exactly when n is odd, and on Cn exactly when n = 3 or n = α·(k+1)−1 for α ≥2.Source: §1 · p. 2
For k = 2^h−4 with h ≥3, the path and cycle nimber sequences are periodic, with Alice’s losses on paths and wins on cycles for n > k confined to stated exceptional values.The exceptional path value is n = 3k+4; the cycle values are n ∈ {2k+1, 5k+3}.Source: §1 · p. 2
For k = 2, the path game’s nimbers closely track Couples-are-Forever: the sequences differ at 27,304 of the first 100 million positions, and Alice loses at only 12 values of n in that range.Source: §1 · pp. 2–3
For cycles C_n, Alice wins for only 13 values of n.Source: §1 · p. 3

2 Hull games are PSPACE-hard

The section establishes PSPACE-completeness for normal and misère hull games, using reductions from Clique Forming. The normal-game hardness holds at diameter at most three, while the misère result holds at diameter at most two.

2 Hull games are PSPACE-hard

CHGℓk, CHGm, and CHGg are PSPACE-complete at diameter at most three for every k ≥2.Source: §2 · p. 3
The hardness reductions start from Clique Forming; for k ≥3 or monophonic convexity, the construction adds five vertices to H and controls the induced paths that can extend beyond length two.For ℓ2, the proof instead relies on the earlier diameter-two reduction, whose relevant induced paths are geodesics of length two.Source: §2 · pp. 3–4
The misère games CHGℓk and CHGm are PSPACE-complete at diameter at most two for every k ≥2.Source: §2 · p. 4
The misère proof follows [3, Thm. 3.1]: universal vertices ensure every vertex can be reached by induced paths of length two, even if H contains longer induced paths.Source: §2 · p. 4

3 Hull games are polynomial in paths and cycles

Sprague-Grundy nimbers reduce winner decisions on paths, cycles, and their disjoint unions to polynomial-time computation. For these path convexities, hull and interval games coincide, so the results apply to both.

3 Hull games are polynomial in paths and cycles

The nimber of a sum of disjoint impartial positions is the bitwise XOR of their nimbers, and the first player wins exactly when the resulting nimber is positive.Source: §3 · p. 5
On paths and cycles, hull and interval games coincide for monophonic and ℓk convexities, so the stated results also apply to CIGm and CIGℓk.Source: §3 · p. 5
For CHGm, Alice wins on a path exactly when its vertex count is odd, while on cycles she wins only on C3.Source: §3 · p. 5
For every k ≥2, the nimber of CHGℓk on a cycle is 1 for n = 3, 0 for 4 ≤n ≤2k, and otherwise determined by mex of the corresponding path-position nimber; it is computable in quadratic time.Source: §3 · p. 6

4 Nimbers of the hull game in convexity ℓk

The section develops nimber results for ℓk hull games on paths, including an explicit formula for a path position with both endpoints selected. The proof proceeds by induction using mex recurrences.

4 Nimbers of the hull game in convexity ℓk

The reported values are 0 for n < k + 1 and n%(k + 1) for n ≥ k + 1.Source: §4 · p. 7
The proof uses induction and the mex recurrence, dividing the argument into ranges around k+1, 2k+2, and 3k+2.Source: §4 · p. 7
For the inductive range n ∈ {2k+3, …, 3k+2}, parity of the XOR terms rules out the candidate remainder r = n%(k+1) from the mex.Source: §4 · p. 7

5 Hull game in convexity ℓ2 and the game Couples-are-Forever

For k = 2, the path hull game's nimber sequence is closely related to Couples-are-Forever, whose periodicity remains open. Computations up to 100 million positions show near agreement after a shift, while Alice loses on only 12 path sizes.

Whether the Couples-are-Forever nimber sequence is periodic remains an open problem; Alice loses for only 14 values of n up to 100 million.Source: §5 · p. 8
Up to a shift of one position, Couples-are-Forever matches the nimber sequence for paths with one or two endpoints preselected.Source: §5 · p. 8
For every n, the path-game nimber nimℓ2(Pn) is either CFn+2 or CFn+3; thus it is bounded above by CFn+3, with CFn+2 the only possible smaller value.Source: §5 · p. 8
The paper relates the path-game nimber to Couples-are-Forever through a mex recurrence whose candidate values are XORs of smaller heap nimbers.The recurrence's only potentially missing value is CFn+2, which explains why the path nimber is either CFn+3 or CFn+2.Source: §5 · p. 8
For n up to 100 million, Alice loses CHGℓ2 on paths for only 12 values of n and wins on cycles for only 13.Source: §5 · p. 9

6 Hull game in convexity ℓk with k odd

For odd k, the paper establishes periodic nimber sequences for the ℓk games and derives exact winner conditions for paths and cycles. On paths, Alice wins exactly when n is odd; on cycles, she wins only at the stated sizes.

The nimber sequences for these path and cycle games are periodic when k is odd.Source: §6 · p. 9
The section also gives nimber sequences for the endpoint-modified paths P′n and P″n when k is odd.The supplied sequence fragments include values indexed by n and k.Source: §6 · p. 10
For odd k, Alice wins CHGℓk on Pn if and only if n is odd.The path nimber is 0 for even n and 1 for odd n.Source: §6 · pp. 10–11
For odd k, Alice wins CHGℓk on Cn exactly when n = 3 or n = α·(k+1)−1 for α ≥ 2.Source: §6 · p. 11

7 Hull game in convexity ℓk with k even

This section studies nimber sequences for even k in the ℓ_k hull game, focusing on the family k = 2^h − 4 and a blockwise analysis of the path sequence. It proves periodicity for the path sequence, identifies its only zero nimber for n > k, and gives cycle-game outcomes.

7 Hull game in convexity ℓk with k even

Computational experiments found periodic nimℓk(Pn) sequences for even k only when k = 2^h − 4 with h ≥ 3, including k = 4, 12, 28, 60, 124, and 252.Source: §7 · p. 11

7.1 Nimbers of P′n and P′′n in CHGℓk with k = 2^h − 4 and h ≥ 3

For k = 2^h − 4, nimℓk(P′′n) equals n modulo k + 1 for n ≥ 3k + 4, except it is 0 at n = 5k + 4.Up to n = 3k + 3, the same residue rule holds except at n = 3(k + 1), where the value is k + 1 instead of 0.Source: §7 · p. 12
For k = 2^h − 4 with h ≥ 3, the nimber sequences for P′n and P′′n have period k + 1, with transients of lengths 4k + 4 and 5k + 4, respectively.Their zero nimbers occur only at n = 1, k + 2, or 4k + 4 for P′n, and at n ≤ k + 1, n = 2k + 2, or n = 5k + 4 for P′′n.Source: §7 · p. 13
For k = 2^h − 4 and n > k, Alice wins CHGℓk on Cn exactly when n is 2k + 1 or 5k + 3.Source: §7 · p. 13

7.2 Nimbers of Pn in CHGℓk with k = 2^h − 4 and h ≥ 3

For Pn, Block 1 alternates 0 and 1 by parity, Block 2 has values 1, 2, 2 at n = k + 1, k + 2, k + 3, and Block 3 repeats 11331122.The subsection’s roadmap divides the sequence into six transient blocks totaling 3k + 5 terms, followed by a periodic tail.Source: §7 · pp. 14–16, Table 1 · p. 14

Boundary blocks

The boundary values are 1, 1, 1, 2, 2 for P2k through P2k+4, and 1, 1, 3, 0, 2 for P3k+1 through P3k+5.These include the sole zero nimber after n > k, at n = 3k + 4.Source: §7 · pp. 17–18

Path nimbers before the periodic tail

For 0 ≤ t ≤ 8b − 1 = k − 5 and n = 2k + 5 + t, nimℓk(P_n) = B[t%8], where B = (1, 1, 3, 3, 1, 1, 2, 2).Source: §7 · p. 17

Periodic tail

For n ≥ 3k + 6, the nimbers repeat the block B^bC, where B = 11331122 and C = 11323.The periodic tail is [B^bC]*, with b = (k − 4)/8.Source: §7 · pp. 19–21
For k = 2^h − 4 with h ≥ 3, the path nimber sequence has period k + 1, transient length 3k + 5, and its only zero for n > k is at n = 3k + 4.Once periodic, the sequence never exceeds 3.Source: §7 · pp. 20–21

8 Concluding remarks and future work

The paper establishes complexity and algorithmic results for induced-path hull games, with exact sequence behavior for selected cases. It also identifies unresolved questions about interval-game hardness, periodicity, and extending the algorithms.

8 Concluding remarks and future work

The paper proves PSPACE-completeness for CHGm and CHGℓk for every k ≥2, and gives polynomial-time winner algorithms on disjoint unions of paths and cycles.For odd k, it obtains exact winner criteria on paths and cycles; for k = 2^h − 4 with h ≥3, it establishes periodic nimber sequences there.Source: §8 · p. 21
For k = 2, the path-game nimber sequence matches those of P′n and P″n exactly and agrees with the Couples-are-Forever sequence at 99.97% of positions up to n = 100 million.The paper describes this as a close relationship with Conway’s game.Source: §8 · p. 21
The complexity of interval games remains open for geodesic, monophonic, and ℓk convexities, unlike the hull games whose PSPACE-completeness is established.The open problem covers every convexity considered in the paper.Source: §8 · p. 21
Whether the k = 2 path-game nimber sequence is eventually periodic, or its 12 losing positions can be characterized without exhaustive search, remains open.The experiments suggest a shifted relationship with Couples-are-Forever, but do not settle it.Source: §8 · p. 21
For k = 2^h − 4 with h ≥3, the paper proves eventual periodicity in paths and cycles; this was the only even-k family with observed periodicity in extensive computational testing.Whether other even k yield aperiodic path-game nimber sequences remains open.Source: §8 · p. 21
The smallest diameter supporting PSPACE-hardness for CHGm and CHGℓk with k ≥3 is unknown; the paper’s reduction achieves diameter three.For ℓ2, diameter-two hardness is already known.Source: §8 · p. 21
Extending the polynomial-time algorithms beyond disjoint unions of paths and cycles—to trees or bounded-treewidth graphs—is left as a future step.The existing algorithms determine winners for CHGm and CHGℓk on the stated unions.Source: §8 · p. 21