Jtdylktuy

I have seen from a few sources (such as the CS Stack Exchange) that the problem of determining all the paths between two vertices $u$ and $v$ is NP hard. However, foR something that I am developing, I need to find only the number of paths of a given length whose first vertice is $v$. Is there an algorithm that can find this in Polynomial time ?

P.S. This is the first time I am posting on Stackexchange, so I apologize in case my question is too "rough" .

If you only need the number of walks of a given length, you can do it in polynomial time (with respect to the number of vertices of the graph) using the incidence (or adjacency) matrix of the graph.

Indeed, assume $G= (V,E)$ is the graph in question, where $|V| = n$ and $A$ is the incidence matrix of $G$, i.e. $A$ is an $ntimes n$ matrix of ${0,1}$-s where $(i,j)$-th element is $1$ iff there is an edge from vertex $i$ to vertex $j$.

Fix an integer $k geq 1$, which is the length of the walk. It is a well-known fact that the $(i,j)$-th entry of the matrix $A^k$ shows the number of walks from $i$ to $j$ having length $k$ (the proof follows by a straightforward induction on $k$ and the definition of a matrix product, see wikipedia for instance).

Getting back to your original question: $A^k$ can be computed in $O(n^3 + nlog k)$ time using singular value decomposition (SVD). Here $n^3$ is the time to complete the SVD and $n log k$ is the time to raise all elements on the diagonal matrix of the SVD into power $k$. See here for further discussion.
Once you have $A^k$, then summing over all elements of the $v$-th row ($v$ was the vertex where you start the walk of length $k$) gives the number of walks from $v$ having length $k$.

For the number of paths (instead of walks), see the other answer.

No, there is no such algorithm, unless P=NP. More precisely: If determining the number of path between two vertices $u$ and $v$ is NP-Hard, then so is calculating the number of paths starting at any vertex $v$.

Indeed, let $G$ be a graph, and $u$ and $v$ any two vertices in $G$. Then write as $n_G(v)$ the number of paths starting at $v$ and write as $n_G(v,u)$ the number of paths starting at $v$ and ending at $u$. Next, let $G'$ be the graph formed from $G$ by adding an extra vertex $z$ and attaching that extra vertex to precisely $u$. Then
$n_G(v)+ n_G(v,u) = n_{G'}(v)$. If we can calculate $n_G(v)$ and $n_{G'}(v)$ in polynomial time then we can calculate $n_{G}(v,u)$ in polynomial time.

And if we can calculate the number $^kn_G(v)$ of paths of length $k$ starting at $v$ then we can certainly calculate $n_G(v)$; indeed take the sum $sum_k$
$^kn_G(v)$ to get $n_G(v)$.

[Computing the total number of walks of a given length $k$ between two vertices is easy to do in polynomial time however; the above answer shows how to do this.]