<p>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 <a href="http://arxiv.org/abs/1305.6577" rel="nofollow">Chekuri et al.</a> 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>

<p>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. </p>

CC BY-SA 3.0
2014-04-03T20:20:45.823Z
So you are saying that the "largest chain obtainable by deletion-contraction" seems to be fixed parameter tractable. That is interesting! Although, this does not tell anything about existence of a large chain as a consequence of having large number of paths.
Raghav Kulkarni
CC BY-SA 3.0
2014-04-03T20:36:01.657Z
@RaghavKulkarni, Yes, I think so, I'm not pretty sure though, just depends to that if is possible to formulate problem as MSO_2 or providing dynamic programming approach for bounded tree width case, actually your problem seems is in bidimentional problems category.
Saeed
CC BY-SA 3.0
2014-04-03T20:41:47.313Z
Also we don't need a very big grid like $K\times K$ because we are just looking for small case, just $2^k$ path, so it's possible to improve the running time (I think much more better, and even may be in $P$, I mean if something like poly log k works then it's very nice or in subexponential FPT algorithm).
Saeed
CC BY-SA 3.0
2014-04-03T19:40:06.933Z
2014-04-03T19:45:19.480Z
2014-04-03T19:45:19.480Z
Saeed
<p>counter-examples to above are posted on MathOverflow:</p>

<p><a href="https://mathoverflow.net/questions/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor">https://mathoverflow.net/questions/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor</a></p>

<p><a href="https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1">https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1</a></p>

<p>Any "right" modification of question that still holds true?</p>

CC BY-SA 3.0
2014-04-11T06:33:56.980Z
2014-04-11T06:33:56.980Z
2017-04-13T12:57:54.777Z
Raghav Kulkarni
<p>Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.</p>

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

<p>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?</p>

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

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

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

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

<p><a href="https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor">https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor</a></p>

CC BY-SA 3.0
2014-04-04T03:05:51.073Z
It may be worth checking the recursive diamond graph to see if it is a counter example. http://cstheory.stackexchange.com/questions/10169/from-edge-disjoint-paths-to-independent-paths
Chandra Chekuri
CC BY-SA 3.0
2014-04-04T04:18:22.953Z
That is an interesting graph. Although, it seems to me that this may not be counter-example for the "$k^\alpha$-chain Conjecture". However, may be for the "$\Omega(k)$-chain Conjecture" this might. Not sure yet.
Raghav Kulkarni
CC BY-SA 3.0
2014-04-04T09:34:39.557Z
It's not a counter example even for $\Omega(k)$, because if it's a counter example for $\Omega(k)$ then the degree of $s$ is at most $O(k)$, and the length of longest $s,t$ path is $O(k)$, then there is no $n^k$ s-t paths, except that we suppose $n=f(k)$, the latter case, again is impossible (actually n is f(k) in that graphs, but it does not lead to contradiction to theorem, because then $f$ is exponential function).
Saeed
CC BY-SA 3.0
2014-04-08T17:15:09.070Z
A counter-example is posted on MathOverflow: http://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor/162668#162668 I still feel that the "right" modification of the question may hold true, at least for some natural graph classes such as planar graphs.
Raghav Kulkarni
CC BY-SA 3.0
2014-04-11T10:15:03.970Z
One variation possibly is this : every $k$-linked graph contains a $k$-chain, but this is a very obvious variation.
Saeed
<graph-theory><graph-algorithms><graph-minor>
Do graphs with large number of paths contain large chain minor?
Raghav Kulkarni
# Do graphs with large number of paths contain large chain minor?

(Asked by: username_0 on 2014-04-03)

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 >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>

**Tags:** graph-theory, graph-algorithms, graph-minor
> **Comments:**
> **username_1**: It may be worth checking the recursive diamond graph to see if it is a counter example. http://cstheory.stackexchange.com/questions/10169/from-edge-disjoint-paths-to-independent-paths  
> **username_0**: That is an interesting graph. Although, it seems to me that this may not be counter-example for the "$k^\alpha$-chain Conjecture". However, may be for the "$\Omega(k)$-chain Conjecture" this might. Not sure yet.  
> **username_2**: It's not a counter example even for $\Omega(k)$, because if it's a counter example for $\Omega(k)$ then the degree of $s$ is at most $O(k)$, and the length of longest $s,t$ path is $O(k)$, then there is no $n^k$ s-t paths, except that we suppose $n=f(k)$, the latter case, again is impossible (actually n is f(k) in that graphs, but it does not lead to contradiction to theorem, because then $f$ is exponential function).  
> **username_0**: A counter-example is posted on MathOverflow: http://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor/162668#162668 I still feel that the "right" modification of the question may hold true, at least for some natural graph classes such as planar graphs.  
> **username_2**: One variation possibly is this : every $k$-linked graph contains a $k$-chain, but this is a very obvious variation.  

---

## 2 answers

### Answer by username_2 on 2014-04-03. Score: 2 | Accepted answer

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.](http://arxiv.org/abs/1305.6577) shown, the graph has tree width at most $O(k^{1/\delta})$ where $\delta > 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.

> **Comments:**
> **username_0**: So you are saying that the "largest chain obtainable by deletion-contraction" seems to be fixed parameter tractable. That is interesting! Although, this does not tell anything about existence of a large chain as a consequence of having large number of paths.  
> **username_2**: @RaghavKulkarni, Yes, I think so, I'm not pretty sure though, just depends to that if is possible to formulate problem as MSO_2 or providing dynamic programming approach for bounded tree width case, actually your problem seems is in bidimentional problems category.  
> **username_2**: Also we don't need a very big grid like $K\times K$ because we are just looking for small case, just $2^k$ path, so it's possible to improve the running time (I think much more better, and even may be in $P$, I mean if something like poly log k works then it's very nice or in subexponential FPT algorithm).  

---

### Answer by username_0 on 2014-04-11. Score: 1

counter-examples to above are posted on MathOverflow:

<https://mathoverflow.net/questions/161006/do-graphs-with-large-number-of-cycles-always-contain-large-necklace-minor>

<https://mathoverflow.net/questions/161451/do-graphs-with-large-number-of-paths-contain-large-chain-minor?lq=1>

Any "right" modification of question that still holds true?


---

