# Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph?

I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. I want a method to effectively parallelize these tasks. One way would be to topological sort them based on depth. Node a which has no precedents will have depth 0. For other nodes, depth will be the depth of precedent with the highest depth +1. Like in the answer provided in this stack exchange question. But here I am not sure if we can get the most amount of parallelization. Tasks in each depth can be run in parallel. But to start processing tasks in a particular depth. All tasks in previous depth should be completed.

Then I came across the idea of transitive reduction of a DAG. Transitive reduction reduces extra edges such that the same reach-ability relation in the original graph is maintained. Does this mean that transitive reduction is implicitly topological sorted? Does doing bfs over a transitively reduced task graph and executing tasks as they come in the bfs order equivalent to topological order?. For the input graph and its transitive reduced version, they seem equivalent. I don't know if there are any cases I am missing. What I want is a way to parallelize a task graph with maximum throughput.

• I do not know whether I fully understand what you are asking for. So, let me start with a simple graph. It has only two paths from top node $a$ to bottom node $b$: path $a-c-d-e-b$ and $a-f-b$. Then with BFS node $b$ will be found before node $e$, and that is not what one wants in a topsort. So, I do not think that BFS is suitable to find a topsort, even as in this case where the graph is a Hasse diagram. Jul 25 at 22:06