4
$\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?

I would be equally happy with $\Omega(\sqrt k)$-chain or $\Omega(k^\alpha)$ for any $\alpha > 0.$

This question is closely related to another one that I asked few days ago: Do graphs with large number of cycles always contain large necklace minor?

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

$\endgroup$
5
$\begingroup$

No, there is no such bound.

Consider the graph $G_n$ whose vertices are pairs $(k,\nu) \in \{1, 2, \dots, n\} \times \{0, 1\}$, with edges between $(k, \nu)$ and $(k+1, \mu)$ for every $k \in \{0, 1, \dots, n-1\}$ and every $\nu, \mu \in \{0, 1\}$. Take $s = (n, 0)$ and $t = (n, 1)$. Then $\left|G_n\right|$ grows linearly in $n$, and the number of paths from $s$ to $t$ grows exponentially in $n$. However, $G_n$ has no 3-chain minors from $s$ to $t$.

We prove this by induction on $n$. Consider a $k$-chain minor of $G_n$ from $s$ to $t$. Let $H$ be the subgraph of $G$ obtained after all edge deletions, but before any contractions. If both $s$ and $t$ have degree 1 in $H$, then by the induction hypothesis $k \leq 2$. Otherwise, one of them has degree $2$, so there is a path of length $2$ in $H$ from $s$ to $t$, which means $k \leq 2$.

You can think of this as iterating the following construction. Given a graph with a specified source and sink, construct a new graph by adding two new vertices, the new source and the new sink, and four new edges, connecting the new source and sink to the old. Each iteration at least doubles the number of paths from source to sink, but adds no new $k$-chain minors for $k \geq 3$.

The idea behind the conjecture is that if a graph has many paths from $s$ to $t$, then it's because the graph can be cut into two independent parts, one with many paths from $s$ to some point $c$ and one with many paths from $c$ to $t$. As the above construction shows, though, even if all the paths pass through some point $c$, there may not be a consistent way to pick an "$s$-side" and a "$t$-side."

$\endgroup$
  • $\begingroup$ Thanks! Your graph (I don't know how to name it; may be `$k$-crosschain'?) does seem to give a counter-example to the $k$-chain conjecture. This is very helpful. I suspect whether the conjecture can be modified by replacing "$k$-chain" with "either $k$-chain or $k$-crosschain". I will probably post it as a new question. $\endgroup$ – Raghav Kulkarni Apr 8 '14 at 10:27
  • $\begingroup$ Doesn't contracting every edge from $(k,0)$ to $(k+1,1)$ produce a long chain minor? It has a doubled edge to the next such vertex, coming from the two edges $(k,0)-(k+1,0)$ and $(k+1,1)-(k+2,1)$. $\endgroup$ – David Eppstein Apr 8 '14 at 17:23
  • $\begingroup$ I think you are right that there is still a long chain minor. But there is no long "s-t chain minor", which is what I meant in the question. Hope this brings a bit more clarification. $\endgroup$ – Raghav Kulkarni Apr 8 '14 at 17:52
  • $\begingroup$ @DavidEppstein: Thanks, I edited the post to say what I actually meant. $\endgroup$ – Anton Malyshev Apr 8 '14 at 21:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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