Inductive Tracing and the Complexity of Finding Hamiltonian Path in DAGs
摘要
The \(\textsf{Hamiltonian Path}\) problem is a classic decision problem that is \(\textsf{NP}\) -complete in general graphs, but solvable in linear time and in nondeterministic logspace ( \(\textsf{NL}\) ) for directed acyclic graphs (DAGs). We show that the \(\textsf{Hamiltonian Path}\) problem for DAGs lies in \(\textsf{UL}\cap \textsf{coUL}\) , providing an improved upper bound on its complexity. To the best of our knowledge, this is the first instance where an unambiguous space upper bound has been established for a natural problem without relying on any variant of the classic Reinhardt-Allender double inductive counting technique, which is itself based on the Immerman-Szelepcsényi inductive counting method. Our proof introduces a novel technique, which we call inductive tracing. While reminiscent of inductive counting, it diverges in a key respect: it does not perform any counting across recursive stages. We also apply this routine to obtain a parameterized unambiguous space bound for the \(\textsf{Long Path}\) problem in DAGs.