Minimum cost cut with discount - what is the complexity? Consider an undirected graph $G=(V,E)$ with non-negative edge costs. Given an integer $k$ with $0\leq k\leq |E|$, let us call an edge set $C\subseteq E$ a $k$-discounted cut, if the following hold:


$C$ is a cut in the usual sense.
The cost of the $k$ most expensive edges in $C$ is changed to 0. (If $k\geq |C|$, then all edge costs in $C$ are changed to 0.) This cost reduction is the "discount." The cost of the $k$-discounted cut is the sum of the edge costs in $C$, after the cost reduction, i.e., the remaining cost after taking the discount.


Task: Given $k$, and the graph with edge costs,  find a  minimum cost $k$-discounted cut.

Question: Is anything known about this problem? Can it be solved in polynomial time?

Note: It is well known that the (conventional) minimum cost cut can be found in polynomial time. It is not clear, however, how the discount influences the complexity.
Consider the connectivity interdiction problem, which can be solved in polynomial time [1].


  (Unweighted) Connectivity interdiction
  
  Given a graph $G$ and integer $k$. Find a set $R$ of $k$ edges, such that the min-cut in $G-R$ is minimized. 


Your problem is the same as this problem because $R$ is the $k$ discounted edges in the minimum $k$-discounted cut. 

Zenklusen's paper discusses a more general weighted version of the problem. Each edge has a weight (independent from cost). $R$ is chosen so the weight is at most $k$. That problem admits a PTAS. The special case we care about is when the weights are all $1$, which is the case solvable in polynomial time. 


Zenklusen, Rico, Connectivity interdiction,  ZBL06945298..