0
$\begingroup$

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:

enter image description here

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?

$\endgroup$
2
  • $\begingroup$ In order theory there is a concept of width (see en.wikipedia.org/wiki/Antichain) which seems to fit what you are describing in your last paragraph. $\endgroup$ Dec 31, 2014 at 1:58
  • 1
    $\begingroup$ Except in the last paragraph you are describing the minimum vertex-cut between the source and the sink. This is efficiently computed using network flow methods. $\endgroup$ Dec 31, 2014 at 5:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.