Linear time algorithm for finding $k$ shortest paths in unweighted graphs Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, 
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths 
  between $s$ and $t$ in $G$.


Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$. 

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?
No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers