Do graphs with large number of paths contain large chain minor?
Seems this is a FPT algorithm for a fixed $k$. First of all we can just consider a block which contains $s,t$. If we have a $k\times k$ grid minor which contains $s,t$ then we can find the corresponding chain. As otherwise, as Chekuri et al. shown, the graph has tree width at most $O(k^{1/\delta})$ where $\delta &gt; 0$ is some constant. So we can compute the tree decomposition of graph then check whether that chain exists or not. I'm not sure if with usual dynamic programming on graphs of bounded tree width is possible to find the chain. Also if is not bounded tree width, their algorithm can find the corresponding grid in polynomial time.

P.S: Note that I didn't use the fact that there are $n^k$ s-t paths, may be by some trick inside this fact is possible to obtain better algorithm.