Minimum cost cut with discount - what is the complexity?

Question

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:

1. $C$ is a cut in the usual sense.

2. 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.

Answer 1

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.

1. Zenklusen, Rico, Connectivity interdiction, ZBL06945298..