Do graphs with large number of paths contain large chain minor? Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.

Note that the number of paths between two endpoints of a $k$-chain is $2^k.$

Question: Let $G$ be a simple graph on n nodes and let $s$ and $t$ be two nodes of $G.$ Suppose that number of (simple) paths from s to t in $G$ is at least $n^k.$ Then, is it possible to obtain a $\Omega(k)$-chain from $G$ with ($s$ and $t$ as endpoints) by a sequence of deletion and contraction of edges?

If the answer is positive then the second part of question is whether there is an efficient algorithm to obtain such a large chain.

I would be equally happy with $\sqrt k$-chain or $k^\alpha$ for any $\alpha &gt;0.$

I would appreciate any partial answer or any intuition on whether such a conjecture should hold.

I had posted this on math overflow few days back. Someone suggested to post it here as well.

https://mathoverflow.net/questions/161451/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.