{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-08","reactions":{}}