# Reducing Hamiltonian Path Problem to Green Path Problem

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.
• 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$. – kanker7 Apr 21 '16 at 17:12
• @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. – Gregory J. Puleo Apr 21 '16 at 17:13
• 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$. – kanker7 Apr 21 '16 at 17:28