Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

Question

Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.

$$ \text{#(paths from 1 to 2)}+\text{#(paths from 1 to 3)}+\cdots+\text{#(paths from 1 to $n$)}. $$

We have to find this in linear time, as number of vertexes can be as large as 100000. I tried using DFS in this question to generate all the paths and keeping up count of these but this is not fast enough.

Is there any mathematical formula for this?

P.S. I am only interested in total number of paths, not generating all the paths. Each vertex has up to 4 or 5 edges.

For example, if the adjacency matrix of a 4 nodes graph is like this:

  A B C D
A 0 1 0 0    
B 1 0 1 1    
C 0 1 0 1   
D 0 0 1 0

Then the number of paths are

from A to B: 1    
from A to C: 2      
from A to D: 2     
therefore 5 paths 

So I want the answer to be 5.

The edges may be unidirectional or bidirectional and I want to find only simple paths.

Answer 1

Suppose you have a polynomial-time algorithm $\mathcal{A}$ to solve this problem, then consider a graph $G$ and arbitrary two vertices $s$ and $t$. We construct a new graph $G'$ by add a new vertex $t'$ into $G$, as well as an edge $(t,t')$. Now we have

\begin{align} \text{#(paths from $s$ to $t$ in $G$)} =&\ \text{#(paths from $s$ to all other vertices in $G'$)}\\ &-\text{#(paths from $s$ to all other vertices in $G$)}. \end{align}

That means, we can use $\mathcal{A}$ to count the number of paths between two vertices in polynomial time. However, the latter problem is #P-hard. So such an algorithm $\mathcal{A}$ does not exist unless $\mathbf{P}=\mathbf{NP}$.