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?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$– D.W. ♦Commented Oct 16, 2015 at 17:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ You might consider not encouraging undesirable posting behaviour. Up to you -- your choice. $\endgroup$– D.W. ♦Commented Oct 16, 2015 at 17:53