6
$\begingroup$

I am trying to find a graph in which both s-t minpaths and min cuts are exponential.

Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an example of graph which has both min paths and min cuts in exponential size.

$\endgroup$
  • $\begingroup$ You have two graphs $G_1$ and $G_2$ each with vertices $s_1,t_1$ and $s_2,t_2$. What happens if you make an edge from $t_1$ to $s_2$ and let $s = s_1$ and $t = t_2$? $\endgroup$ – Pål GD May 17 '14 at 20:49
11
$\begingroup$

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts.

An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the weights so that there have to be enough "inner" nodes in either partition.

Idea: Use a complete layer graph with $\sqrt{n}$ layers and $\sqrt{n}$ nodes in each layer. Add $s$ and $t$ and wire with the first resp. last layer; make the weights on these edges so large that the first layer has to be in the partition of $s$ (and the last in that of $t$) for every minimum cut.

The graphs look like this (unit weights on all unlabelled edges):

enter image description here
[source]

Now we can count.

  • The graph has $n + 2$ nodes and $(n+2)\sqrt{n} - n \in \Theta(n^{\frac{3}{2}})$ edges.
  • Every shortest s-t-path picks one node in every layer; hence, we get $\sqrt{n}^{\sqrt{n}}$ such paths.
  • No edge $(s,\_)$ or $(\_,t)$ is ever part of a minimum cut (each such edge has more weight than all others together). Convince yourself that all cuts constructed by fixing a column (but the first and the last), putting every node either left or right and using this as the "cut line", are minimal with weight $n$. We obtain $(\sqrt{n}-2) \cdot 2^{\sqrt{n}}$ many such cuts.

At least with layer graphs, I think the two quantities can not be exponential at the same time; one needs non-constant depth, the other linear width. I'm not sure if a similar argument carries over to general graphs.

$\endgroup$
7
$\begingroup$

Take any graph $G$ on $n$ vertices which has $2^{\Omega(n)}$ minimal $s$-$t$ paths. Add to $G$ an independent set of size $n$. Now it has at least $2^n$ minimum cuts.

$\endgroup$
  • 1
    $\begingroup$ Oh, right, deadends. Didn't think of those. *facepalm* $\endgroup$ – Raphael Dec 6 '14 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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