Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts?

Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which has the minimum cost over ALL cuts of G, and which also satisfies the additional requirement that $s \in S$ and $t \in T$. A minimum $(s, t)$-cut does not neccessary have to be a global minimum cut.

  • $\begingroup$ Is a minimum $(s,t)$-cuts a global minimum cut which is also a $(s,t)$-cut, or a $(s,t)$-cut that has minimum cost among all $(s,t)$-cuts? If it is the latter, then my answer is incorrect and you should look at @InuyashaYagami's answer. $\endgroup$ – Nathaniel May 17 at 18:08
  • $\begingroup$ @Nathaniel as the term is defined in the script of my uni. A $(s, t)-$cut has a minimum cost over ALL cuts of $G$. So I think a $(s, t)$-cut also has to be a global minimum cut. $\endgroup$ – Long Nguyen May 17 at 18:14
  • $\begingroup$ In that case, I should delete my answer. Sophie you should edit your question in that case. Thanks for the clarification. :). You shoud simply say global min cut instead of s,t min cut. $\endgroup$ – Inuyasha Yagami May 17 at 18:21
  • 1
    $\begingroup$ @InuyashaYagami I suggest you don't delete your answer, as it is an interesting answer for another definition, and it could maybe help someone who reaches this question with similar keywords but uses the other definition. $\endgroup$ – Nathaniel May 17 at 18:25
  • 1
    $\begingroup$ @InuyashaYagami I share Nathaniel's opinion $\endgroup$ – Long Nguyen May 17 at 18:26

If we fix the vertices $s$ and $t$ in the graph, then we can have an exponential number of $(s,t)$ min-cuts.

Following is an example of a graph that contains an exponential number of $(s,t)$-min cuts.

Let the vertex set be $V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$. Let the edges set contains the edges $(s,u_{i})$, $(u_{i},v_{i})$, and $(v_{i},t)$ for each $i \in \{1,\dotsc,n\}$. Therefore, there are total $3 n$ edges. Each edge has capacity $1$.

Let $C = (S,T)$ be a cut such that $s \in S$ and $t \in T$. Consider the vertices $u_{i}$ and $v_i$. There are four possibilities:

  1. $u_i \in S$ and $v_i \in T$. Then edge $(u_i,v_i)$ is in the cut.
  2. $u_i \in T$ and $v_i \in S$. Then edge $(u_i,v_i)$ is in the cut.
  3. $u_i \in S$ and $v_i \in S$. Then edge $(v_i,t)$ is in the cut.
  4. $u_i \in T$ and $v_i \in T$. Then edge $(s,u_i)$ is in the cut.

For every pair of $u_i$ and $v_i$ at least one edge adds to the cut. Therefore, minimum cut cost is at least $n$.

To find all the cuts of size exactly $n$, add all the vertices: $u_1,\dotsc,u_n$ to $S$. It is optional to include a vertex $v_{i}$ in the set $S$. The remaining vertices, i.e., $V \setminus S$ belongs to $T$. Any such cut has a capacity $n$. Therefore, it is a min-cut. Since there are $2^n$ choices of including $v_{i}$'s, the total number of min-cuts are $2^n \in 2^{\Theta(|V|)}$. Hence, we get an exponential number of min-cuts.

Note: This is an asymptotically tight bound since the possible number of $(S,T)$ cuts are at most $2^{|V|}$.

  • $\begingroup$ That seems ok to count the number of $(s,t)$-cuts reaching the minimum cost among all $(s,t)$-cuts. $\endgroup$ – Nathaniel May 17 at 18:04

A graph of order $n$ has at most $\frac{n(n-1)}{2}$ minimum cuts. Since a minimum $(s,t)$-cut is also a minimum cut, that answer your question.

  • $\begingroup$ Is there a proof for the claim $\cfrac{n(n - 1)}{2}$ is the upper bound of minimum cuts? I followed your link but could not find any proof $\endgroup$ – Long Nguyen May 17 at 17:03
  • $\begingroup$ Okay I think I can construct the proof myself. Thanks. $\endgroup$ – Long Nguyen May 17 at 17:06
  • $\begingroup$ The upper bound can be proved with Karger's algorithm. A $n$-cycle have exactly this number of minimum cuts. $\endgroup$ – Nathaniel May 17 at 17:08
  • $\begingroup$ @Nathaniel Can you please check my answer? Can you please check where it is incorrect? Thanks! $\endgroup$ – Inuyasha Yagami May 17 at 17:48
  • 1
    $\begingroup$ @InuyashaYagami I am still not sure what OP wanted to ask… $\endgroup$ – Nathaniel May 17 at 18:04

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.