Id: arxiv/2611.11476 Url: https://arxiv.org/abs/2611.11476 Tags: cs.CC, math.CO Score: 0 Title: On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes Domain: cs.CC Source: arxiv Authors: Huazhong Lü, Tingzeng Wu Reviews: 0 Subject: cs.CC Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-08 Page: https://delphi.science/r/arxiv/2611.11476 Let $Q_n$ be the $n$-dimensional hypercube, and let $P\subseteq E(Q_n)$ be a set of prescribed edges. It is known that, for $n\ge 2$, every such set $P$ with $|P|\leq 2n-3$ whose edges form a linear forest is contained in a Hamiltonian cycle of $Q_n$. This bound is sharp for general linear forests. The computational complexity of deciding whether a prescribed edge set of a hypercube can be extended to a Hamiltonian cycle was posed as an open question by Dvořák [SIAM J. Discrete Math. 19 (2005) 135--144]. We prove that the problem is NP-complete even when the prescribed edges form a spanning…