Playing Snake on a Graph

Denise Graafsma; Bodo Manthey; Alexander Skopalik

doi:10.48550/arXiv.2506.21281

Playing Snake on a Graph

Denise Graafsma
, Bodo Manthey
, Alexander Skopalik

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

31 Downloads (Pure)

Abstract

Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

Original language	English
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2506.21281
Publication status	Published - 26 Jun 2025

Keywords

cs.DM

Access to Document

10.48550/arXiv.2506.21281Licence: CC BY

2506.21281v1Final published version, 709 KBLicence: CC BY

1 Conference contribution

Playing Snake on a Graph
Graafsma, D., Manthey, B. & Skopalik, A., 2026, Graph-Theoretic Concepts in Computer Science: 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers. Fernau, H. & Kindermann, P. (eds.). 1 ed. Cham: Springer, p. 230-243 14 p. (Lecture Notes in Computer Science; vol. 16124 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
3 Downloads (Pure)

Cite this

@techreport{36958b00e3d2497b8586577ee45a58c9,

title = "Playing Snake on a Graph",

abstract = " Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight. ",

keywords = "cs.DM",

author = "Denise Graafsma and Bodo Manthey and Alexander Skopalik",

year = "2025",

month = jun,

day = "26",

doi = "10.48550/arXiv.2506.21281",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Playing Snake on a Graph

AU - Graafsma, Denise

AU - Manthey, Bodo

AU - Skopalik, Alexander

PY - 2025/6/26

Y1 - 2025/6/26

N2 - Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

AB - Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

KW - cs.DM

U2 - 10.48550/arXiv.2506.21281

DO - 10.48550/arXiv.2506.21281

M3 - Preprint

BT - Playing Snake on a Graph

PB - ArXiv.org

ER -

Playing Snake on a Graph

Abstract

Keywords

Access to Document

Fingerprint

Research output

Playing Snake on a Graph

Cite this