Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y has to pass. Such node can be found e.g. by assigning a weight to each edge in such a way that G becomes a flow network. Then a node is bottleneck iff its input (and output) flow is equal to input flow of X.
I originally wanted to extend the notion of bottleneck to more nodes, i.e. what's the minimal number of nodes (except source and sink of course) such that each path from source to sink passes through at least one of them? Such a number I call the "parallelism degree of G". Let me further illustrate the problem on following graph:
According to above definition parallelism degree of this graph is 2 (e.g. nodes C and G). The first question is whether there is efficient (polynomial?) algorithm for computing parallelism degree. I pretty much suspect that this must be some well described problem but I wasn't able to find anything related (perhaps word "parallel" is inappropriate here).
Related question is whether my definition is "correct". Suppose there is no edge from C to D. Then suddenly the parallelism degree becomes just 1 which is probably not what one "wants". Could you think of more useful definition, i.e. something like maximum of parallelism degrees of subgraphs between each consecutive pair of bottlenecks (which would yield 3 in this case)? Or perhaps something even more general?