0
$\begingroup$

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll also only consider DAGs for obvious reasons.

Imaginably, this is a hard query to google for. I'm looking for a complexity that is more precise than just "exponential" - is there some nice property of a graph that expresses this? For example, it would be convenient if the complexity would be linear if we the graph is just a tree. Maybe treewidth is helpful?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Suppose the graph has an adjacency matrix $M$. It's well known that the number of paths of length $k$ from $i$ to $j$ is $(M^k)_{ij}$. Since we care about paths of any length, we are interested in $M^0 + M^1 + M^2 + \dots = (I - M)^{-1}$. In particular, the vector $(I - M)^{-1} \bf{1}$ has in its $i$th position the number of paths starting from $i$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's neat but unfortunately not really useful 😅. This seems even harder to put a bound on, and I'm guessing that trees don't obviously satisfy the property I want through this lens. $\endgroup$
    – Adam Jamil
    Commented Jul 21, 2023 at 17:33

Your Answer

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

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