# DAG Hamiltonian Path NP-complete

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 ?

• Is it clear that splitting one vertex makes the graph acyclic? Which vertex do you pick? – user53923 Feb 2 '18 at 9:28
• 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. – Neel Basu Feb 2 '18 at 9:42
• 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?) – user53923 Feb 2 '18 at 10:17
• 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. – Neel Basu Feb 2 '18 at 11:17
• Your reduction just doesn't work. You can use topological ordering to solve the Hamiltonian path problem on a DAG in polynomial time. – Yuval Filmus Feb 2 '18 at 15:46