5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Dmytro Taranovsky Apr 5 at 1:30
4
$\begingroup$

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..
$\endgroup$
  • $\begingroup$ 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"). $\endgroup$ – Dmytro Taranovsky Apr 5 at 14:19
  • $\begingroup$ I've updated my answer to include this discussion. $\endgroup$ – Chao Xu Apr 5 at 16:30
  • $\begingroup$ 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. $\endgroup$ – Andras Farago Apr 8 at 20:53
  • $\begingroup$ It is very common for this kind of problem. The weighted case gives us a knapsack constraint. $\endgroup$ – Chao Xu Apr 8 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.