1
$\begingroup$

Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .

Is there a reference or name for the algorithm? If not, are there well known applications?

$\endgroup$
  • 1
    $\begingroup$ I don't know the algorithm, but these books have relevant material, I believe: Kemeny and Snell, Finite Markov Chains (chapter 1); Flajolet and Sedgewick, Analytical Combinatorics. $\endgroup$ – Mars Jul 25 '20 at 15:50
  • $\begingroup$ @Mars Could you say more about those references please? Do they refer specifically to this problem and if so, in which context? $\endgroup$ – fomin Jul 25 '20 at 18:50
  • $\begingroup$ The first reference contains a methods for counting paths in DAGs. I'm pretty sure that the second will, too. I don't know whether they are what you want. $\endgroup$ – Mars Jul 25 '20 at 23:28
1
$\begingroup$

This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details.

It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs by extending the value set to $\mathbb{N} \cup \infty$ and adding a suitable $a^*$ operator.

$\endgroup$
  • $\begingroup$ Could you say more about the semiring problem? I couldn't see which part of the attached paper you were referring to (it doesn't seem to have anything with that name). $\endgroup$ – fomin Jul 25 '20 at 18:47
  • $\begingroup$ @fomin Did you read and understand section 4 of the paper? (That paper might not use the exact phrase "semiring problem", that's just the paper I reach for reflexively whenever I want to link someone to info about graph semiring algorithms.) $\endgroup$ – Aaron Rotenberg Jul 25 '20 at 18:55
  • 1
    $\begingroup$ @fomin Here is another reference on semiring graph problems. Semiring algorithms generalize the idea of using dynamic progamming to efficiently compute some notion of sum over all paths in a graph. $\endgroup$ – Aaron Rotenberg Jul 25 '20 at 19:00
  • $\begingroup$ Could you add some mathematical detail to your answer? In particular, why the counting problem OP is interested in is equivalent to a semiring problem from PL. $\endgroup$ – Anush Jul 26 '20 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.