Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time.
Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging the nodes on either side of the edge). What is the optimal way of selecting an optimal set of $k$ edges (whose capacity will be increased to infinity) to maximize the min cut?
Theorem. The problem in the post is NP-hard.
By "the problem in the post", I mean, given a graph $G=(V,E)$ and integer $k$, to choose $k$ edges to raise the capacities of so as to maximize the min cut in the modified graph.
The idea is to reduce from Max Cut. Roughly, a given graph $G=(V,E)$ has max cut size $s$ if and only if you can increase the capacities of $n-2$ edges so that the resulting graph has min cut size $s$. The idea is that $n-2$ edges are just enough to force the resulting graph to have only one finite-capacity cut, and that can be any cut you choose.
This idea doesn't quite work because to get a given cut $(C, V\setminus C)$, you need the subgraphs induced by $C$ and $V\setminus C$ each to be connected. But you can work around this with an appropriate gadget.
Proof. Given a connected graph $G=(V,E)$, define a connected cut to be a cut $(C,V\setminus C)$ such that the subgraphs induced by $C$ and by $V\setminus C$ are each connected. Define Max Connected Cut to be the problem of finding a connected cut (in a given connected graph) maximizing the number of edges crossing the cut.
We show that Max Connected Cut reduces to the problem in the post. Then we show that unweighted Max Cut reduces to Max Connected Cut.
Lemma 1. Max Connected Cut reduces in poly time to the problem defined in the post.
Proof. Given a Max-Connected-Cut instance $G=(V,E)$, let $k=|V|-2$. To prove the lemma, we prove the following:
Claim 1: For any $s>0$, there is a connected cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF it is possible to raise $k$ edge capacities in $G$ to infinity so that the resulting graph has min cut capacity at least $s$.
ONLY IF: Suppose there is a connected cut $(C,V\setminus C)$ of capacity at least $s$. Let $T_1$ and $T_2$ be subtrees spanning, respectively, $C$ and $V\setminus C$, then raise the capacities of edges in $T_1$ and $T_2$. (Note that $|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$.) The only finite-capacity cut remaining in the graph is then $(C, V\setminus C)$, of capacity at least $s$, so the resulting graph has min cut capacity at least $s$.
IF: Suppose it is possible to raise $k$ edge capacities in $G$ so that the resulting graph has min cut capacity at least $s$. Consider the subgraph formed by the $k$ raised edges. Without loss of generality, assume this subgraph is acyclic. (Otherwise, "unraise" one edge from a cycle of raised edges and instead raise some unraised edge that joins two connected components from the subgraph. This only increases the min cut in the resulting graph.) By the choice of $k=n-2$, the subgraph of raised edges has two connected components, say $C$ and $V\setminus C$, so the only finite-capacity cut in the resulting graph is $(C,V\setminus C)$. And this cut has capacity at least $s$, as it did in the original graph.
This proves the claim (and the lemma). (QED)
For completeness, we show that Max Connected Cut is NP-complete, by reduction from unweighted Max Cut.
Lemma 2. Unweighted Max Cut reduces in poly time to Max Connected Cut.
Proof. For any integer $N\ge 1$, define graph $P(N)$ to consist of two paths $A$ and $B$, each of length $N$, with edges from each vertex in $A$ to each vertex in $B$. We leave it as an exercise to the reader to verify that the max cut in $P(N)$ ($A$ on one side, $B$ on the other) has size $N^2$, and no other cut has size larger than, say, $N^2-N/100$.
Here is the reduction. Given any unweighted Max Cut instance $G=(V,E)$, construct a graph $G'=(V',E')$ as follows. Let $n=|V|$. Let $N = 100(n^2 + 2n)$. Add to $G$ the graph $P(N)$ defined above (with its two paths $A$ and $B$). From each vertex $v\in V$ add an edge to one vertex in $A$ and another edge to one vertex in $B$. This defines the reduction. To finish, we prove it is correct:
Claim 2: For any $s\ge 0$, there is a cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF there is a connected cut in $G'$ of size at least $s+N^2+n$.
ONLY IF: Given any cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, consider the connected cut $(A\cup C, B\cup V\setminus C)$ in $G'$. This connected cut in $G'$ cuts at least $s$ edges from $C$ to $V\setminus C$, plus $N^2$ edges from $A$ to $B$, plus $n$ of the $2n$ edges from $V$ to $A\cup B$.
IF: Suppose there is a connected cut in $G'$ of size at least $s+N^2+n$. $A$ and $B$ are on opposite sides of the cut. (Otherwise, since the second largest cut in $P(N)$ cuts at most $N^2-N/100$ edges in $P(N)$, the total number of edges cut is at most $N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$.) Let $C$ denote the vertices in $V$ on the side of the cut with $A$. Then there are $N^2$ edges in the cut from $A$ to $B$, and $n$ from $V$ to $A\cup B$, so there must be at least $s$ from $C$ to $V\setminus C$.
This proves the claim and Lemma 2. (QED)
By Lemmas 1 and 2, since unweighted Max Cut is NP-hard, the problem in the post is also NP-hard.
