The Green Path Problem is as follows: given a graph $G$ with $n/2$ green vertices and $n/2$ red vertices, is there a simple path from $v_1$ to $v_n$ that contains every green vertex? The path can include any number of red vertices.

It is fairly obviously that if $G$ has a Hamiltonian path, then $G$ must also have a green path (if there's a simple path that hits all the vertices, then there's a simple path that hits all the green vertices).

But what about the other way around? $G$ having a green path, to me, does not necessarily imply that $G$ should also have a Hamiltonian path. This is where I am struggling to prove that the Green Path Problem is NP-complete.

My current train of thought it to somehow manipulate the edges of $G$ such that all Hamiltonian paths include all $n/2$ green vertices, but I am not sure how to go about doing this.

I would appreciate any insight into this reduction!


You don't need to use the same graph in both problems. Try constructing a new graph $H$ that is somehow based on $G$, such that $G$ has a Hamiltonian path if and only if $H$ has a green path.

  • $\begingroup$ How does this sound: let $H$ be a new graph in which there is a Hamiltonian path through all the green vertices, and a Hamiltonian path through all the red vertices. If we connect the two endpoints of these subgraphs, we would get a Hamiltonian path through $H$. $\endgroup$ – kanker7 Apr 21 '16 at 17:12
  • $\begingroup$ @kanker7 That construction of $H$ doesn't seem to involve $G$ at all, so it doesn't give you any information about whether $G$ has a Hamiltonian path. $\endgroup$ – Gregory J. Puleo Apr 21 '16 at 17:13
  • $\begingroup$ Hmm, you're right. Any tips on going forward? $\endgroup$ – kanker7 Apr 21 '16 at 17:14
  • $\begingroup$ @kanker7 try starting with G and then adding some extra vertices. The idea may be easier to see if you initially don't worry about getting exactly n/2 red vertices. $\endgroup$ – Gregory J. Puleo Apr 21 '16 at 17:21
  • $\begingroup$ I think I have it... Let $H = G\cup \{s,t\}$, where $(s, v_1)\in H.edges$ and $(v_k, t)\in H.edges$ and $v_1$ and $v_k$ are green vertices. Then, G has a green path iff $H$ has a Hamiltonian path from $s$ to $t$. $\endgroup$ – kanker7 Apr 21 '16 at 17:28

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.