# Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated!

Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is NP-complete.

HCE: Given an undirected graph G and an edge e of G, does G have a Hamiltonian circuit/cycle that uses e?

I've tried to approach this by showing that HC $\leq$ HCE, but I'm wondering if my approach is too convoluted.

EDIT:

I think I have a solution. Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$, and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat*}{1} V'= & V\cup\{v_{\alpha},v_{\beta},v_{\gamma}\},v_{\alpha},v_{\beta},v_{\gamma}\notin V\\ E'= & E\cup\{(v_{\alpha},v_{\beta}),(v_{\beta},v_{\gamma})\}\cup\{\bigcup_{i\in\{\alpha,\gamma\},v\in V}(v,v_{i})\} \end{alignat*}

Let the edge $e=(v_{\alpha},v_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v_{\alpha}$ and $v_{\gamma}$ are connected to all the vertices in $G$ and $v_{\beta}$. $v_{\beta}$ has a degree of 2, and is only connected to $v_{\alpha}$and $v_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v_{1},v_{2},...,v_{n}$. Then $G'$ will also have a path $v_{1},v_{2},...,v_{n}$ with each vertex only appearing once in the path. In order to turn this path into a HC, the three additional vertices will have to be included. In order to do so, the path has to be extended in either $v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$ or $v_{n},v_{\gamma},v_{\beta},v_{\alpha},v_{1}$. $G'$ thus have a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP \impliesf(G)=G'\in HCE Consider some G' with a HCE along some path v_{1},v_{2},...,v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}. Since G has vertices V=V'\backslash{v_{\alpha},v_{\beta},v_{\gamma}}, G has a HP along vertices v_{1},v_{2},...,v_{n}. \therefore G'\in HCE \implies G\in HP And thus G\in HP iff f(G)=G'\in HCE. Since f can run in p-time, HP \leq HCE. \therefore HCE is NP-complete. • Can't you use Turing reduction, where for each edge you check if there's a HC going though it? – avakar Nov 18 '13 at 18:33 • @avakar No. NP-completeness is defined with respect to many-one reductions, not Turing reductions. – David Richerby Jan 15 '14 at 15:59 • @Lawliet You should convert your edit into an answer. (Answer your own question!) – Yuval Filmus Apr 16 '14 at 1:01 ## 3 Answers Given: a graph G, an edge e, and a length k. Optimization problem output: a cycle of length k, containing e (or none, if there is none). Decision problem output: "yes" if such a cycle exists, "no" otherwise. Now, it is obviously in NP, as you can simply check any answer to the optimization problem; see if it is a cycle, see if the cycle contains e, and check that the length of the cycle is k. There are two easy ways to prove it is NP-hard. Imagine you had a magic algorithm, {\rm M{\small AGIC}}(G,e,k), that can answer this for you. Method 1 hint: In the k-SAT to DHC (directed Hamiltonian cycle) reduction, aren't there some edges that must occur? (and don't these carry over to UHC (undirected Hamiltonian cycle)?) More hints (mouseover): The reduction from k-SAT to DHC (directed Hamiltonian cycle) involved a root node, and a sink node. The sink node has an edge to the root node; and it is the only incoming edge to the root node; hence, the sink-root edge must be used in the DHC. Furthermore, in the reduction from DHC to UHC, each node gets split into 3 nodes, and the middle one is connected to the two outer ones with a single edge. Well, as a general rule, any degree-2 nodes make it easy to solve this problem (because the cycle must pass through it). Method 2 hint: What happens if you pick a node. The Hamiltonian Cycle must pass through one of its edges. How many edges can a node have? More hints (mouseover): Maybe you can solve a regular UHC with some calls to {\rm M{\small AGIC}}(G,e,k). • Method 2 doesn't work. It's a Turing reduction but NP-completeness is defined with respect to many-one reductions. – David Richerby Jan 15 '14 at 15:59 This nice answer to CS theory post, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs?, provides an answer to your question (even when input graphs restricted to cubic graphs). I think I have a solution. Consider a graph G=(V,E) where V is the set of vertices in G, and E is the set of edges in G. Let f(G)=G'=(V',E') where \begin{alignat*}{1} V'= & V\cup\{v_{\alpha},v_{\beta},v_{\gamma}\},v_{\alpha},v_{\beta},v_{\gamma}\notin V\\ E'= & E\cup\{(v_{\alpha},v_{\beta}),(v_{\beta},v_{\gamma})\}\cup\{\bigcup_{i\in\{\alpha,\gamma\},v\in V}(v,v_{i})\} \end{alignat*} Let the edge e=(v_{\alpha},v_{\beta}). G'is the graph G with three additional vertices. v_{\alpha} and v_{\gamma} are connected to all the vertices in G and v_{\beta}. v_{\beta} has a degree of 2, and is only connected to v_{\alpha}and v_{\gamma}. f can be computed in p-time. Consider some G that has a HP along vertices v_{1},v_{2},...,v_{n}. Then G' will also have a path v_{1},v_{2},...,v_{n} with each vertex only appearing once in the path. In order to turn this path into a HC, the three additional vertices will have to be included. In order to do so, the path has to be extended in either v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1} or v_{n},v_{\gamma},v_{\beta},v_{\alpha},v_{1}. G' thus have a HC that will always include the edge e. \therefore G \in HP \impliesf(G)=G'\in HCE

Consider some $G'$ with a HCE along some path $v_{1},v_{2},...,v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$. Since $G$ has vertices $V=V'\backslash{v_{\alpha},v_{\beta},v_{\gamma}}$, $G$ has a HP along vertices $v_{1},v_{2},...,v_{n}$.

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time, HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.