<p>Consider the connectivity interdiction problem, which can be solved in polynomial time [1].</p>

<blockquote>
  <p><strong>(Unweighted) Connectivity interdiction</strong></p>
  
  <p>Given a graph <span class="math-container">$G$</span> and integer <span class="math-container">$k$</span>. Find a set <span class="math-container">$R$</span> of <span class="math-container">$k$</span> edges, such that the min-cut in <span class="math-container">$G-R$</span> is minimized. </p>
</blockquote>

<p>Your problem is the same as this problem because <span class="math-container">$R$</span> is the <span class="math-container">$k$</span> discounted edges in the minimum <span class="math-container">$k$</span>-discounted cut. </p>

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

<ol>
<li><em>Zenklusen, Rico</em>, <a href="http://dx.doi.org/10.1016/j.orl.2014.07.010" rel="nofollow noreferrer"><strong>Connectivity interdiction</strong></a>,  <a href="https://zbmath.org/?q=an:06945298" rel="nofollow noreferrer">ZBL06945298</a>..</li>
</ol>

CC BY-SA 4.0
2019-04-05T14:19:19.047Z
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
CC BY-SA 4.0
2019-04-05T16:30:13.360Z
I've updated my answer to include this discussion.
Chao Xu
CC BY-SA 4.0
2019-04-08T20:53:32.767Z
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
CC BY-SA 4.0
2019-04-08T21:23:10.227Z
It is very common for this kind of problem. The weighted case gives us a knapsack constraint.
Chao Xu
CC BY-SA 4.0
2019-04-04T21:49:32.043Z
2019-04-05T16:29:33.110Z
2019-04-05T16:29:33.110Z
Chao Xu
<p>Consider an undirected graph <span class="math-container">$G=(V,E)$</span> with non-negative edge costs. Given an integer <span class="math-container">$k$</span> with <span class="math-container">$0\leq k\leq |E|$</span>, let us call an edge set <span class="math-container">$C\subseteq E$</span> a <em><span class="math-container">$k$</span>-discounted cut</em>, if the following hold:</p>

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

<p><strong>Task:</strong> Given <span class="math-container">$k$</span>, and the graph with edge costs,  find a  minimum cost <span class="math-container">$k$</span>-discounted cut.</p>

<p><strong>Question:</strong> Is anything known about this problem? Can it be solved in polynomial time?</p>

<p><em>Note:</em> 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.</p>

CC BY-SA 4.0
2019-04-05T01:30:11.607Z
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](https://faculty.nps.edu/kwood/docs/WoodDetNetInt93.pdf) by Kevin Wood; the proof applies to both directed and undirected graphs).
Dmytro Taranovsky
<graph-theory><graph-algorithms>
Minimum cost cut with discount - what is the complexity?
Andras Farago
# Minimum cost cut with discount - what is the complexity?

(Asked by: username_0 on 2019-04-04)

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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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](https://faculty.nps.edu/kwood/docs/WoodDetNetInt93.pdf) by Kevin Wood; the proof applies to both directed and undirected graphs).  

---

## 1 answers

### Answer by username_2 on 2019-04-04. Score: 4 | Accepted answer

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**](http://dx.doi.org/10.1016/j.orl.2014.07.010), [ZBL06945298](https://zbmath.org/?q=an:06945298)..

> **Comments:**
> **username_1**: 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").  
> **username_2**: I've updated my answer to include this discussion.  
> **username_0**: 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.  
> **username_2**: It is very common for this kind of problem. The weighted case gives us a knapsack constraint.  

---

