Extending prescribed edge paths to cycles in hypercubes is NP-complete

On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes

Computational Complexity

Summary

This paper studies a puzzle involving a high-dimensional cube, called a hypercube, where some connections between points are fixed. The question is whether those fixed connections can be part of a loop that visits every point exactly once. The authors show that deciding this is a very hard problem, even if the fixed connections form simple structures without isolated points. They prove this by turning a known hard logic problem into this puzzle, using clever gadgets inside the hypercube.

What this means in practice

  • For network designers: Know that determining a path covering all nodes with certain fixed links in a hypercube network is computationally infeasible in general.
  • For circuit layout engineers: Use the NP-completeness result to avoid relying on guaranteed extensions of given wiring paths to full cycles in hypercube-based designs.

A theory result. No direct application yet.

Authors

Huazhong Lü, Tingzeng Wu

Abstract

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 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.