betaFeedback

WorksComputer Science

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

Abstract

Let QnQ_n be the nn-dimensional hypercube, and let P⊆E(Qn)P\subseteq E(Q_n) be a set of prescribed edges. It is known that, for n≥2n\ge 2, every such set PP with ∣P∣≤2n−3|P|\leq 2n-3 whose edges form a linear forest is contained in a Hamiltonian cycle of QnQ_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.

keywords: Hypercube; Hamiltonian cycle; prescribed edges; linear forest; Hamiltonian-cycle extension; NP-completeness; 05C45; 68R10; 68Q17

Introduction

The nn-dimensional hypercube QnQ_n is the graph on the binary words of length nn, in which two vertices are adjacent if they differ in exactly one coordinate. Its Hamiltonian cycles, equivalently cyclic binary Gray codes, have been studied extensively in combinatorics and interconnection-network theory [4, 16]. Although QnQ_n has a Hamiltonian cycle for every n≥2n \ge2, additional requirements on the edges of such a cycle lead to substantially different questions. Given a set P⊆E(Qn)P \subseteq E(Q_n), the problem is to find a Hamiltonian cycle of QnQ_n containing every edge of PP. If such a cycle exists, then the graph formed by PP must be a linear forest, unless PP itself is a Hamiltonian cycle. It is therefore natural to ask whether this necessary condition is sufficient for a Hamiltonian extension and, if not, what additional restrictions are needed.

Caha and Koubek [2] proved that every set PP of at most n−1n-1 edges of QnQ_n whose edges form a collection of pairwise vertex-disjoint paths is contained in a Hamiltonian cycle of QnQ_n. Dvořák [6] established the bound 2n−32n-3: for n≥2n \ge2 and ∣P∣≤2n−3|P| \le2n-3, the set PP is contained in a Hamiltonian cycle of QnQ_n if and only if it forms a linear forest. The bound is sharp for every n≥3n \ge3, as there exists a linear forest in QnQ_n with exactly 2n−22n-2 edges that is not contained in any Hamiltonian cycle.

Prescribed-edge extension to Hamiltonian path and cycle has also been studied in hypercubes and other interconnection networks. For hypercubes, Dvořák and Gregor [8] characterized when a prescribed edge set PP with ∣P∣≤2n−4|P| \le2n-4 can be contained in a Hamiltonian path of QnQ_n with specified end vertices. For kk-ary nn-cubes, Stewart [17] proved that every prescribed linear forest with at most 2n−12n-1 edges extends to a Hamiltonian cycle when k≥4k \ge4. Yang and Zhang [22] studied the extension of prescribed linear forests to Hamiltonian paths with specified end vertices in kk-ary nn-cubes with odd kk, in the presence of faulty edges. For balanced hypercubes, Lü and Wang [13] proved that every prescribed linear forest with at most nn edges extends to a Hamiltonian cycle, and Cheng [5] subsequently improved this bound to 2n−12n-1.

A particularly important special case arises when the prescribed edge set is a matching. In this setting, the classical Ruskey-Savage conjecture [15] asks whether every matching of a hypercube can be extended to a Hamiltonian cycle. Although the conjecture remains open, Hamiltonian-cycle extension has been established for several restricted classes of matchings, including matchings of size up to specified bounds and matchings whose edges lie in at most five dimensions. Fink [9] proved that every perfect matching of QnQ_n can be extended to a Hamiltonian cycle, thereby settling Kreweras’ conjecture. He also pointed out that every matching of QnQ_n can be extended to a Hamiltonian cycle when n∈{2,3,4}n \in\{2,3,4\}. Wang and Zhao [20] subsequently established the conjecture for Q5Q_5.

For general matchings, several works have established size bounds that guarantee a Hamiltonian extension. Wang and Zhang [18] proved that every matching of size at most 2n−12n-1 has a Hamiltonian extension. They later improved this bound to 3n−103n-10 in a subsequent paper [19]. Dvořák and Fink [7] established the quadratic bound n216+n4\frac{n^2}{16}+\frac{n}{4}, a bound that grows quadratically with the dimension nn. More recently, Ali et al. [1] proved that, for n≥6n \ge6, every matching MM in QnQ_n with ∣M∣≤4n−21|M| \le4n-21 extends to a Hamiltonian cycle. In a different direction, Wang and Wang [21] proved that a matching MM of QnQ_n extends to a Hamiltonian cycle if its edges lie in at most five dimensions and ∣M∣<10×2n−5|M| < 10 \times2^{n-5}. Fink and Hotmar [10] subsequently removed the size condition, establishing Hamiltonian extension for every matching whose edges lie in at most five dimensions. A complementary sufficient condition for Hamiltonian extension, based on local bounds on the number of matching edges in subcubes, was established in [23]. Fink and Mütze [11] also proved that every matching of QnQ_n, n≥2n \ge2, can be extended to a cycle that visits at least a 2/32/3-fraction of all vertices. Although these works establish bounds on the size of matchings that are guaranteed to extend to Hamiltonian cycles, as well as structural conditions under which such extensions exist, they do not by themselves provide a general criterion for extending arbitrary prescribed edge sets to Hamiltonian cycles.

A related problem asks whether Qn−FQ_n-F is Hamiltonian for an arbitrary set F⊆E(Qn)F \subseteq E(Q_n) of faulty edges. Chan and Lee [3] proved that this problem is NP-complete. In contrast, the prescribed-edge problem requires a Hamiltonian cycle containing every edge of a given set PP, rather than avoiding a set of forbidden edges.

Dvořák [6] raised the question of whether Hamiltonian-cycle extension through prescribed edges in hypercubes is also NP-complete. Stewart [17] later observed that the unrestricted prescribed-edge problem for hypercubes and kk-ary nn-cubes had not yet been investigated from a complexity-theoretic perspective. To the best of our knowledge, the complexity of deciding whether an arbitrary prescribed edge set in a hypercube can be extended to a Hamiltonian cycle remains unresolved.

We study the following Hamiltonian-cycle extension problem in hypercubes.

Spanning Linear-Forest Hamiltonian-Cycle Extension

Instance: An integer n≥2n \ge2, encoded in binary, and a set P⊆E(Qn)P \subseteq E(Q_n) represented by an explicit list of edges, each specified by its two nn-bit endpoints, such that the graph (V(Qn),P)(V(Q_n), P) is a spanning linear forest with no isolated vertices. In this representation, QnQ_n is specified implicitly by its dimension nn, whereas PP is specified explicitly by its edge list.

Question: Does QnQ_n contain a Hamiltonian cycle CC such that P⊆E(C)P \subseteq E(C)?

Our main theorem is the following.

Theorem 1.1. The spanning linear-forest Hamiltonian-cycle extension problem is NP-complete.

Furthermore, the same reduction establishes NP-hardness for the Hamiltonian-cycle extension problem when the prescribed edge set is either an arbitrary linear forest or an unrestricted edge set (see Corollary 5.3).

In our input representation, the hypercube QnQ_n is specified implicitly by its dimension nn, whereas the prescribed edge set PP is given explicitly. This distinction is important for establishing membership in NP. For every instance of the restricted problem, the spanning and no-isolated-vertex conditions imply 2∣P∣=∑v∈V(Qn)deg⁡P(v)≥2n2|P| = \sum_{v \in V(Q_n)} \deg_P(v) \ge2^n. Since each edge of PP is represented by its two nn-bit endpoints, the input length is Ω(n∣P∣)=Ω(n2n)\Omega(n|P|) = \Omega(n2^n). On the other hand, a Hamiltonian cycle can be represented by listing its 2n2^n vertices, each as an nn-bit word, requiring O(n2n)O(n2^n) bits. Thus, an explicit Hamiltonian cycle provides a polynomial-size certificate for the restricted problem.

For general prescribed edge sets, however, PP may be sparse, so an explicit listing of a Hamiltonian cycle may have length superpolynomial in the input size. Consequently, the above certificate argument does not establish membership in NP for the unrestricted version.

The remainder of the paper is organized as follows. Section 2 sets up the reduction by specifying the source 3-SAT instances and describing the local hypercube constructions. Section 3 develops the uniform embedding of these constructions and verifies the required structural properties of the prescribed edge set. Section 4 establishes the soundness of the reduction. Section 5 completes the proof of Theorem 1.1 and establishes two further NP-hardness results for general versions of the Hamiltonian-cycle extension problem. Section 6 concludes the paper.

Preliminaries and Source Problem

Notation, Input Representation, and Source Problem

For a graph GG, a path whose vertices appear in the order v0,v1,…,vkv_0,v_1,\ldots,v_k is denoted by ⟨v0,v1,…,vk⟩\langle v_0,v_1,\ldots,v_k\rangle. If P=⟨v0,…,vk⟩P=\langle v_0,\ldots,v_k\rangle and Q=⟨w0,…,wℓ⟩Q=\langle w_0,\ldots,w_\ell\rangle with vk=w0v_k=w_0, their concatenation is denoted by ⟨v0,…,vk,w1,…,wℓ⟩\langle v_0,\ldots,v_k,w_1,\ldots,w_\ell\rangle. A linear forest is a forest whose connected components are paths. Equivalently, it is an acyclic graph of maximum degree at most two. Thus, the condition that (V(Qn),P)(V(Q_n),P) is a spanning linear forest with no isolated vertices is equivalent to requiring that PP be acyclic and 1≤deg⁡P(v)≤21\leq\deg_P(v)\leq2 for every v∈V(Qn)v\in V(Q_n).

For two binary words x,y∈{0,1}nx,y\in\{0,1\}^n, their Hamming distance is defined by dH(x,y)=∣{i∈[n]:xi≠yi}∣d_H(x,y)=|\{i\in[n]:x_i\ne y_i\}|. The nn-dimensional hypercube QnQ_n is the graph with vertex set V(Qn)={0,1}nV(Q_n)=\{0,1\}^n and edge set E(Qn)={{x,y}:x,y∈{0,1}n, dH(x,y)=1}E(Q_n)=\{\{x,y\}:x,y\in\{0,1\}^n,\ d_H(x,y)=1\}. For any integer r≥1r\geq1 and any edge set S⊆E(Qr)S\subseteq E(Q_r), we write GS=(V(Qr),S)G_S=(V(Q_r),S) and denote the degree of a vertex vv in GSG_S by deg⁡S(v)\deg_S(v).

The reduction starts from the following restricted version of 3-SAT. A Boolean formula is a conjunction of clauses, where each clause is a disjunction of literals. In 3-SAT, every clause contains exactly three literals. We use the standard restriction in which the three literals of each clause involve distinct variables. This restriction remains NP-complete; see Karp [12] and Papadimitriou [14].

Let Φ\Phi be an instance of this restricted version of 3-SAT with clauses C1,…,CmC_1,\ldots,C_m. Without loss of generality, we discard any variables that do not appear in Φ\Phi and relabel the occurring variables as x1,…,xtx_1,\ldots,x_t in a fixed order, where m≥1m\geq1 and 3≤t≤3m3\leq t\leq3m. For each clause CqC_q, write Cq=ℓq,1∨ℓq,2∨ℓq,3C_q=\ell_{q,1}\lor\ell_{q,2}\lor\ell_{q,3}, q∈[m]q\in[m]. Here ℓq,k\ell_{q,k} denotes the kk-th literal occurrence of clause CqC_q. For each pair (q,k)∈[m]×{1,2,3}(q,k)\in[m]\times\{1,2,3\}, let i(q,k)∈[t]i(q,k)\in[t] denote the index of the variable appearing in ℓq,k\ell_{q,k}, and let b(q,k)∈{0,1}b(q,k)\in\{0,1\} denote the truth value assigned to the variable xi(q,k)x_{i(q,k)} that makes ℓq,k\ell_{q,k} true. The reduction constructs a hypercube instance from Φ\Phi. The encoding of clauses, variables, and their connections is described in the following section.

Path-Forest Expansion Operations

The constructions below repeatedly enlarge a path forest by replacing an internal edge with a prescribed path in a larger subcube. We formalize this operation as a path-forest expansion.

For later use, we recall the binary reflected Gray path. For d≥1d \ge1 and 0≤k<2d0 \le k < 2^d, define gk=k⊕(k≫1)g_k = k \oplus(k \gg1), where ⊕\oplus denotes bitwise XOR and k≫1k \gg1 denotes shifting the binary representation of kk one position to the right. The sequence ⟨g0,g1,…,g2d−1⟩\langle g_0, g_1, \ldots, g_{2^d-1}\rangle is the binary reflected Gray path of QdQ_d.

Throughout this subsection, we consider a spanning linear forest F⊆E(Qd)F \subseteq E(Q_d) with no isolated vertices. An edge e=uv∈Fe = uv \in F is called an internal edge if deg⁡F(u)=deg⁡F(v)=2\deg_F(u) = \deg_F(v) = 2. A path-forest expansion at an internal edge e={u,v}e = \{u,v\} is performed by introducing a new half-cube adjacent to QdQ_d. Let u′u' and v′v' be the copies of uu and vv in this new half-cube, and let e′={u′,v′}e' = \{u',v'\} be the corresponding parallel edge. The two edges ee and e′e' lie in a 4-cycle. The expansion removes the edge ee and inserts the path ⟨u,P(u′,v′),v⟩\langle u, P(u',v'), v\rangle, where P(u′,v′)P(u',v') is the prescribed Hamiltonian path in the newly introduced half-cube.

We identify the vertices of QdQ_d with their integer labels. Namely, a binary word ad−1⋯a1a0∈{0,1}da_{d-1}\cdots a_1a_0 \in\{0,1\}^d, where a0a_0 is the least significant bit, is represented by the integer ∑j=0d−1aj2j\sum_{j=0}^{d-1} a_j2^j. Let P1,…,PsP_1,\ldots,P_s denote the path components of GFG_F, and let aia_i and bib_i be the two endpoints of PiP_i. We define End⁡(F)={{ai,bi}:1≤i≤s}\operatorname{End}(F) = \{\{a_i,b_i\}: 1 \le i \le s\}. Thus, End⁡(F)\operatorname{End}(F) records the unordered endpoint pairs of all path components of FF. We also define the residual endpoint edge set as R(F)={{u,v}∈E(Qd):deg⁡F(u)=deg⁡F(v)=1, {u,v}∉F}R(F) = \{\{u,v\} \in E(Q_d): \deg_F(u) = \deg_F(v) = 1,\ \{u,v\} \notin F\}. Hence, R(F)R(F) consists of cube edges that can potentially join two endpoints of the path forest without using an already prescribed edge.

The following properties follow immediately from the definition of a path-forest expansion.

Property 1 Suppose that e={u,v}e = \{u,v\} is an internal edge of FF. Let F′F' denote the spanning linear forest obtained by applying the path-forest expansion to FF at ee. Then the following properties hold.

(1). (V(Qd+1),F′)(V(Q_{d+1}), F') is again a spanning linear forest of Qd+1Q_{d+1}.

(2). Every path component of FF not containing ee remains unchanged.

End⁡(F′)=End⁡(F).(1)\operatorname{End}(F')=\operatorname{End}(F). \tag*{(1)}
R(F′)=R(F).(2)R(F')=R(F). \tag*{(2)}

Path-Forest Endpoints and Completion Edges

Lemma 2.1 There exists a spanning linear forest A8⊆E(Q8)A_8 \subseteq E(Q_8) consisting of two paths, with End⁡(A8)={{14,38},{46,54}}\operatorname{End}(A_8)=\{\{14,38\},\{46,54\}\} and R(A8)={{14,46},{38,46},{38,54}}R(A_8)=\{\{14,46\},\{38,46\},\{38,54\}\}. Moreover, the edge e={150,182}∈A8e=\{150,182\}\in A_8 is an internal edge. After deleting ee, the resulting forest satisfies End⁡(A8∖{e})={{14,150},{38,182},{46,54}}\operatorname{End}(A_8\setminus\{e\})=\{\{14,150\},\{38,182\},\{46,54\}\}.

Proof. We construct A8A_8 from a two-path spanning forest of Q4Q_4 by four successive path-forest expansions.

The initial forest F4F_4 consists of the two paths ⟨0,1,3,2,10,11,9,8,12,13,5⟩\langle0,1,3,2,10,11,9,8,12,13,5\rangle and ⟨4,6,14,15,7⟩\langle4,6,14,15,7\rangle. Hence its endpoint pairs are End⁡(F4)={{0,5},{4,7}}\operatorname{End}(F_4)=\{\{0,5\},\{4,7\}\}. We apply path-forest expansions to the successive internal edges {1,3}\{1,3\}, {1,17}\{1,17\}, {1,33}\{1,33\} and {1,65}\{1,65\} appearing in the four expansion steps, when the current hypercube dimensions are 4, 5, 6, 7, respectively. At each step, the selected edge is replaced by the prescribed path in the newly introduced half-cube according to the definition of a path-forest expansion.

Let F8F_8 denote the resulting two-path spanning forest in Q8Q_8. By the structural properties of path-forest expansions, the endpoint pairs are preserved throughout the construction. Therefore, when the vertices of the original Q4Q_4 are viewed as the corresponding vertices of Q8Q_8 with four leading zero coordinates, End⁡(F8)={{0,5},{4,7}}\operatorname{End}(F_8)=\{\{0,5\},\{4,7\}\}.

We now apply a cube automorphism only to obtain a convenient labeling of this construction. Let π\pi be the coordinate permutation given by

(π(0),π(1),…,π(7))=(3,4,5,0,1,2,6,7),(\pi(0),\pi(1),\ldots,\pi(7))=(3,4,5,0,1,2,6,7),

and for x∈V(Q8)x\in V(Q_8) define

f(x)=14⊕⨁j:bit⁡j(x)=12π(j),f(x)=14\oplus\bigoplus_{j:\operatorname{bit}_j(x)=1}2^{\pi(j)},

where bit⁡j(x)\operatorname{bit}_j(x) denotes the jj-th bit of the binary representation of xx. Thus, ff consists of a permutation of the coordinates followed by an XOR translation by the vertex 14. Hence, ff is an automorphism of Q8Q_8 and preserves adjacency.

A direct calculation from the definition of ff gives

f(0)=14,f(5)=38,f(4)=46,f(7)=54.f(0)=14,\qquad f(5)=38,\qquad f(4)=46,\qquad f(7)=54.

Therefore, End⁡(F8)\operatorname{End}(F_8) is mapped as {0,5}↦{14,38}\{0,5\}\mapsto\{14,38\} and {4,7}↦{46,54}\{4,7\}\mapsto\{46,54\}. We define A8=f(F8)A_8=f(F_8). Consequently, End⁡(A8)={{14,38},{46,54}}\operatorname{End}(A_8)=\{\{14,38\},\{46,54\}\}.

It remains to verify the existence and position of the specified internal edge e={150,182}e=\{150,182\}. Under the inverse of the above automorphism, ee is mapped to {131,135}\{131,135\}.

The fourth path-forest expansion replaces the edge {1,65}\{1,65\} by a path entering the newly introduced half-cube 128+Q7128+Q_7. The inserted part is the Hamiltonian path obtained by the XOR translation by the vertex 11 of the binary reflected Gray path defined above. Hence the vertices of the translated path are given by hk=1⊕gkh_k=1\oplus g_k.

Since g3=2g_3=2, g4=6g_4=6, we have h3=1⊕g3=3h_3=1\oplus g_3=3 and h4=1⊕g4=7h_4=1\oplus g_4=7. Therefore, two consecutive vertices of the inserted path are 128+h3=131128+h_3=131, 128+h4=135128+h_4=135. Hence {131,135}\{131,135\} is an internal edge of the inserted path, and its image e={150,182}e=\{150,182\} is an internal edge of A8A_8.

We next determine the residual endpoint edge set. The only degree-one vertices of A8A_8 are the four vertices appearing in End⁡(A8)={{14,38},{46,54}}\operatorname{End}(A_8)=\{\{14,38\},\{46,54\}\}. Among the six possible pairs of these four vertices, exactly three pairs have Hamming distance one: {14,46}\{14,46\}, {38,46}\{38,46\} and {38,54}\{38,54\}. None of these three edges belongs to A8A_8. Consequently, R(A8)={{14,46},{38,46},{38,54}}R(A_8)=\{\{14,46\},\{38,46\},\{38,54\}\}.

The edge ee lies on the path with endpoints 1414 and 3838, and deleting ee splits this path into two paths. Therefore, the resulting endpoint pairs are End⁡(A8∖{e})={{14,150},{38,182},{46,54}}\operatorname{End}(A_8\setminus\{e\})=\{\{14,150\},\{38,182\},\{46,54\}\}. The configuration of A8A_8 is shown in Figure 1(a), with the relevant vertices labelled.

Local spanning path forests

Figure 1. Local spanning path forests. (a) The two paths of A8A_8, with the specified edge {150,182}\{150,182\} marked; (b) The three paths of W9W_9, with endpoint pairs {14,294}\{14,294\}, {46,54}\{46,54\}, and {302,310}\{302,310\}; (c) A three-cut clause forest, with its three cut edges shown dashed; (d) One possible pairing in a two-cut bridge forest, with ports 150 and 182 on each side.

This proves all claimed properties of A8A_8.

We use the following two Hamiltonian cycles C0C_0 and C1C_1 of Q6Q_6.

C0=⟨14,15,13,12,8,9,11,10,2,3,1,0,4,5,7,6,22,23,21,20,16,17,19,18,26,27,25,24,28,29,31,30,62,63,61,60,56,57,59,58,50,51,49,48,52,53,55,54,38,39,37,36,32,33,35,34,42,43,41,40,44,45,47,46⟩C_0=\langle14,15,13,12,8,9,11,10,2,3,1,0,4,5,7,6,22,23,21,20,16,17,19,18,26,27,25,24,28,29,31,30,62,63,61,60,56,57,59,58,50,51,49,48,52,53,55,54,38,39,37,36,32,33,35,34,42,43,41,40,44,45,47,46\rangle
C1=⟨10,11,9,8,12,13,15,14,6,7,5,4,0,1,3,2,18,19,17,16,20,21,23,22,30,31,29,28,24,25,27,26,58,59,57,56,60,61,63,62,54,55,53,52,48,49,51,50,34,35,33,32,36,37,39,38,46,47,45,44,40,41,43,42⟩C_1=\langle10,11,9,8,12,13,15,14,6,7,5,4,0,1,3,2,18,19,17,16,20,21,23,22,30,31,29,28,24,25,27,26,58,59,57,56,60,61,63,62,54,55,53,52,48,49,51,50,34,35,33,32,36,37,39,38,46,47,45,44,40,41,43,42\rangle

Lemma 2.2 There exists a three-path spanning linear forest W9⊆E(Q9)W_9 \subseteq E(Q_9) such that End⁡(W9)={{14,294},{46,54},{302,310}}\operatorname{End}(W_9) = \{\{14,294\},\{46,54\},\{302,310\}\}, and R(W9)={{14,46},{46,302},{54,310},{294,302},{294,310}}R(W_9) = \{\{14,46\},\{46,302\},\{54,310\},\{294,302\},\{294,310\}\}.

Proof. We construct W9W_9 from the two Hamiltonian cycles C0C_0 and C1C_1 defined above. First, remove the two edges {14,46}\{14,46\} and {54,55}\{54,55\} from C0C_0, and denote the resulting spanning linear forest by F0′F'_0. Then End⁡(F0′)={{14,55},{46,54}}\operatorname{End}(F'_0) = \{\{14,55\},\{46,54\}\}. Similarly, remove the two edges {38,46}\{38,46\} and {54,55}\{54,55\} from C1C_1, and denote the resulting spanning linear forest by F1′F'_1. Then End⁡(F1′)={{38,55},{46,54}}\operatorname{End}(F'_1) = \{\{38,55\},\{46,54\}\}.

We apply two successive path-forest expansions to each of F0′F'_0 and F1′F'_1. The first expansion is performed at the internal edge {0,1}\{0,1\} in Q6Q_6. The edge {0,4}\{0,4\} belongs to both original forests and remains internal after this expansion. We perform the second expansion at this preserved edge.

We denote the resulting forests in Q8Q_8 by F0F_0 and F1F_1, respectively. By Property 1, the endpoint pairs of all paths remain unchanged. Therefore, End⁡(F0)={{14,55},{46,54}}\operatorname{End}(F_0) = \{\{14,55\},\{46,54\}\}, and End⁡(F1)={{38,55},{46,54}}\operatorname{End}(F_1) = \{\{38,55\},\{46,54\}\}.

We embed F0F_0 into the lower half of Q9Q_9 and embed F1F_1 into the upper half of Q9Q_9. The vertices of the upper copy are translated by 256, so that 38, 46, 54, 55 are mapped respectively to 294, 302, 310, 311.

Now add the edge {55,311}\{55,311\}. This edge joins the path component of F0F_0 ending at 55 with the corresponding path component in the upper copy of F1F_1 beginning at 311. Hence these two components merge into a single path whose endpoints are 14 and 294. The remaining two path components have endpoint pairs {46,54}\{46,54\} and {302,310}\{302,310\}. Consequently, End⁡(W9)={{14,294},{46,54},{302,310}}\operatorname{End}(W_9) = \{\{14,294\},\{46,54\},\{302,310\}\}.

It remains to determine the residual endpoint edge set. The degree-one vertices

of W9W_9 are exactly 14, 294, 46, 54, 302, 310. The adjacency of two endpoint vertices in Q9Q_9 is equivalent to their XOR being a power of two. Checking the (6) endpoint pairs using the criterion u⊕v=2ju \mathbin{\oplus} v = 2^j gives exactly

{14,46},{46,302},{54,310},{294,302},{294,310}.\{14,46\},\quad\{46,302\},\quad\{54,310\},\quad\{294,302\},\quad\{294,310\}.

None of these edges belongs to W9W_9. Hence

R(W9)={{14,46},{46,302},{54,310},{294,302},{294,310}}.R(W_9)=\{\{14,46\},\{46,302\},\{54,310\},\{294,302\},\{294,310\}\}.

The three paths of W9W_9 are shown in Figure 1(b). Its three prescribed paths have endpoint pairs {14,294}\{14,294\}, {46,54}\{46,54\}, and {302,310}\{302,310\}, respectively.

The following theorem of Dvořák provides a useful criterion for extending prescribed edges to Hamiltonian cycles in hypercubes.

Theorem 2.3 [6] For n≥2n \ge2 and F⊆E(Qn)F \subseteq E(Q_n) with ∣F∣≤2n−3|F| \le2n-3, the set FF is contained in a Hamiltonian cycle of QnQ_n if and only if FF is a linear forest.

The following lemma provides a deterministic construction for our reduction based on Theorem 2.3, with running time polynomial in the number of vertices of the hypercube.

Lemma 2.4 Let s≥3s \ge3, and let MM be a matching of QsQ_s with ∣M∣≤3|M| \le3. There is a deterministic algorithm that constructs the edge list of a Hamiltonian cycle of QsQ_s containing MM in O(2ssO(1))O(2^s s^{O(1)}) time.

Proof. For s≤5s \le5, the required cycle exists by Theorem 2.3 and can be found by exhaustive search in bounded time. Suppose that s≥6s \ge6. Extend the set of dimensions of the edges in MM to a set II of four dimensions. Delete all edges whose dimensions lie outside II. The remaining graph is a disjoint union of Q4Q_4-subcubes and contains every edge of MM. These subcubes are indexed by Qs−4Q_{s-4}.

Fix a dimension h∈Ih \in I not used by MM, and choose an edge f0=uvf_0=uv of dimension hh in one subcube. Denote its corresponding copy in each subcube HH by f0H=uHvHf_0^H=u_Hv_H. Since f0H∉Mf_0^H \notin M and M∩E(H)M \cap E(H) is a matching, (M∩E(H))∪{f0H}(M \cap E(H)) \cup\{f_0^H\} is a linear forest with at most four edges. By Theorem 2.3, it is contained in a Hamiltonian cycle CHC_H, which can be found by exhaustive search on sixteen vertices.

List the subcubes in cyclic binary reflected Gray order. Delete f0Hf_0^H from each CHC_H, obtaining a spanning path with endpoints uHu_H, vHv_H. Around this cyclic order, join consecutive paths alternately by the corresponding cross edges uHuH′u_Hu_{H'} and vHvH′v_Hv_{H'}. Since the number of subcubes is even, each path endpoint receives exactly one cross edge, and the paths form a single Hamiltonian cycle containing MM. Making all choices in a fixed order gives a deterministic construction in O(2ssO(1))O(2^s s^{O(1)}) time.

Uniform addresses and prescribed joins

Address coordinates and logical locations

The coordinates of the host hypercube QnQ_n are split into an address block of size aa and a local block of size dd, where n=a+dn=a+d. Accordingly, Qn=Qa□QdQ_n=Q_a\square Q_d.

The address cube QaQ_a must accommodate both the positions of all gadgets and the routing paths that connect them. We represent each vertex of QaQ_a by a full address (u,z,λ)∈V(Qa)(u,z,\lambda)\in V(Q_a), consisting of three coordinate blocks: a base-address block u∈{0,1}Bu\in\{0,1\}^{B}, a route tag z∈{0,1}rbz\in\{0,1\}^{r_b}, and a two-bit lane label λ∈{0,1}2\lambda\in\{0,1\}^{2}. Thus, the dimension of the address cube is a=B+rb+2a=B+r_b+2. The route tag zz distinguishes the H=3m+tH=3m+t logical connections in the construction, comprising 3m3m literal occurrences and tt terminal variable connections; hence, rb=⌈log⁡2(H+1)⌉r_b=\lceil\log_2(H+1)\rceil. When z=0z=0, the symbol 0 denotes the all-zero rbr_b-bit string.

The base address specifies the logical location of a gadget and consists of five consecutive blocks: a clause identifier of length 3hc3h_c, a variable identifier of length hvh_v, a six-bit marker block, an auxiliary Gray-code block of length hωh_\omega, and a single-bit terminal flag τ\tau. Thus, B=3hc+hv+6+hω+1B=3h_c+h_v+6+h_\omega+1, where hc=max⁡{1,⌈log⁡2m⌉}h_c=\max\{1,\lceil\log_2 m\rceil\}, hv=max⁡{1,⌈log⁡2t⌉}h_v=\max\{1,\lceil\log_2 t\rceil\}, and hω=⌈log⁡2(2t+1)⌉h_\omega=\lceil\log_2(2t+1)\rceil. For integers 0≤x<2h0\leq x<2^h, let bin⁡h(x)\operatorname{bin}_h(x) denote the standard hh-bit binary representation of xx, and let ρh(x)\rho_h(x) denote the concatenation of three identical copies of bin⁡h(x)\operatorname{bin}_h(x), having total length 3h3h. For 0≤j≤t0\leq j\leq t, let ωj\omega_j be the hωh_\omega-bit reflected Gray encoding of 2j2j. The words ω0,…,ωt\omega_0,\ldots,\omega_t are distinct and have even Hamming weight. Consequently, dH(ωj,ωj′)≥2d_H(\omega_j,\omega_{j'})\geq2 whenever j≠j′j\ne j', and dH(ωi−1,ωi)=2d_H(\omega_{i-1},\omega_i)=2 for every 1≤i≤t1\leq i\leq t.

For each clause CqC_q, define cq=(ρhc(q−1),0hv,000000,0hω,0)c_q=(\rho_{h_c}(q-1),0^{h_v},000000,0^{h_\omega},0). We reserve the first three coordinates of the six-bit marker block for the three literal positions. Put σ1=100000\sigma_1=100000, σ2=010000\sigma_2=010000, and σ3=001000\sigma_3=001000, and define the literal attachment addresses by ℓq,k=(ρhc(q−1),0hv,σk,0hω,0)\ell_{q,k}=(\rho_{h_c}(q-1),0^{h_v},\sigma_k,0^{h_\omega},0) for k∈{1,2,3}k\in\{1,2,3\}. The base address ℓq,k\ell_{q,k} identifies the location of the kk-th literal occurrence of clause CqC_q. Specifically, the corresponding variable route contains the vertex (ℓq,k,0,00)(\ell_{q,k},0,00) in QaQ_a.

For the variable identifiers, let γi\gamma_i be the hvh_v-bit reflected Gray encoding of i−1i-1. Thus consecutive variables have Gray identifiers at Hamming distance one. Define si=(03hc,γi,111000,ωi−1,1)s_i=(0^{3h_c},\gamma_i,111000,\omega_{i-1},1) and ti=(03hc,γi,111000,ωi,0)t_i=(0^{3h_c},\gamma_i,111000,\omega_i,0). For 1≤i<t1\le i<t, define the bridge address bi=(03hc,γi+1,111000,ωi,0)b_i=(0^{3h_c},\gamma_{i+1},111000,\omega_i,0). Thus tit_i and bib_i differ only in the variable identifier block, while bib_i and si+1s_{i+1} differ only in the terminal flag. These two adjacencies will later be used to attach the bridge between the constructions for variables xix_i and xi+1x_{i+1}.

Variable routes in the address cube

Fix a variable xix_i, and list all literal occurrences (q,k)(q,k) satisfying i(q,k)=ii(q,k)=i in increasing order of their clause indices. If these occurrences are (qi,1,ki,1),…,(qi,νi,ki,νi)(q_{i,1},k_{i,1}),\ldots,(q_{i,\nu_i},k_{i,\nu_i}), consider the logical sequence si,ℓqi,1,ki,1,…,ℓqi,νi,ki,νi,tis_i,\ell_{q_{i,1},k_{i,1}},\ldots,\ell_{q_{i,\nu_i},k_{i,\nu_i}},t_i. Each consecutive pair in this sequence determines one logical connection. Since ∑iνi=3m\sum_i\nu_i=3m, the total number of such connections is ∑i(νi+1)=3m+t=H\sum_i(\nu_i+1)=3m+t=H. Assign a distinct nonzero rbr_b-bit route tag to every logical connection.

Let u,vu,v be any consecutive pair of base addresses along the logical sequence of a variable xix_i (that is, u,v∈{si,ℓqi,1,ki,1,…,ti}u,v\in\{s_i,\ell_{q_{i,1},k_{i,1}},\ldots,t_i\}). A logical connection between base addresses uu and vv with route tag zz is represented by a path in the address cube. We call this path a leg. It is given by

(u,0,00)→(u,0,10)→(u,z,10)→(u,z,11)→(v,z,11)→(v,z,01)→(v,0,01)→(v,0,00).(u,0,00)\mathbin{\to}(u,0,10)\mathbin{\to}(u,z,10)\mathbin{\to}(u,z,11) \mathbin{\to}(v,z,11)\mathbin{\to}(v,z,01)\mathbin{\to}(v,0,01)\mathbin{\to}(v,0,00).

If two consecutive displayed addresses differ in more than one coordinate, the arrow between them denotes the shortest cube path obtained by flipping the differing coordinates one at a time, in increasing order of their indices.

Expanding each multi-coordinate transition of a leg into the specified sequence of single-coordinate flips and concatenating the legs in the order of the logical sequence produces the routed address path vi,0,vi,1,…,vi,Liv_{i,0},v_{i,1},\ldots,v_{i,L_i} for variable xix_i, where consecutive vertices are adjacent in QaQ_a. Since each leg from uu to vv starts at (u,0,00)(u,0,00) and ends at (v,0,00)(v,0,00), and the logical sequence starts at sis_i and ends at tit_i, we have vi,0=(si,0,00)v_{i,0}=(s_i,0,00), vi,Li=(ti,0,00)v_{i,L_i}=(t_i,0,00).

The internal junctions between consecutive legs are precisely the logical locations (ℓq,k,0,00)(\ell_{q,k},0,00) corresponding to the literal occurrences of xix_i. The other vertices strictly inside the expanded legs are auxiliary routing vertices, each having a nonzero lane label. Consequently, the vertices on the route with route tag 00 and lane label $00 are precisely its logical locations: the initial address (si,0,00)(s_i,0,00), the specified literal-occurrence addresses, and the terminal address (ti,0,00)(t_i,0,00). By the definitions of sis_i and tit_i, the auxiliary words ωi−1\omega_{i-1} and ωi\omega_i differ in exactly two coordinates, while their terminal flags 11 and 00 differ in one coordinate. Hence dH(si,ti)=3d_H(s_i,t_i)=3. By the endpoint identities established above, dH(vi,0,vi,Li)=3d_H(v_{i,0},v_{i,L_i})=3. Since every edge of the hypercube changes exactly one coordinate, the length of any path between two vertices has the same parity as their Hamming distance. Therefore, Li≡dH(vi,0,vi,Li)≡dH(si,ti)≡3≡1(mod2)L_i \equiv d_H(v_{i,0},v_{i,L_i}) \equiv d_H(s_i,t_i) \equiv3 \equiv1 \pmod{2}. In particular, LiL_i is odd.

Note that each literal occurrence (q,k)(q,k) of variable xix_i is placed at an intermediate vertex vi,p(q,k)=(ℓq,k,0,00)v_{i,p(q,k)}=(\ell_{q,k},0,00) for a unique index p(q,k)∈{1,…,Li−1}p(q,k)\in\{1,\ldots,L_i-1\}. Here, the base address ℓq,k\ell_{q,k} shares the clause identifier ρhc(q−1)\rho_{h_c}(q-1) with the clause base address cqc_q, differing from cqc_q only in the kk-th marker coordinate. The vertex vi,p(q,k)v_{i,p(q,k)} is incident with the two consecutive route edges {vi,p(q,k)−1,vi,p(q,k)}\{v_{i,p(q,k)-1},v_{i,p(q,k)}\} and {vi,p(q,k),vi,p(q,k)+1}\{v_{i,p(q,k)},v_{i,p(q,k)+1}\}. Since the full addresses (ℓq,k,0,00)(\ell_{q,k},0,00) and (cq,0,00)(c_q,0,00) are adjacent in QaQ_a, this vertex provides the attachment position for the clause subcube corresponding to CqC_q.

Local labels and spanning forests

To fix the dimension of the local subcube QdQ_d, let Lmax⁡=max⁡1≤i≤tLiL_{\max}=\max_{1\le i\le t}L_i, put r=⌈log⁡2Lmax⁡⌉r=\lceil\log_2 L_{\max}\rceil, and set d=8+r+3hvd=8+r+3h_v. For each address α∈V(Qa)\alpha\in V(Q_a), let Qd(α)Q_d(\alpha) denote the corresponding dd-dimensional subcube of QnQ_n at address α\alpha. Whenever αβ∈E(Qa)\alpha\beta\in E(Q_a), the identity matching between V(Qd(α))V(Q_d(\alpha)) and V(Qd(β))V(Q_d(\beta)) formed by edges {(α,y),(β,y)}\{(\alpha,y),(\beta,y)\} for all y∈V(Qd)y\in V(Q_d) defines the set of cross-subcube edges between them.

The dd local coordinates consist of a 3hv3h_v-bit variable prefix, an rr-bit route-link code, and an eight-bit local port label. For 0≤j<Lmax⁡0\le j<L_{\max}, let θj\theta_j be the rr-bit reflected Gray encoding of jj. For 1≤i≤t1\le i\le t, 0≤j<Li0\le j<L_i, and ζ∈{0,…,255}\zeta\in\{0,\ldots,255\}, define

Λ(i,j,ζ)=(ρhv(i−1),θj,bin⁡8(ζ))∈{0,1}d.\Lambda(i,j,\zeta)=(\rho_{h_v}(i-1),\theta_j,\operatorname{bin}_8(\zeta))\in\{0,1\}^d.

The parameter jj refers to the route link joining vi,jv_{i,j} and vi,j+1v_{i,j+1}, while ζ\zeta is an eight-bit local port label. In particular, the values 14, 38, 46, 54, 150, and 182 used below refer only to the last eight local coordinates.

We now place a spanning linear forest inside every local subcube associated with the logical construction. The linear forests from Lemmas 2.1 and 2.2 serve as low-dimensional templates. By repeated application of the path-forest expansion operation, each copy of A8A_8 or W9W_9 is enlarged to a spanning linear forest of the required local dd-dimensional subcube. The expansion preserves the relevant endpoint structure and, for the A8A_8 template, the specified internal edge {150,182}\{150, 182\}.

At the initial and terminal route positions vi,0v_{i,0} and vi,Liv_{i,L_i}, place an expanded copy of the two-path forest A8A_8. We refer to these as the terminal A8A_8-subcubes of variable xix_i. At every internal route position vi,pv_{i,p} with 0<p<Li0 < p < L_i, place an expanded copy of the three-path forest W9W_9. Since the consecutive Gray words θp−1\theta_{p-1} and θp\theta_p differ in exactly one coordinate, we identify the ninth coordinate of the W9W_9 template with this unique differing coordinate. All other coordinates of the rr-bit route-position block remain fixed within this copy of W9W_9. After this identification, the side of the W9W_9-subcube facing route link (i,p−1)(i,p-1) has Boolean endpoints with local labels Λ(i,p−1,46)\Lambda(i,p-1,46) and Λ(i,p−1,54)\Lambda(i,p-1,54), while the side facing route link (i,p)(i,p) has Boolean endpoints with local labels Λ(i,p,46)\Lambda(i,p,46) and Λ(i,p,54)\Lambda(i,p,54).

For each route link jj, let χj\chi_j denote its common-channel port label, defined by χj=14\chi_j=14 when jj is even and χj=38\chi_j=38 when jj is odd. Thus, the common-channel port labels alternate between 14 and 38 along each variable route. At an internal route position vi,pv_{i,p}, orient the W9W_9-subcube so that its common-channel endpoint on the side of link p−1p-1 has local label Λ(i,p−1,χp−1)\Lambda(i,p-1,\chi_{p-1}), while its endpoint on the side of link pp has local label Λ(i,p,χp)\Lambda(i,p,\chi_p). Orient the terminal A8A_8-subcubes consistently with their unique adjacent route links. Consequently, the endpoint of the subcube at vi,jv_{i,j} facing vi,j+1v_{i,j+1} and the endpoint of the subcube at vi,j+1v_{i,j+1} facing vi,jv_{i,j} both have the local label Λ(i,j,χj)\Lambda(i,j,\chi_j). For every route link jj, prescribe the cross-subcube edge

{(vi,j,Λ(i,j,χj)),(vi,j+1,Λ(i,j,χj))}.\left\{(v_{i,j},\Lambda(i,j,\chi_j)),(v_{i,j+1},\Lambda(i,j,\chi_j))\right\}.

Thus, every route link has exactly one prescribed common-channel edge, whose port label alternates between 14 and 38. The two parallel cross-subcube edges with local labels Λ(i,j,46)\Lambda(i,j,46) and Λ(i,j,54)\Lambda(i,j,54) are not prescribed; they will serve as the two Boolean candidates in a Hamiltonian extension.

We next define the clause constructions. For b∈{0,1}b \in\{0,1\}, put ζ0=54\zeta_0=54 and ζ1=46\zeta_1=46. For a literal occurrence (q,k)(q,k), let i=i(q,k)i=i(q,k) and p=p(q,k)p=p(q,k). In the local subcube Qd((cq,0,00))Q_d((c_q,0,00)), select the edge

eq,k={Λ(i,p−1,ζb(q,k)),Λ(i,p,ζb(q,k))}.e_{q,k}=\left\{\Lambda(i,p-1,\zeta_{b(q,k)}),\Lambda(i,p,\zeta_{b(q,k)})\right\}.

The two endpoints of eq,ke_{q,k} have the same variable prefix and the same local port label, and differ only in the consecutive route-position codes θp−1\theta_{p-1} and θp\theta_p. Since these two Gray words differ in exactly one coordinate, eq,ke_{q,k} is an edge of the local QdQ_d-subcube. The edge eq,ke_{q,k} is chosen as the cut edge associated with the literal occurrence (q,k)(q,k): after it is removed from the clause Hamiltonian cycle, its two endpoints become degree-one vertices corresponding to the two sides of the W9W_9-subcube placed at the literal route position vi,pv_{i,p}. These two exposed clause endpoints may then be joined, through the corresponding cross-subcube edges, to the two matching endpoints of that W9W_9-subcube. The cross-subcube edges are left unprescribed and form the optional external connection associated with (q,k)(q,k).

The three cut edges eq,1,eq,2,eq,3e_{q,1},e_{q,2},e_{q,3} form an induced matching by Lemma 3.1(4). Apply Lemma 2.4 in the local subcube at (cq,0,00)(c_q,0,00) to construct a Hamiltonian cycle CqlocC_q^{\mathrm{loc}} containing all three cut edges. Define the clause forest by Fq=Cqloc−{eq,1,eq,2,eq,3}F_q=C_q^{\mathrm{loc}}-\{e_{q,1},e_{q,2},e_{q,3}\}. Then FqF_q is a spanning linear forest consisting of three paths, with six degree-one vertices given by the endpoints of the three deleted edges. We call FqF_q the three-cut clause forest associated with CqC_q. The resulting local structure is illustrated in Figure 1(c), where the three deleted edges are indicated by orange dashed lines. Note that eq,1,eq,2,eq,3e_{q,1},e_{q,2},e_{q,3} are not included in the prescribed forest. In fact, they remain available for use in a Hamiltonian extension. For any selected index k∈{1,2,3}k\in\{1,2,3\}, restoring the other two cut edges gives Fq+{eq,k′:k′≠k}=Cqloc−{eq,k}F_q+\{e_{q,k'}:k'\ne k\}=C_q^{\mathrm{loc}}-\{e_{q,k}\}, which is a Hamiltonian path whose endpoints are the two endpoints of eq,ke_{q,k}.

We now specify the external connections associated with eq,1,eq,2e_{q,1},e_{q,2} and eq,3e_{q,3}. The endpoints of eq,ke_{q,k} are degree-one vertices of the clause forest FqF_q. Since the outer addresses (cq,0,00)(c_q,0,00) and vi,p=(ℓq,k,0,00)v_{i,p}=(\ell_{q,k},0,00) are adjacent in QaQ_a, these two endpoints can be connected to the corresponding vertices of the W9W_9-subcube in Qd(vi,p)Q_d(v_{i,p}) by the cross-subcube edges

gq,k−={((cq,0,00),Λ(i,p−1,ζb(q,k))),((vi,p,Λ(i,p−1,ζb(q,k))))},g_{q,k}^{-}=\left\{\left((c_q,0,00),\Lambda(i,p-1,\zeta_{b(q,k)})\right),\left((v_{i,p},\Lambda(i,p-1,\zeta_{b(q,k)}))\right)\right\},
gq,k+={((cq,0,00),Λ(i,p,ζb(q,k))),((vi,p,Λ(i,p,ζb(q,k))))}.g_{q,k}^{+}=\left\{\left((c_q,0,00),\Lambda(i,p,\zeta_{b(q,k)})\right),\left((v_{i,p},\Lambda(i,p,\zeta_{b(q,k)}))\right)\right\}.

Neither gq,k−g_{q,k}^{-} nor gq,k+g_{q,k}^{+} belongs to the prescribed forest. Together, these two edges provide the optional external connection between the clause subcube and the variable subcube at the literal position vi,pv_{i,p}.

Finally, consider the bridge between variables xix_i and xi+1x_{i+1}, where 1≤i<t1\le i<t. In the terminal A8A_8-subcube of xix_i, delete the internal edge corresponding to the template edge {150,182}\{150,182\}, whose endpoints have local labels Λ(i,Li−1,150)\Lambda(i,L_i-1,150) and Λ(i,Li−1,182)\Lambda(i,L_i-1,182). In the initial A8A_8-subcube of xi+1x_{i+1}, delete the corresponding internal edge with endpoints Λ(i+1,0,150)\Lambda(i+1,0,150) and Λ(i+1,0,182)\Lambda(i+1,0,182).

Inside the bridge subcube Qd((bi,0,00))Q_d((b_i,0,00)), define the two edges

ei−={Λ(i,Li−1,150),Λ(i,Li−1,182)},e_i^-=\{\Lambda(i,L_i-1,150),\Lambda(i,L_i-1,182)\},
ei+={Λ(i+1,0,150),Λ(i+1,0,182)}.e_i^+=\{\Lambda(i+1,0,150),\Lambda(i+1,0,182)\}.

Hence, ei−e_i^- and ei+e_i^+ form an induced matching in the bridge subcube by Lemma 3.1(4). By Lemma 2.4, there exists a Hamiltonian cycle CibrC_i^{br} in this subcube containing both edges. Deleting these two edges from CibrC_i^{br} yields a spanning linear forest consisting of exactly two vertex-disjoint paths, with the four endpoints given by the endpoints of ei−e_i^- and ei+e_i^+. We call this forest the two-cut bridge forest (see Figure 1(d)). We then prescribe the four cross-subcube edges joining these four degree-one vertices to the four newly exposed degree-one vertices of the adjacent terminal A8A_8-subcubes, along the outer cube edges {(ti,0,00),(bi,0,00)}\{(t_i,0,00),(b_i,0,00)\} and {(bi,0,00),(si+1,0,00)}\{(b_i,0,00),(s_{i+1},0,00)\}.

The outer addresses assigned to the variable-route positions, clause gadgets, and bridge gadgets are called occupied addresses, and all remaining outer addresses are called unoccupied addresses. Accordingly, the corresponding local subcubes are called occupied subcubes and unoccupied subcubes, respectively.

Let Gocc(Φ)G_{\mathrm{occ}}(\Phi) denote the graph whose vertices are all vertices in the occupied local subcubes and whose edges are precisely the prescribed edges specified within and between these subcubes. The Boolean candidate edges and the optional clause-variable connection edges are not included in Gocc(Φ)G_{\mathrm{occ}}(\Phi). Lemma 5.1 shows how a satisfying assignment determines additional edges that complete Gocc(Φ)G_{\mathrm{occ}}(\Phi) to a Hamiltonian cycle on the occupied vertices.

Figure 2 illustrates this construction for the representative clause Cq=(x1∨¬x2∨xt)C_q=(x_1\lor\neg x_2\lor x_t) and the assignment (x1,x2,xt)=(0,0,0)(x_1,x_2,x_t)=(0,0,0), showing how the prescribed edges and the selected optional edges combine to form the Hamiltonian cycle.

Schematic Hamiltonian-cycle construction

Figure 2. A schematic Hamiltonian-cycle construction for the clause Cq=(x1∨¬x2∨xt)C_q = (x_1 \vee\neg x_2 \vee x_t) under the assignment (x1,x2,xt)=(0,0,0)(x_1,x_2,x_t) = (0,0,0). Blue solid edges denote prescribed edges, whereas green solid edges denote the optional edges selected under the given assignment. The Hamiltonian cycle is the union of all blue and green solid edges shown in the figure.

Address separation and validity of the prescribed connections

Lemma 3.1 The address assignments defined above have the following properties.

(1). For each variable xix_i, the route vi,0,…,vi,Liv_{i,0},\ldots,v_{i,L_i} is a simple path in QaQ_a. Two distinct legs are vertex-disjoint unless they are consecutive legs of the same variable route; in that case, they share exactly one vertex, namely the literal address (ℓq,k,0,00)(\ell_{q,k},0,00) at which they are concatenated.

(2). Among the occupied addresses of QaQ_a, each clause address (cq,0,00)(c_q, 0, 00) is adjacent exactly to its three literal addresses (ℓq,k,0,00)(\ell_{q,k}, 0, 00), k∈{1,2,3}k \in\{1,2,3\}. Each bridge base address (bi,0,00)(b_i, 0, 00) is adjacent precisely to (ti,0,00)(t_i, 0, 00) and (si+1,0,00)(s_{i+1}, 0, 00).

(3). All prescribed common-channel edges, all prescribed bridge-attachment edges, and all optional clause-variable connection edges belong to E(Qn)E(Q_n).

(4). The three cut edges in each clause subcube form an induced matching of size three, and the two cut edges in each bridge subcube form an induced matching of size two.

Proof. (1) Each leg is a simple path, since its successive coordinate paths flip distinct coordinates without repetition and occupy different lanes. For distinct legs, their segments in lane 10 are disjoint because each such segment has a fixed initial base address, and distinct legs have distinct initial base addresses. Similarly, their segments in lane 01 are disjoint because each such segment has a fixed terminal base address, and distinct legs have distinct terminal base addresses. Their segments in lane 11 are disjoint because each leg is assigned a distinct nonzero route tag.

(2) We verify the asserted adjacencies among all occupied addresses of QaQ_a. First consider the logical addresses with route tag 0 and lane label 00. For each clause CqC_q, the three literal addresses ℓq,1,ℓq,2,ℓq,3\ell_{q,1},\ell_{q,2},\ell_{q,3} differ from cqc_q in exactly one marker coordinate. ordinate, so they are adjacent to cqc_q. If q′≠qq' \ne q, then

dH(ρhc(q−1),ρhc(q′−1))=3dH(bin⁡hc(q−1),bin⁡hc(q′−1))≥3.d_H(\rho_{h_c}(q-1),\rho_{h_c}(q'-1))=3d_H(\operatorname{bin}_{h_c}(q-1),\operatorname{bin}_{h_c}(q'-1))\ge3.

Thus no other clause address or literal address is adjacent to cqc_q. Moreover, the marker block of every variable address si,tis_i,t_i and every bridge address bib_i is 111000, which differs from the marker block 000000 of cqc_q in three coordinates. Hence the only occupied logical addresses adjacent to cqc_q are its three literal addresses.

Now fix a bridge address bib_i. Its marker block 111000 differs from the marker block of each clause address in three coordinates and from the marker block σk\sigma_k of each literal address in two coordinates. For any terminal variable address tjt_j, the definitions give dH(bi,tj)=dH(γi+1,γj)+dH(ωi,ωj)d_H(b_i,t_j)=d_H(\gamma_{i+1},\gamma_j)+d_H(\omega_i,\omega_j), which is one when j=ij=i, and is at least two when j≠ij\ne i. Similarly, dH(bi,sj)=dH(γi+1,γj)+dH(ωi,ωj−1)+1d_H(b_i,s_j)=d_H(\gamma_{i+1},\gamma_j)+d_H(\omega_i,\omega_{j-1})+1, which is one when j=i+1j=i+1, and is at least three otherwise. Finally, if j≠ij\ne i, then dH(bi,bj)≥dH(ωi,ωj)≥2d_H(b_i,b_j)\ge d_H(\omega_i,\omega_j)\ge2. Consequently, among the logical addresses, bib_i is adjacent exactly to tit_i and si+1s_{i+1}.

It remains to consider the auxiliary vertices introduced by the expanded legs. Every such vertex has a nonzero lane label. If it is adjacent to a vertex of the form (a,0,00)(a,0,00), then its route tag must be zero and its base address must equal aa. By the construction of a leg from uu to vv, the only auxiliary vertices with zero route tag are (u,0,10)(u,0,10) and (v,0,01)(v,0,01). Consequently, an auxiliary vertex can be adjacent to a location of the form (a,0,00)(a,0,00) only when that location is an endpoint of its own leg.

(3) Since Qn=Qa□QdQ_n=Q_a\Box Q_d, two vertices with adjacent outer addresses and identical local coordinates are adjacent in QnQ_n. The common-channel edges use consecutive vertices of a variable address path. The bridge-attachment edges use the outer-address adjacencies established in (2), and the optional clause-variable edges use the adjacency between cqc_q and ℓq,k\ell_{q,k}. Thus all the stated edges belong to QnQ_n.

(4) Each clause cut edge eq,ke_{q,k} is an edge of its local QaQ_a because the consecutive Gray codes θp−1\theta_{p-1} and θp\theta_p differ in exactly one coordinate. The three literals of a clause involve distinct variables, whose triple-repeated variable prefixes have pairwise Hamming distance at least three. Therefore, endpoints belonging to distinct clause cut edges are nonadjacent, and the three edges form an induced matching.

For a bridge cut edge, the local labels 150 and 182 differ in exactly one coordinate, since 150⊕182=32150\oplus182=32. The two bridge cut edges use distinct variable prefixes at Hamming distance at least three, so their endpoints are pairwise nonadjacent across the two edges. Hence they form an induced matching of size two. □\square

Degree-feasible cross-subcube edges

We now determine which non-prescribed cross-subcube edges can be used in a Hamiltonian extension without violating the degree-two condition. Let PP consist of all prescribed edges, including the edges of the local spanning forests and the prescribed cross-subcube edges. Since every vertex of a Hamiltonian cycle has degree two, a non-prescribed edge joining two vertices of prescribed degree one is called degree-feasible. For each occupied outer address α\alpha, define

Tα={y∈{0,1}d:deg⁡P((α,y))=1}.T_\alpha=\{y\in\{0,1\}^d:\deg_P((\alpha,y))=1\}.

Thus, TαT_\alpha records the local coordinates of vertices that can be incident with one additional edge in Hamiltonian completion. If αβ∈E(Qa)\alpha\beta\in E(Q_a), the degree-feasible cross-subcube edges between Qd(α)Q_d(\alpha) and Qd(β)Q_d(\beta) are precisely

{{(α,y),(β,y)}:y∈Tα∩Tβ}.\{\{(\alpha,y),(\beta,y)\}:y\in T_\alpha\cap T_\beta\}.

Since the endpoints of every prescribed cross-subcube edge already have prescribed degree two, no such edge belongs to this set.

Lemma 3.2 For adjacent occupied addresses in QaQ_a, the prescribed and degree-feasible cross-subcube edges are as follows.

  1. Between vi,jv_{i,j} and vi,j+1v_{i,j+1}, there is one prescribed common-channel edge corresponding to the port χj\chi_j (that is, 14 if jj is even and 38 if jj is odd), together with two degree-feasible edges corresponding to the ports 46 and 54.

  1. Between (cq,0,00)(c_q,0,00) and vi,p(q,k)v_{i,p(q,k)}, where i=i(q,k)i=i(q,k), the only degree-feasible edges are gq,k−g_{q,k}^{-} and gq,k+g_{q,k}^{+}; neither is prescribed.

  1. Between (bi,0,00)(b_i,0,00) and either (ti,0,00)(t_i,0,00) or (si+1,0,00)(s_{i+1},0,00), there are exactly two prescribed edges and no degree-feasible edges.

  1. All other adjacent occupied addresses have no prescribed or degree-feasible cross-subcube edges between them.

Proof. (1)–(3) follow directly from the definitions of the local forests and their prescribed connections. For (4), it suffices to consider pairs of route positions vi,pv_{i,p} and vi′,qv_{i',q} that are not consecutive on the same variable route. If i≠i′i\ne i', ρhv(i−1)\rho_{h_v}(i-1) and ρhv(i′−1)\rho_{h_v}(i'-1) differ in at least three coordinates. Hence there is no local coordinate $y for which both (vi,p,y)(v_{i,p},y) and (vi′,q,y)(v_{i',q},y) have degree one in PP. Consequently, no degree-feasible cross-subcube edge can join the two corresponding local subcubes.

Suppose now that i=i′i=i' and p<qp<q. Since the two positions are not consecutive, q−p≥2q-p\ge2. Thus, the local labels of the degree-one vertices in Qd(vi,p)Q_d(v_{i,p}) are of the form Λ(i,0,ζ)\Lambda(i,0,\zeta) if p=0p=0, of the forms Λ(i,p−1,ζ)\Lambda(i,p-1,\zeta) and Λ(i,p,ζ)\Lambda(i,p,\zeta) if 0<p<Li0<p<L_i, and of the form Λ(i,Li−1,ζ)\Lambda(i,L_i-1,\zeta) if p=Lip=L_i, for the corresponding port labels specified above. Since q−p≥2q-p\ge2, the two positions have no common route link.

Therefore, in either case, no degree-feasible non-prescribed cross-subcube edge can join the two corresponding local subcubes. By construction, no prescribed cross-subcube edge is assigned between these pairs either.

Acyclicity of the prescribed edges on occupied subcubes

Lemma 3.3 The graph Gocc(Φ)G_{\mathrm{occ}}(\Phi) is a spanning linear forest with exactly

c0=2∑i=1tLi+t+3mc_0=2\sum_{i=1}^{t}L_i+t+3m

components.

Proof. Recall that LiL_i is the length of the expanded route vi,0,vi,1,…,vi,Liv_{i,0},v_{i,1},\ldots,v_{i,L_i} of variable xix_i. After deleting the edge corresponding to {150,182}\{150,182\} from each A8A_8-subcube incident with a bridge subcube, the forest has

Nloc=4+6(t−1)+3(∑i=1tLi−t)+2(t−1)+3mN_{\mathrm{loc}}=4+6(t-1)+3\left(\sum_{i=1}^{t}L_i-t\right)+2(t-1)+3m
=3∑i=1tLi+5t−4+3m=3\sum_{i=1}^{t}L_i+5t-4+3m

path components. Here, the two end A8A_8-subcubes contribute four paths, the 2(t−1)2(t-1) bridge-incident A8A_8-subcubes contribute three paths each, each W9W_9-subcube contributes three paths, each bridge subcube contributes two paths, and each clause subcube contributes three paths.

Add the prescribed common-channel edges in route order. Each edge joins distinct components, extending the common-channel paths along the variable routes without creating a cycle. Since there are ∑i=1tLi\sum_{i=1}^{t}L_i such edges, the component count decreases by ∑i=1tLi\sum_{i=1}^{t}L_i.

Each bridge subcube consists of two disjoint paths. The four prescribed attachment edges join their endpoints to the two distinct exposed components on each side, extending the paths without creating a cycle. Thus each bridge reduces the number of path components by four.

Consequently, Gocc(Φ)G_{\mathrm{occ}}(\Phi) is acyclic and has

c0=Nloc−∑i=1tLi−4(t−1)=2∑i=1tLi+t+3m\begin{aligned} c_0 &= N_{\mathrm{loc}}-\sum_{i=1}^{t} L_i-4(t-1)\\ &=2\sum_{i=1}^{t} L_i+t+3m \end{aligned}

components.

Every vertex has prescribed degree one or two. Hence every component is a path, and Gocc(Φ)G_{\mathrm{occ}}(\Phi) is a spanning linear forest with exactly c0c_0 path components.

Extending the prescribed forest to the unoccupied local subcubes

The graph Gocc(Φ)G_{\mathrm{occ}}(\Phi) constructed so far spans all vertices in the occupied local subcubes, but it does not yet include the vertices in the unoccupied local subcubes. We now incorporate those remaining local subcubes by path substitutions.

Whenever an already incorporated subcube Qd(α)Q_d(\alpha) is adjacent to a subcube Qd(β)Q_d(\beta) that has not yet been incorporated, we choose an edge xyxy of the prescribed forest lying entirely within Qd(α)Q_d(\alpha), and let x′,y′x',y' be its corresponding vertices in Qd(β)Q_d(\beta). We delete xyxy and replace it with the two cross-subcube edges xx′xx' and yy′yy', together with a Hamiltonian path of Qd(β)Q_d(\beta) from x′x' to y′y'. The chosen edge xyxy must be an internal edge of the prescribed local forest in Qd(α)Q_d(\alpha), so that neither xx nor yy is an endpoint of a path. In particular, xyxy is not adjacent to any prescribed common-channel edge or prescribed bridge-attachment edge. The newly incorporated subcube can then be used in further extensions.

To specify the order of these extensions, choose a multi-source breadth-first forest T\mathcal{T} of QaQ_a, rooted at all addresses corresponding to the initially occupied subcubes. For each address β\beta corresponding to an unoccupied subcube, define its parent to be the neighbor of β\beta immediately preceding it on the unique path in T\mathcal{T} from the root of its tree to β\beta. Conversely, the children of an address α\alpha are all addresses β\beta whose parent is α\alpha. Process the addresses in order of increasing distance from the root set, so that each parent subcube is incorporated before its children. Since QaQ_a has maximum degree aa, each address has at most aa children.

Lemma 3.4 Starting from Gocc(Φ)G_{\mathrm{occ}}(\Phi), the path-substitution process produces the graph GΦ=(V(Qa+d),P(Φ))G_{\Phi}=(V(Q_{a+d}),P(\Phi)), which is a spanning linear forest of Qa+dQ_{a+d}. Moreover, the pairing of the degree-one endpoints of Gocc(Φ)G_{\mathrm{occ}}(\Phi) is preserved, and every vertex in an unoccupied subcube has degree two.

Proof. Let N=2dN=2^d. Each initially occupied subcube contains a spanning linear forest with at most three components, and hence at least N−3N-3 prescribed edges.

When choosing an edge for a path substitution, we avoid all endpoints of the local paths before the prescribed cross-subcube edges are added. These include every degree-one vertex of Gocc(Φ)G_{\mathrm{occ}}(\Phi) in the subcube and every vertex incident with a prescribed cross-subcube edge. Since the local forest has at most three components, there are at most six such vertices, each incident with exactly one local prescribed edge. Excluding these edges leaves at least N−9N-9 eligible edges. Since T\mathcal{T} is a rooted spanning forest of QaQ_a, each address has at most aa children. Thus, each local subcube needs at most aa pairwise vertex-disjoint eligible edges, one for each child. Since the local forest has maximum degree two, each greedy selection eliminates at most three eligible edges, including the selected edge itself. Consequently, we can select the required aa pairwise vertex-disjoint eligible edges whenever N−9>3(a−1)N-9>3(a-1).

Since each of the HH logical legs contains at least seven edges of QaQ_a, we have

∑i=1tLi≥7H,Lmax⁡≥7Ht.\sum_{i=1}^{t} L_i \ge7H,\qquad L_{\max}\ge\frac{7H}{t}.

Moreover, d=3hv+r+8d=3h_v+r+8 and 2hv≥t2^{h_v}\ge t. Hence

N=256⋅2r⋅23hv≥256⋅7Ht⋅t3=1792Ht2.\begin{aligned} N &= 256\cdot2^r\cdot2^{3h_v}\\ &\ge256\cdot\frac{7H}{t}\cdot t^3\\ &=1792Ht^2. \end{aligned}

Since hc≤mh_c\le m, hv≤t−1h_v\le t-1, hω≤th_\omega\le t, and rb≤Hr_b\le H, the definitions of aa and BB give a≤2H+t+8≤3H+8a\le2H+t+8\le3H+8. Combining this bound with N≥1792Ht2N\ge1792Ht^2 and the assumptions m≥1m\ge1 and t≥3t\ge3, we obtain N>3a+6N>3a+6, and consequently N≥2a+4N\ge2a+4. Therefore, every initially occupied local subcube has enough eligible edges for all its children in T\mathcal{T}. For each newly incorporated subcube, write its Hamiltonian path as

⟨w0,w1,…,wN−1⟩.\langle w_0,w_1,\ldots,w_{N-1}\rangle.

Since its address has at most aa children in T\mathcal{T}, reserve the following matching of size aa for their subsequent incorporations: w2kw2k+1w_{2k}w_{2k+1}, k=1,…,ak=1,\ldots,a. These edges avoid both endpoints of the path because N≥2a+4N\ge2a+4.

Now process T\mathcal{T} in the specified order. For each address β\beta outside the root set, use the edge reserved for β\beta in its parent subcube and perform the path substitution described above. If the selected edge in the parent subcube is xyxy, the edge x′y′x'y' in the new subcube corresponds to a Hamiltonian path from x′x' to y′y' of QdQ_d, since d≥2d\ge2.

It therefore preserves acyclicity and the original endpoint pairing. The reserved edges within each parent subcube form a matching, so all substitutions can be carried out in the specified order. Eventually every local subcube is incorporated, and every vertex in a newly incorporated subcube has prescribed degree two. Thus, GΦG_\Phi is a spanning linear forest of QnQ_n with the required properties.

Thus, the construction transforms each 3-SAT instance Φ\Phi into a prescribed-edge graph GΦ=(V(Qa+d),P(Φ))G_\Phi=(V(Q_{a+d}),P(\Phi)) on the hypercube Qa+dQ_{a+d}, yielding the instance (a+d,P(Φ))(a+d,P(\Phi)) of the Hamiltonian-cycle extension problem. The Boolean candidate edges and the optional clause-variable connection edges are not included in P(Φ)P(\Phi).

Boolean Consistency and Soundness

We first show that any Hamiltonian cycle extending P(Φ)P(\Phi) in Qa+dQ_{a+d} can be reduced to a cycle on the occupied local subcubes by reversing the path substitutions of Section 3.7.

Lemma 4.1 Let CC be a Hamiltonian cycle of Qa+dQ_{a+d} containing P(Φ)P(\Phi). Reversing the path substitutions in decreasing distance from the roots of T\mathcal{T} produces a cycle CoccC_{\mathrm{occ}} spanning the occupied vertices and containing every edge of Gocc(Φ)G_{\mathrm{occ}}(\Phi). Moreover,

E(C)∖P(Φ)=E(Cocc)∖E(Gocc(Φ)).E(C)\setminus P(\Phi)=E(C_{\mathrm{occ}})\setminus E(G_{\mathrm{occ}}(\Phi)).

Proof. By Lemma 3.4, every vertex in an unoccupied local subcube has prescribed degree two in P(Φ)P(\Phi), and hence cannot be incident with any non-prescribed edge of CC. Consider a leaf β\beta of the breadth-first forest T\mathcal{T} outside the root set, and let α\alpha be its parent. In Qd(β)Q_d(\beta), the cycle CC must traverse the entire prescribed Hamiltonian path from x′x' to y′y' together with the two prescribed cross-subcube edges xx′xx' and yy′yy'. Replacing the subpath ⟨x,x′,…,y′,y⟩\langle x,x',\ldots,y',y\rangle of CC by the original internal edge xyxy of Qd(α)Q_d(\alpha) yields a single cycle covering all remaining subcubes and containing the pre-substitution prescribed forest. Repeating this contraction in reverse breadth-first order eliminates all unoccupied subcubes without altering any edges incident to degree-one vertices of Gocc(Φ)G_{\mathrm{occ}}(\Phi), yielding the desired cycle CoccC_{\mathrm{occ}}.

At every reversal, the removed path belongs to the current prescribed forest, and the restored edge belongs to the preceding prescribed forest; all completion edges remain unchanged.

By Lemma 4.1, to analyse a Hamiltonian cycle CC containing P(Φ)P(\Phi), it suffices to work with its contracted cycle CoccC_{\mathrm{occ}} on the occupied subcubes. For a variable route xix_i and a route link 0≤j<Li0 \le j < L_i, let ϵi,j,b(C)∈{0,1}\epsilon_{i,j,b}(C) \in\{0,1\} be the indicator function denoting whether CC (and hence CoccC_{\mathrm{occ}}) uses the Boolean cross-subcube edge with local port label Λ(i,j,ζb)\Lambda(i,j,\zeta_b) on that link, where b∈{0,1}b \in\{0,1\} corresponds to ζ0=54\zeta_0=54 and ζ1=46\zeta_1=46. Define αq,k(C)=1\alpha_{q,k}(C)=1 if both gq,k−g_{q,k}^{-} and gq,k+g_{q,k}^{+} belong to E(C)E(C), and αq,k(C)=0\alpha_{q,k}(C)=0 if neither belongs to E(C)E(C).

Lemma 4.2 Let CC be a Hamiltonian cycle of Qa+dQ_{a+d} containing every edge of P(Φ)P(\Phi). Then, for each literal occurrence (q,k)(q,k), the two optional cross-subcube edges gq,k−g_{q,k}^{-} and gq,k+g_{q,k}^{+} either both belong to CC, or neither does.

Proof. In the prescribed three-cut clause forest FqF_q, the edge eq,k=uve_{q,k}=uv is removed, leaving uu and vv with degree one in Gocc(Φ)G_{\mathrm{occ}}(\Phi). In the contracted cycle CoccC_{\mathrm{occ}}, every vertex has degree two, so CoccC_{\mathrm{occ}} must supply exactly one additional incident edge for both uu and vv. By Lemmas 3.1(4) and 3.2, the only degree-feasible edges incident to uu and vv are the internal edge eq,ke_{q,k} and the external cross-subcube edges gq,k−g_{q,k}^{-} and gq,k+g_{q,k}^{+}. If CC uses gq,k−g_{q,k}^{-} at uu, then eq,ke_{q,k} cannot be used, forcing CC to use gq,k+g_{q,k}^{+} at vv. Conversely, if neither external edge is used, CC must restore eq,ke_{q,k}.

For each i∈{1,…,t}i \in\{1,\ldots,t\}, set

ρi={0,i=1,2,2≤i≤t.\rho_i = \begin{cases} 0, & i=1,\\ 2, & 2 \le i \le t. \end{cases}

For each variable xix_i and each 0≤j<Li0 \le j < L_i, define Si,j=⋃r=0jV(Qd(vi,r))S_{i,j}=\bigcup_{r=0}^{j} V(Q_d(v_{i,r})).

Lemma 4.3 Let CC be a Hamiltonian cycle containing every edge of P(Φ)P(\Phi), and let CoccC_{\mathrm{occ}} be its contracted cycle from Lemma 4.1. Then the number of edges of CoccC_{\mathrm{occ}} having exactly one endpoint in Si,jS_{i,j} is

1+ϵi,j,0(C)+ϵi,j,1(C)+ρi+2∑(q,k):i(q,k)=i,p(q,k)≤jαq,k(C).(3)1+\epsilon_{i,j,0}(C)+\epsilon_{i,j,1}(C)+\rho_i+2\sum_{\substack{(q,k):\,i(q,k)=i,\,p(q,k)\le j}}\alpha_{q,k}(C). \tag*{(3)}

Consequently, exactly one of the two Boolean candidates is used on each route link.

Proof. Fix a variable xix_i and an index 0≤j<Li0\le j<L_i. We count the edges of CoccC_{\mathrm{occ}} with exactly one endpoint in Si,jS_{i,j}. Since CoccC_{\mathrm{occ}} is supported entirely on the occupied local subcubes and contains Gocc(Φ)G_{\mathrm{occ}}(\Phi), no edges incident with unoccupied subcubes are present in CoccC_{\mathrm{occ}}, and every non-prescribed edge of CoccC_{\mathrm{occ}} is identical to that of CC.

Among the prescribed common-channel edges along the route of xix_i, only the edge on link jj, joining Qd(vi,j)Q_d(v_{i,j}) and Qd(vi,j+1)Q_d(v_{i,j+1}), has exactly one endpoint in Si,jS_{i,j}. It therefore contributes 1. The two other possible edges on this link are the Boolean candidates corresponding to the ports 46 and 54. Since CC and CoccC_{\mathrm{occ}} share the same non-prescribed edges, their contributions are ϵi,j,0(C)\epsilon_{i,j,0}(C) and ϵi,j,1(C)\epsilon_{i,j,1}(C), respectively.

If i>1i>1, the two bridge-attachment edges at the initial subcube of xix_i have exactly two endpoints in total in Si,jS_{i,j}, one from each edge. Thus, they contribute ρi=2\rho_i=2. For i=1i=1, there is no such bridge, and ρ1=0\rho_1=0.

Finally, consider a literal occurrence (q,k)(q,k) of xix_i at route position p(q,k)≤jp(q,k)\le j. Its two optional clause-variable connection edges join a subcube in Si,jS_{i,j} to the corresponding clause subcube outside Si,jS_{i,j}. By the definition of αq,k(C)\alpha_{q,k}(C), these two edges contribute 2αq,k(C)2\alpha_{q,k}(C). Occurrences with p(q,k)>jp(q,k)>j contribute no edges to this count.

Consequently, adding these contributions gives precisely the expression in (4.1). Since CoccC_{\mathrm{occ}} is a cycle, the number of its edges with exactly one endpoint in Si,jS_{i,j} is even. Hence the number counted in (4.1) is even, which yields

ϵi,j,0(C)+ϵi,j,1(C)≡1(mod2).\epsilon_{i,j,0}(C)+\epsilon_{i,j,1}(C)\equiv1\pmod{2}.

Since both indicators belong to {0,1}\{0,1\}, their sum is exactly 1. Thus, CC uses exactly one of the two Boolean candidates on each route link. □\square

Lemma 4.4 Let CC be a Hamiltonian cycle containing every edge of P(Φ)P(\Phi). For each internal route position vi,pv_{i,p}, the Boolean candidate edges selected by CC on its two incident route links have the same local port label in {46,54}\{46,54\}. Moreover, if vi,pv_{i,p} is the literal socket for (q,k)(q,k) and αq,k(C)=1\alpha_{q,k}(C)=1, then this common label is ζ1−b(q,k)\zeta_{1-b(q,k)}, while the two clause-variable connection edges use ζb(q,k)\zeta_{b(q,k)}.

Proof. In the W9W_9-subcube at vi,pv_{i,p}, the prescribed forest consists of the common-channel path and two Boolean paths whose endpoint pairs are {Λ(i,p−1,46),Λ(i,p−1,54)}\{\Lambda(i,p-1,46),\Lambda(i,p-1,54)\} on the side of link p−1p-1 and {Λ(i,p,46),Λ(i,p,54)}\{\Lambda(i,p,46),\Lambda(i,p,54)\} on the side of link pp (corresponding to {46,54}\{46,54\} and {302,310}\{302,310\} in Lemma 2.2). Since the two endpoints of the common-channel path already have degree two in Gocc(Φ)G_{\mathrm{occ}}(\Phi), they cannot be incident with any additional edge in CoccC_{\mathrm{occ}}.

By Lemma 4.3, CoccC_{\mathrm{occ}} uses exactly one Boolean candidate edge on link p−1p-1, say at port ζ∈{46,54}\zeta\in\{46,54\}, which saturates Λ(i,p−1,ζ)\Lambda(i,p-1,\zeta) to degree two. Let ζ′\zeta' be the complementary port in {46,54}\{46,54\}. Since the Boolean candidate edge at Λ(i,p−1,ζ′)\Lambda(i,p-1,\zeta') on link p−1p-1 is not used, the degree-one vertex Λ(i,p−1,ζ′)\Lambda(i,p-1,\zeta') must receive its second incident edge in CoccC_{\mathrm{occ}} either from the internal residual edge set R(W9)R(W_9) or from an external clause connection. By Lemma 2.2 and Lemma 3.2, the only such edges incident to Λ(i,p−1,ζ′)\Lambda(i,p-1,\zeta') are the internal residual edge {Λ(i,p−1,ζ′),Λ(i,p,ζ′)}\{\Lambda(i,p-1,\zeta'),\Lambda(i,p,\zeta')\} (corresponding to {46,302}\{46,302\} or {54,310}\{54,310\}) and, when vi,pv_{i,p} is the literal socket for (q,k)(q,k) with ζ′=ζb(q,k)\zeta'=\zeta_{b(q,k)}, the external edge gq,k−g_{q,k}^{-}.

If CoccC_{\mathrm{occ}} uses the internal residual edge {Λ(i,p−1,ζ′),Λ(i,p,ζ′)}\{\Lambda(i,p-1,\zeta'),\Lambda(i,p,\zeta')\}, then the endpoint Λ(i,p,ζ′)\Lambda(i,p,\zeta') on the side of link pp also reaches degree two. If instead CoccC_{\mathrm{occ}} uses gq,k−g_{q,k}^{-}, then Lemma 4.2 forces gq,k+∈E(Cocc)g_{q,k}^{+}\in E(C_{\mathrm{occ}}), which is incident to Λ(i,p,ζ′)\Lambda(i,p,\zeta') and likewise saturates Λ(i,p,ζ′)\Lambda(i,p,\zeta') to degree two. In either case, Λ(i,p,ζ′)\Lambda(i,p,\zeta') cannot be incident with the Boolean candidate edge on link pp. Since Lemma 4.3 requires CoccC_{\mathrm{occ}} to use a Boolean candidate edge on link pp, it must use the one incident to the remaining available endpoint Λ(i,p,ζ)\Lambda(i,p,\zeta). Hence links p−1p-1 and pp select the same port label ζ\zeta. Moreover, when αq,k(C)=1\alpha_{q,k}(C)=1, both gq,k−g_{q,k}^{-} and gq,k+g_{q,k}^{+} belong to CoccC_{\mathrm{occ}} and saturate the endpoints labeled ζb(q,k)\zeta_{b(q,k)}, forcing ζ′=ζb(q,k)\zeta'=\zeta_{b(q,k)} and ζ=ζ1−b(q,k)\zeta=\zeta_{1-b(q,k)}.

Lemma 4.5 Every Hamiltonian extension of P(Φ)P(\Phi) induces a satisfying assignment of Φ\Phi.

Proof. Let CC be a Hamiltonian cycle containing every edge of the final prescribed set P(Φ)P(\Phi), and let CoccC_{\mathrm{occ}} be its contracted cycle from Lemma 4.1.

By Lemma 4.3, exactly one of the two Boolean candidate edges is used on each route link 0≤j<Li0 \le j < L_i. Moreover, Lemma 4.4 forces the Boolean candidate edges on the two route links incident with each W9W_9-subcube to have the same local port label. Consequently, all route links of a given variable xix_i use the same Boolean port. Define the assignment by setting xi=0x_i=0 if this port is 46, and xi=1x_i=1 if it is 54. We next show that every activated literal is true under this assignment. Suppose that the occurrence (q,k)(q,k) of xix_i is activated, so that αq,k(C)=1\alpha_{q,k}(C)=1. The two corresponding clause-variable connection edges use the port ζb(q,k)\zeta_{b(q,k)} at the two sides of the W9W_9-subcube. These edges saturate their incident vertices, so the Boolean channel must use the other port, namely ζ1−b(q,k)\zeta_{1-b(q,k)}. Since ζ0=54\zeta_0=54 and ζ1=46\zeta_1=46, this means that the variable route uses port 46 when b(q,k)=0b(q,k)=0 and port 54 when b(q,k)=1b(q,k)=1. Thus xi=b(q,k)x_i=b(q,k), which is precisely the value that makes the literal occurrence (q,k)(q,k) true.

It remains to show that every clause has an activated occurrence. Fix a clause CqC_q and suppose that none of its occurrences is activated. The contracted cycle CoccC_{\mathrm{occ}} contains the original clause forest FqF_q. By Lemma 3.1(4) and Lemma 3.2, each endpoint of eq,ke_{q,k} can receive its additional incident edge only by restoring eq,ke_{q,k} or by using the corresponding clause-variable edge. Since no occurrence is activated, CoccC_{\mathrm{occ}} contains none of the six clause-variable edges. It must therefore contain all three cut edges eq,1,eq,2,eq,3e_{q,1},e_{q,2},e_{q,3}, closing the three-cut clause forest FqF_q into a separate cycle component and contradicting that CoccC_{\mathrm{occ}} is a single cycle.

Therefore, every clause has at least one activated occurrence. By the preceding argument, each such occurrence is a true literal under the assignment defined above. Hence every clause of Φ\Phi is satisfied, and Φ\Phi is satisfiable.

Completeness and complexity

The preceding section has established that every Hamiltonian cycle containing P(Φ)P(\Phi) induces a satisfying assignment of Φ\Phi. We now prove the converse. Our task is therefore to select additional edges, according to a satisfying assignment σ\sigma of Φ\Phi, so that the resulting graph is a Hamiltonian cycle containing every edge of P(Φ)P(\Phi).

Lemma 5.1 For every satisfying assignment of Φ\Phi, there exists a Hamiltonian cycle of Qa+dQ_{a+d} containing every edge of P(Φ)P(\Phi).

Proof. Fix a satisfying assignment σ\sigma of Φ\Phi, and put ηi=σ(xi)\eta_i=\sigma(x_i) for 1≤i≤t1\leq i\leq t. First, we construct a Hamiltonian cycle CoccC_{\mathrm{occ}} covering all vertices in the occupied local subcubes and containing every edge of Gocc(Φ)G_{\mathrm{occ}}(\Phi).

For each variable xix_i, let ζ=ζ1−ηi\zeta=\zeta_{1-\eta_i} and ζ′=ζηi\zeta'=\zeta_{\eta_i} (so ζ=46\zeta=46 and ζ′=54\zeta'=54 when ηi=0\eta_i=0, and vice versa when ηi=1\eta_i=1). Temporarily restore the deleted internal edges corresponding to {150,182}\{150,182\} in the bridge-incident terminal A8A_8-subcubes so that every terminal subcube at vi,0v_{i,0} and vi,Liv_{i,L_i} contains the full two-path forest A8A_8 of Lemma 2.1. We assemble a cycle for variable xix_i as follows:

  1. Along all route links $0 \le j < L_i$, the prescribed common-channel edges join the common-channel paths of all local subcubes on the route into a single path running from Λ(i,0,38)\Lambda(i,0,38) in Qd(vi,0)Q_d(v_{i,0}) to Λ(i,Li−1,38)\Lambda(i,L_i-1,38) in $Q_d(v_{i,L_i}) (since χ0=χLi−1=14\chi_0 = \chi_{L_i-1} = 14 as LiL_i is odd).

  1. On every route link 0≤j<Li0 \le j < L_i, select the Boolean candidate cross-subcube edge at port ζ\zeta. Inside each internal W9W_9-subcube at vi,pv_{i,p} (0<p<Li0 < p < L_i), select the internal residual edge {Λ(i,p−1,ζ′),Λ(i,p,ζ′)}\{\Lambda(i,p-1,\zeta'),\Lambda(i,p,\zeta')\} (corresponding to {46,302}\{46,302\} or {54,310}\{54,310\} in Lemma 2.2). Together with the prescribed Boolean paths in the local subcubes, these edges form a second disjoint path running from Λ(i,0,ζ′)\Lambda(i,0,\zeta') in Qd(vi,0)Q_d(v_{i,0}) to Λ(i,Li−1,ζ′)\Lambda(i,L_i-1,\zeta') in Qd(vi,Li)Q_d(v_{i,L_i}).

  1. At the initial subcube Qd(vi,0)Q_d(v_{i,0}) and the terminal subcube Qd(vi,Li)Q_d(v_{i,L_i}), close the two paths into a single cycle spanning the variable route of xix_i by adding the terminal residual edges {Λ(i,0,38),Λ(i,0,ζ′)}\{\Lambda(i,0,38),\Lambda(i,0,\zeta')\} and {Λ(i,Li−1,38),Λ(i,Li−1,ζ′)}\{\Lambda(i,L_i-1,38),\Lambda(i,L_i-1,\zeta')\} from R(A8)={{14,46},{38,46},{38,54}}R(A_8) = \{\{14,46\},\{38,46\},\{38,54\}\}.

Next, for each 1≤i<t1 \le i < t, remove the temporarily restored internal edges {Λ(i,Li−1,150),Λ(i,Li−1,182)}\{\Lambda(i,L_i-1,150),\Lambda(i,L_i-1,182)\} in Qd(vi,Li)Q_d(v_{i,L_i}) and {Λ(i+1,0,150),Λ(i+1,0,182)}\{\Lambda(i+1,0,150),\Lambda(i+1,0,182)\} in Qd(vi+1,0)Q_d(v_{i+1,0}). Join the exposed endpoints across the two-cut bridge forest in Qd((bi,0,00))Q_d((b_i,0,00)) via the four prescribed bridge-attachment edges. Since each bridge splices two distinct cycles by replacing one internal edge in each with two disjoint connecting paths, doing this for all 1≤i<t1 \le i < t merges the tt variable cycles into a single cycle covering all variable and bridge subcubes.

For each clause CqC_q, choose a literal occurrence (q,k)(q,k) that is true under σ\sigma, and put i=i(q,k)i = i(q,k) and p=p(q,k)p = p(q,k). Then ηi=b(q,k)\eta_i = b(q,k), so the residual edge {Λ(i,p−1,ζb(q,k)),Λ(i,p,ζb(q,k))}\{\Lambda(i,p-1,\zeta_{b(q,k)}),\Lambda(i,p,\zeta_{b(q,k)})\} was selected in step (2). Replace this edge by gq,kg_{q,k}, the Hamiltonian path Fq+{eq,k′:k′≠k}F_q + \{e_{q,k'}: k' \ne k\} through the clause subcube, and gq,kg_{q,k}. Each replacement incorporates a new clause subcube and preserves a single cycle. After all clauses have been incorporated, the resulting Hamiltonian cycle CoccC_{\mathrm{occ}} spans the occupied vertices and contains every edge of Gocc(Φ)G_{\mathrm{occ}}(\Phi).

Finally, apply to CoccC_{\mathrm{occ}} the exact sequence of path substitutions from § 3.7 used to obtain P(Φ)P(\Phi) from Gocc(Φ)G_{\mathrm{occ}}(\Phi), maintaining a current cycle throughout. At each step, the selected internal edge xyxy of the current prescribed forest belongs to the current cycle. Replacing xyxy by the two prescribed cross-subcube edges xx′xx',yy′yy' and the prescribed Hamiltonian path through the newly incorporated subcube preserves a single cycle containing the updated prescribed forest. After all substitutions, the resulting graph is a Hamiltonian cycle of Qa+dQ_{a+d} containing P(Φ)P(\Phi).

To complete the complexity analysis, it remains to verify that the reduction can be carried out in polynomial time and that the decision problem itself belongs to NP.

Lemma 5.2 The mapping Φ↦(a+d,P(Φ))\Phi\mapsto(a+d,P(\Phi)), where P(Φ)P(\Phi) is given by its edge list, is computable in polynomial time. Moreover, the spanning linear-forest hamiltonian-cycle extension problem belongs to NP.

Proof. Let K=⌈log⁡2(H+1)⌉K=\lceil\log_2(H+1)\rceil, where H=3m+t≤6mH=3m+t\le6m. Here H≥6H\ge6 and K≥3K\ge3. We have rb=Kr_b=K, hc,hv≤Kh_c,h_v\le K, and hω≤K+1h_\omega\le K+1. Therefore B≤5K+8B\le5K+8 and a≤6K+10a\le6K+10. Each leg requires at most BB changes in the base-address block, at most 2rb2r_b changes in the route-tag block for the transitions 0→z0\to z and z→0z\to0, and four changes in the lane label. Thus its length is at most B+2rb+4≤7K+12B+2r_b+4\le7K+12. Consequently,

Lmax⁡≤H(7K+12)<22K+3.L_{\max}\le H(7K+12)<2^{2K+3}.

using H<2KH<2^K and 7K+12≤2K+37K+12\le2^{K+3} for K≥3K\ge3. Hence r=⌈log⁡2Lmax⁡⌉≤2K+3r=\lceil\log_2 L_{\max}\rceil\le2K+3, d=8+r+3hv≤5K+11d=8+r+3h_v\le5K+11, and n≤11K+21n\le11K+21. In particular, 2n≤211K+21<232(H+1)112^n\le2^{11K+21}<2^{32}(H+1)^{11}. Since P(Φ)P(\Phi) has maximum degree two, it contains at most 2n2^n edges. Each edge is specified by two nn-bit endpoints, so its explicit edge list requires O(n2n)=O((H+1)11log⁡(H+1))O(n2^n)=O((H+1)^{11}\log(H+1)) bits. As H≤6mH\le6m, the output length is polynomial in the bit length of Φ\Phi.

The variable routes and prescribed cross-subcube joins can be generated by the rules in § 3.1–§ 3.3. The A8A_8- and W9W_9-subcubes given in Lemmas 2.1 and 2.2 and their expansions can be constructed in O(2ddO(1))O(2^d d^{O(1)}) time per subcube. Lemma 2.4 constructs each clause and bridge cycle within the same time bound. The breadth-first forest can be generated by inspecting at most a2aa2^a address neighbors. The reserved edges can be selected and the path substitutions of Lemma 3.4 performed in O(2dnO(1))O(2^d n^{O(1)}) time per address. The prescribed edge set can be maintained throughout the construction and then output as an explicit edge list. Since there are at most 2a2^a local subcubes, the construction takes O(2anO(1))O(2^a n^{O(1)}) time after reading and relabeling the formula. The bounds above therefore show that the total running time is polynomial in the bit length of Φ\Phi.

For membership in NP, consider any instance (n,P)(n, P) of the problem. Since every vertex has prescribed degree at least one, 2n≤2∣P∣2^n \le2|P|. A certificate is a cyclic ordering of all 2n2^n vertices, requiring O(n2n)=O(n∣P∣)O(n2^n) = O(n|P|) bits, which is polynomial in the input length. In polynomial time, we can verify that every vertex occurs exactly once, that consecutive vertices, including the last and first, are adjacent in QnQ_n, and that the cycle contains every edge of PP. Hence, the problem belongs to NP. □

We now combine Lemmas 4.5, 5.1, and 5.2 to prove Theorem 1.1.

Proof of Theorem 1.1. The 3-SAT problem in which every clause contains three literals on three distinct variables is NP-complete. Given a formula Φ\Phi in this problem, the construction in § 3 produces an instance (a+d,P(Φ))(a+d, P(\Phi)) of the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem, where P(Φ)P(\Phi) is a spanning linear forest of Qa+dQ_{a+d} and every vertex has prescribed degree either one or two. By Lemmas 4.5 and 5.1, Φ\Phi is satisfiable if and only if there exists a Hamiltonian cycle of Qa+dQ_{a+d} containing every edge of P(Φ)P(\Phi). By Lemma 5.2, the mapping Φ↦(a+d,P(Φ))\Phi\mapsto(a+d, P(\Phi)) is computable in polynomial time. Hence, the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem is NP-hard. Moreover, by the same complexity lemma, it belongs to NP. Therefore, the problem is NP-complete. □

We conclude this section by deriving two further NP-hardness results for broader classes of prescribed edge sets. Both problems use the same input representation and Hamiltonian-cycle extension question as the SPANNING LINEAR-FOREST HAMILTONIAN-CYCLE EXTENSION problem, but impose weaker structural restrictions on the prescribed edge set.

Linear-Forest Hamiltonian-Cycle Extension

Instance: An integer n≥2n \ge2, encoded in binary, and an explicitly listed edge set P⊆E(Qn)P \subseteq E(Q_n) such that (V(P),P)(V(P), P) is a linear forest, where V(P)V(P) denotes the set of vertices incident with edges in PP.

Question: Does QnQ_n contain a Hamiltonian cycle CC such that P⊆E(C)P \subseteq E(C)?

Prescribed-Edge Hamiltonian-Cycle Extension

Instance: An integer n≥2n \ge2, encoded in binary, and an explicitly listed edge set P⊆E(Qn)P \subseteq E(Q_n).

Question: Does QnQ_n contain a Hamiltonian cycle CC such that P⊆E(C)P \subseteq E(C)?

Corollary 5.3. The linear-forest hamiltonian-cycle extension problem is NP-hard. Moreover, the prescribed-edge hamiltonian-cycle extension problem is also NP-hard.

Proof. The reduction constructed in the proof of Theorem 1.1 maps every source 3-SAT instance Φ\Phi to an instance (a+d,P(Φ))(a+d, P(\Phi)) in which P(Φ)P(\Phi) is a spanning linear forest and every vertex has prescribed degree one or two. Consequently, every instance produced by this reduction satisfies the input restrictions of both the linear-forest hamiltonian-cycle extension problem and the unrestricted prescribed-edge hamiltonian-cycle extension problem.

By Lemmas 4.5 and 5.1, Φ\Phi is satisfiable if and only if P(Φ)P(\Phi) is contained in a Hamiltonian cycle of Qa+dQ_{a+d}. Moreover, the reduction is computable in polynomial time by Lemma 5.2. Hence, the same reduction establishes NP-hardness for both problems.

The same reduction establishes NP-hardness for both problems when the host hypercube is given by explicit vertex and edge lists, since the constructed dimension satisfies n=O(log⁡∣Φ∣)n = O(\log|\Phi|). Under this representation, a Hamiltonian cycle is a polynomial-size certificate that can be verified in polynomial time, so both problems are NP-complete.

Concluding Remarks

We prove that the Hamiltonian-cycle extension problem on hypercubes is NP-complete when the prescribed edge set is a spanning linear forest in which every vertex has prescribed degree one or two. The same reduction also establishes NP-hardness when the prescribed edge set is a linear forest not necessarily spanning, and even when no structural restrictions are imposed on the prescribed edge set. For sparse prescribed-edge instances in these more general settings, however, an explicit Hamiltonian cycle may have superpolynomial size relative to the input. Consequently, the usual explicit-cycle certificate does not establish membership in NP for these more general problems, although this does not rule out the existence of other polynomial-size certificates.

An especially restrictive special case of the prescribed-edge extension problem arises when PP is a matching. This is the setting of the Ruskey-Savage conjecture, which asks whether every matching of QnQ_n, for every n≥2n \ge2, can be extended to a Hamiltonian cycle. Our reduction does not address this case, since the prescribed forests produced by our construction contain vertices of prescribed degree two and hence are not matchings. Investigating the Hamiltonian-cycle extension problem when the prescribed edge set is restricted to a matching is a natural direction for further research.

References

  1. [1]A. Ali, G. Ali, W. Yang, Extending the size of matchings to Hamiltonian cycles in hypercubes, Journal of Interconnection Networks 26 (4) (2026) 2550021.DOI
  2. [2]R. Caha, V. Koubek, Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, Journal of Graph Theory 51 (2) (2006) 137–169.DOI
  3. [3]M. Y. Chan, S.-J. Lee, On the existence of Hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics 4 (4) (1991) 511–527.DOI
  4. [4]M.-S. Chen, K. G. Shin, Processor allocation in an N-cube multiprocessor using Gray codes, IEEE Transactions on Computers C-36 (12) (1987) 1396–1407.DOI
  5. [5]D. Cheng, Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes, Discrete Applied Mathematics 262 (2019) 56–71.DOI
  6. [6]T. Dvořák, Hamiltonian cycles with prescribed edges in hypercubes, SIAM Journal on Discrete Mathematics 19 (1) (2005) 135–144.DOI
  7. [7]T. Dvořák, J. Fink, Gray codes extending quadratic matchings, Journal of Graph Theory 90 (2) (2019) 123–136.DOI
  8. [8]T. Dvořák, P. Gregor, Hamiltonian paths with prescribed edges in hypercubes, Discrete Mathematics 307 (16) (2007) 1982–1998.DOI
  9. [9]J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, Journal of Combinatorial Theory, Series B 97 (6) (2007) 1074–1076.DOI
  10. [10]J. Fink, V. Hotmar, Matchings with five directions in hypercubes extend to Hamilton cycles and paths with prescribed ends, in: H. Fernau, P. Kindermann (Eds.), Graph-Theoretic Concepts in Computer Science, Vol. 16124 of Lecture Notes in Computer Science, 2026, pp. 258–269.
  11. [11]J. Fink, T. Mütze, Matchings in hypercubes extend to long cycles, SIAM Journal on Discrete Mathematics 39 (3) (2025) 1826–1854.
  12. [12]R. M. Karp, Reducibility among combinatorial problems, in: R. E. Miller, J. W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103.
  13. [13]H. Liu, F. Wang, Hamiltonian paths passing through prescribed edges in balanced hypercubes, Theoretical Computer Science 761 (2019) 23–33.
  14. [14]C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  15. [15]F. Ruskey, C. D. Savage, Hamilton cycles that extend transposition matchings in Cayley graphs of Sₙ, SIAM Journal on Discrete Mathematics 6 (1) (1993) 152–166.
  16. [16]C. D. Savage, A survey of combinatorial Gray codes, SIAM Review 39 (4) (1997) 605–629.DOI
  17. [17]I. A. Stewart, Hamiltonian cycles through prescribed edges in k-ary n-cubes, in: Combinatorial Optimization and Applications (COCOA 2011), Vol. 6831 of Lecture Notes in Computer Science, Springer, 2011, pp. 82–97.DOI
  18. [18]F. Wang, H. Zhang, Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges, Discrete Mathematics 321 (2014) 35–44.arxiv.org/abs/1301.2931
  19. [19]F. Wang, H. Zhang, Small matchings extend to Hamiltonian cycles in hypercubes, Graphs and Combinatorics 32 (2016) 363–376.DOI
  20. [20]F. Wang, W. Zhao, Matchings extend to Hamiltonian cycles in 5-cube, Discussiones Mathematicae Graph Theory 38 (2018) 217–231.DOI
  21. [21]S. Wang, F. Wang, A kind of matchings extend to Hamiltonian cycles in hypercubes, RAIRO-Operations Research 58 (2024) 5237–5254.DOI
  22. [22]Y. Yang, L. Zhang, Hamiltonian paths of k-ary n-cubes avoiding faulty links and passing through prescribed linear forests, IEEE Transactions on Parallel and Distributed Systems 33 (7) (2022) 1752–1760.
  23. [23]W. Zuo, H. Lü, On extending restricted matchings to Hamiltonian cycles in hypercubes, Discussiones Mathematicae Graph Theory, accepted (2026).

Paper details

vlnc:W_tx2c7mtc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents