1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much for the help :) I hadn't even taken into consideration that a hamiltonian path wasn't directed. But am I right that this problem is NP complete? It's also similar to PATH, which is in P, so now I'm a bit unsure that it even is NP complete... $\endgroup$ – user2795095 May 26 '14 at 11:23
  • 1
    $\begingroup$ @user2795095 No problem :). It is indeed NP-complete, it's much like the LONGEST PATH problem, which is NP-complete (short paths are easy to find, long paths aren't). $\endgroup$ – Luke Mathieson May 26 '14 at 11:27
  • $\begingroup$ Great, that's good to know :)! Can I ask one last question before I continue trying to find the reduction? Do you agree that HAMPATH is the best problem to reduce from? If no, I will try to see if there are any other languages that are more suited. $\endgroup$ – user2795095 May 26 '14 at 12:35
  • $\begingroup$ I guess it could also be possible to reduce 3-CNF-SAT to DPATH, but I'm not sure if this is more cumbersome... $\endgroup$ – user2795095 May 26 '14 at 12:50
  • $\begingroup$ HAMPATH is pretty good source problem. There is a very easy reduction, almost certainly easier than from 3-SAT. $\endgroup$ – Luke Mathieson May 26 '14 at 13:09

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.