On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes
En palabras de los autores
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\v{r}\'ak [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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.