# 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:

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.

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.

• The variation (a form of network interdiction) where the source $s$ has to be disconnected from the sink $t$ is strongly NP-complete (see Deterministic Network Interdiction by Kevin Wood; the proof applies to both directed and undirected graphs). – Dmytro Taranovsky Apr 5 '19 at 1:30

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..
• For those who cannot access the article, can you add why the abstract talks of PTAS (and confirm whether as stated the problem is the "special case [that can] be solved efficiently"). – Dmytro Taranovsky Apr 5 '19 at 14:19
• I've updated my answer to include this discussion. – Chao Xu Apr 5 '19 at 16:30
• It is quite interesting that the $s-t$ connectivity interdiction is NP-complete (see comment to the original question), while the global connectivity interdiction is in P, but only for the unweighted case. The weighted case becomes NP-complete again, but it has a PTAS, according to the referenced article. – Andras Farago Apr 8 '19 at 20:53
• It is very common for this kind of problem. The weighted case gives us a knapsack constraint. – Chao Xu Apr 8 '19 at 21:23