1
$\begingroup$

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!

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2016 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$ Apr 21, 2016 at 17:13
  • $\begingroup$ Hmm, you're right. Any tips on going forward? $\endgroup$
    – kanker7
    Apr 21, 2016 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$ Apr 21, 2016 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, 2016 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .