World's most popular travel blog for travel bloggers.

[Solved]: Proving DPATH is NP-complete by a reduction from HAMPATH

, , No Comments
Problem Detail: 

I have a language DPATH that I'm trying to complete is NP-complete.

DPATH = {<G, a1,...,an>|G is a digraph with a directed path that covers the sequence a1,...,an} 

All of the nodes in the sequence has to be visited exactly one time, but it doesn't matter in which order they are visited.

I am trying to show a reduction from HAMPATH to DPATH but I'm having some difficulties. When given input <G, s, t> I have to create a computable function f, that outputs <G, a1,...,an>. Can i say that a1 = s, and an = t, and that each node that the hamiltonian path goes through is labeled with a node from the sequence? My problem with this, is that what if the HAMPATH graph has more nodes than the sequence? Do I have to take this into account when creating the reduction?

Asked By : user2795095

Answered By : Luke Mathieson

Remember that given the HAMPATH instance, you are constructing the DPATH instance. As long as

  • it's a valid instance of DPATH,
  • it's a Yes-instance if and only if the HAMPATH instance is, and
  • it's computable in polynomial time,

you can do whatever you want. So in particular, you get to pick how long the sequence is, you can pick any $a_{i}$ to be $s$ or $t$ (though in this case you may want to think carefully how you ensure that these are the first and last vertices in the path - otherwise it might be hard to argue for the Hamiltonian path), you don't even have to have the graph $G$ in the HAMPATH instance be the graph $G'$ in the DPATH instance (I suggest that you look at something very close to it though).

In the spoiler below are some additional hints, but don't use them unless you're really stuck - you learn a lot less if you don't put in the effort and time.

One thing you have to do is take the HAMPATH graph and make it directed. There is a very simple way to turn undirected graphs into directed graphs, and it can work here. Another is ensuring that $s$ is the start of the sequence and $t$ is the end. I suggest adding new vertices to be $a_{1}$ and $a_{n}$ such that you can only get out of $a_{1}$ and only get into $a_{n}$, but you still have to work out how to connect them into the graph - remember that you don't know whether $G$ has a Hamiltonian path, or where it is even if it does, so you have to take care of all possibilities.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback