patternMinor
Almost Hamiltonian
Viewed 0 times
almosthamiltonianstackoverflow
Problem
A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice.
Is the problem of determining whether a graph is almost Hamiltonian NP-complete?
Is the problem of determining whether a graph is almost Hamiltonian NP-complete?
Solution
Yes it is NP-complete. Membership in NP is trivial. Thus, we must only show NP-hardness. To do so, we use a reduction from the original Hamilton cycle problem.
Given a graph $G=(\{v_1,\dots,v_n\},E)$, we can construct a new Graph $G'=(\{v_1,\dots,v_n\}\cup\{v_1',\dots,v_n'\},E \cup \{(v_i,v_i')\mid 1\leq i\leq n\} \cup \{(v_i',v_i)\mid 1\leq i\leq n\})$. Note that in order to reach one of the nodes $v_i'$, one must visit $v_i$ twice on a cycle $v_i - v_i' - v_i$. Apart from that, the edges in $G'$ are the same as in $G$. Thus, $G'$ is almost Hamiltonian if and only if $G$ is Hamiltonian, which completes the proof.
Given a graph $G=(\{v_1,\dots,v_n\},E)$, we can construct a new Graph $G'=(\{v_1,\dots,v_n\}\cup\{v_1',\dots,v_n'\},E \cup \{(v_i,v_i')\mid 1\leq i\leq n\} \cup \{(v_i',v_i)\mid 1\leq i\leq n\})$. Note that in order to reach one of the nodes $v_i'$, one must visit $v_i$ twice on a cycle $v_i - v_i' - v_i$. Apart from that, the edges in $G'$ are the same as in $G$. Thus, $G'$ is almost Hamiltonian if and only if $G$ is Hamiltonian, which completes the proof.
Context
StackExchange Computer Science Q#48324, answer score: 4
Revisions (0)
No revisions yet.