← 研踪 PaperTrailarXiv:2611.11476 · v1
On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes
首次提交 2026-11-09 00:15
版本更新 2026-11-09 00:15
雷达观测 2026-11-10 12:16
摘要
Let be the -dimensional hypercube, and let be a set of prescribed edges. It is known that, for , every such set with whose edges form a linear forest is contained in a Hamiltonian cycle of . 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 linear forest with no isolated vertices. We give a polynomial-time reduction from a restricted 3-SAT problem, using local spanning path-forest gadgets for variables and clauses that are uniformly embedded in the hypercube. The same reduction therefore establishes NP-hardness of two versions of Hamiltonian-cycle extension problems for general prescribed edge sets.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 00:15 · 最新观测版本
On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes
Let be the -dimensional hypercube, and let be a set of prescribed edges. It is known that, for , every such set with whose edges form a linear forest is contained in a Hamiltonian cycle of . 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 linear forest with no isolated vertices. We give a polynomial-time reduction from a restricted 3-SAT problem, using local spanning path-forest gadgets for variables and clauses that are uniformly embedded in the hypercube. The same reduction therefore establishes NP-hardness of two versions of Hamiltonian-cycle extension problems for general prescribed edge sets.
查看此版本解读 →查看此版本原文 ↗