How to calculate maximal parallelism in a DAG?

Question

Given a DAG (directed acyclic graph), how does one calculate the maximal parallelism?

Instantaneous parallelism is the maximum number of processors that can be kept busy at each point in execution of algorithm; the maximal parallelism is the highest instantaneous parallelism.

Put another way, given a DAG representing a dependency graph of tasks, what is the minimum number of processors/threads such that no task is ever blocked?

The closest approach I found here is:

• apply a topological sort on the DAG
• traverse over the nodes by the topological order, calculate the minimum level:
  • no parents: 0
  • otherwise: minimum parent level + 1
• return the max level width (max num of nodes assigned the same level)

This algorithm worked for me on several samples, however doesn't work on a tree. E.g.:

  o 0
 / \
o 1 o 1
   / \
  o 2 o 2
     / \
    o 3 o 3

According to the algorithm above, max width is 2, but clearly max parallelism in a tree is the number of leafs, 4 in the example above.

A similar approach is partially described here (see slide titled Computing critical path etc., which describes how to calculate earliest start times of nodes and that "maximal...parallelism can easily be computed from this").

---

Edit 1:

@AliSoltani's solution to use BFS to find the length of the critical path and that is the max parallelism degree is incorrect, since it only applies to a subset of examples, mainly trees in which the number of leafs is equal to the longest path. Here's an illustration of a case where this wouldn't work:

---

Edit 2:

@AliSultani's 2nd solution using BFS to find the level with maximum number of nodes, and set that max as the max parallelism, is also incorrect, as it doesn't take into account cases where nodes from different levels may run concurrently. See this counterexample:

Answer 1

This problem is reducible to the Maximum Directed Cut problem.

Let's build an auxiliary DAG from the original one.

1. For every vertex u[i] of the original graph add vertexes v[i] and w[i] to the new graph, and connect them using an edge (v[i], w[i]) with a cost 1.
2. For every edge (u[i], u[j]) of the original graph add an edge (w[i], v[j]) with a cost 0 to the new graph.
3. Now the problem is equivalent to finding the maximum directed cut in the auxiliary graph.

Example: