8
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ It may be worth checking the recursive diamond graph to see if it is a counter example. cstheory.stackexchange.com/questions/10169/… $\endgroup$
    – Chandra Chekuri
    Apr 4, 2014 at 3:05
  • $\begingroup$ 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. $\endgroup$
    – Raghav Kulkarni
    Apr 4, 2014 at 4:18
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Apr 4, 2014 at 9:34
  • $\begingroup$ A counter-example is posted on MathOverflow: mathoverflow.net/questions/161451/… I still feel that the "right" modification of the question may hold true, at least for some natural graph classes such as planar graphs. $\endgroup$
    – Raghav Kulkarni
    Apr 8, 2014 at 17:15
  • $\begingroup$ One variation possibly is this : every $k$-linked graph contains a $k$-chain, but this is a very obvious variation. $\endgroup$
    – Saeed
    Apr 11, 2014 at 10:15

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Raghav Kulkarni
    Apr 3, 2014 at 20:20
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Apr 3, 2014 at 20:36
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Apr 3, 2014 at 20:41
1
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.