Computing Directed Pathwidth in O(1.89n) Time

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in $O(1.{89}^n)$ time. This is the first algorithm with running time better than the straightforward $O^{⁎}(2^n)$ . As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in $O(1.{9657}^n)$ time.