0
$\begingroup$

The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG. But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two vertices ${s,t}$ which will make the graph acyclic and then ask for $s\rightarrow t$ hamiltonian path in that DAG. These two problems are equivalent. Then why is one NP-complete and other is not ?

$\endgroup$
  • 2
    $\begingroup$ Is it clear that splitting one vertex makes the graph acyclic? Which vertex do you pick? $\endgroup$ – user53923 Feb 2 '18 at 9:28
  • $\begingroup$ If there exists at least one vertex by splitting which we can make the digraph acyclic. Then there exists an equivalent $s\rightarrow t$ hamiltonian path problem on DAG. Which is supposed to be NP-complete too. $\endgroup$ – Neel Basu Feb 2 '18 at 9:42
  • 2
    $\begingroup$ That proves that if there exists such a vertex in a digraph, indeed deciding HC in this graph is easy (in the way you propose). However, if a graph has "many" cycles, you will not find such a vertex I think (after splitting a single vertex, the graph will still have cycles, thus not be a DAG). (and splitting multiple vertices would cause problems, no?) $\endgroup$ – user53923 Feb 2 '18 at 10:17
  • $\begingroup$ I haven't thought about many cycles case. But then I have to split those vertices in such a way that breaks the cycle. So the splitted vertices will be terminal vertices I think. If that is doable in P time then we again get $s\rightarrow t$ Hamiltonian Path problem with more than two terminal vertices. $\endgroup$ – Neel Basu Feb 2 '18 at 11:17
  • $\begingroup$ Your reduction just doesn't work. You can use topological ordering to solve the Hamiltonian path problem on a DAG in polynomial time. $\endgroup$ – Yuval Filmus Feb 2 '18 at 15:46
1
$\begingroup$

Your proposed approach doesn't work. For some directed graphs there is no single vertex you can split to turn it into a DAG. An algorithm only qualifies as a solution to the Hamiltonian Cycle problem if it solves the problem for all graphs. It's not enough to solve the problem for a subset of "easy" graphs.

$\endgroup$

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.