Problem Detail: 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’= & Vcup{v_{alpha},v_{beta},v_{gamma}},v_{alpha},v_{beta},v_{gamma}notin V E’= & Ecup{(v_{alpha},v_{beta}),(v_{beta},v_{gamma})}cup{bigcup_{iin{alpha,gamma},vin 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 Gin$ HP And thus $Gin$ HP iff $f(G)=G’in$ HCE. Since $f$ can run in p-time, HP $leq$ HCE. $therefore$ HCE is NP-complete.
Asked By : Lawliet
Answered By : Lawliet
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’= & Vcup{v_{alpha},v_{beta},v_{gamma}},v_{alpha},v_{beta},v_{gamma}notin V E’= & Ecup{(v_{alpha},v_{beta}),(v_{beta},v_{gamma})}cup{bigcup_{iin{alpha,gamma},vin 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 Gin$ HP And thus $Gin$ HP iff $f(G)=G’in$ HCE. Since $f$ can run in p-time, HP $leq$ HCE. $therefore$ HCE is NP-complete.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/17999
