6
$\begingroup$

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 $\implies$$f(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.

$\endgroup$
  • $\begingroup$ Can't you use Turing reduction, where for each edge you check if there's a HC going though it? $\endgroup$ – avakar Nov 18 '13 at 18:33
  • $\begingroup$ @avakar No. NP-completeness is defined with respect to many-one reductions, not Turing reductions. $\endgroup$ – David Richerby Jan 15 '14 at 15:59
  • 1
    $\begingroup$ @Lawliet You should convert your edit into an answer. (Answer your own question!) $\endgroup$ – Yuval Filmus Apr 16 '14 at 1:01
1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Method 2 doesn't work. It's a Turing reduction but NP-completeness is defined with respect to many-one reductions. $\endgroup$ – David Richerby Jan 15 '14 at 15:59
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 $\implies$$f(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.