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

CC BY-SA 4.0
2023-07-21T17:33:16.607Z
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.
Adam Jamil
CC BY-SA 4.0
2023-07-21T03:45:32.677Z
2023-07-21T03:45:32.677Z
Command Master
<p>By &quot;revisit nodes,&quot; 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.</p>
<p>Imaginably, this is a hard query to google for. I'm looking for a complexity that is more precise than just &quot;exponential&quot; - 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?</p>

<graph-theory><graph-algorithms><directed-acyclic-graph><complexity>
What's the exact complexity of a DFS if we revisit nodes?
Adam Jamil
# What's the exact complexity of a DFS if we revisit nodes?

(Asked by: username_0 on 2023-07-20)

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?

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph, complexity


---

## 1 answers

### Answer by username_1 on 2023-07-21. Score: 1

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$.

> **Comments:**
> **username_0**: 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.  

---

