Symbolic topological sorting with OBDDs

We present a symbolic OBDD algorithm for topological sorting which requires O(log²|V|) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log⁴|V|loglog|V|). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs.