Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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|}$.
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.
