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 ?
6
-
2$\begingroup$ Is it clear that splitting one vertex makes the graph acyclic? Which vertex do you pick? $\endgroup$– user53923Commented Feb 2, 2018 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 BasuCommented Feb 2, 2018 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$– user53923Commented Feb 2, 2018 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 BasuCommented Feb 2, 2018 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 FilmusCommented Feb 2, 2018 at 15:46
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
