Computer Science Colloquium
Date: Thursday, 24 April 2025
Time: 12:00 PM
Venue: Seminar Hall
Complexity of Finding Hamiltonian Path in DAGs
Ronak Bhadra
IIT Kanpur.
24-04-25

---

Abstract

A path in a graph that visits each vertex in it exactly once is called a Hamiltonian Path. The problem of deciding whether a graph has a Hamiltonian path or not is known to be NP-complete for general graphs. However, for Directed Acyclic Graphs (DAGs), it is known to be solvable in linear time as well as in nondeterministic logspace (NL).

A problem is said to be in the complexity class UL if there is a non-deterministic logspace Turing Machine that accepts a positive (yes) instance of the problem along exactly one computation path and rejects a negative (no) instance of the problem along all computation paths. The class UL, as can be inferred from the definition, is contained in NL. The complexity class consisting of the complements of the problems in UL is called coUL. Since NL=coNL (Immerman-Szelepcsenyi Theorem), coUL is also contained in NL. It is not difficult to see that the problem of finding Hamiltonian Path in DAGs is in UL. However, since it is not known yet whether UL=coUL, it is not apparent that the problem also lies in the complexity class coUL. In this talk, we will discuss our result where we show that the problem of finding Hamiltonian Path for Directed Acyclic Graphs (DAGs) is in the complexity class coUL.

(Joint work with Raghunath Tewari (IITK))