Skip to main content
added 294 characters in body
Source Link
Chao Xu
  • 4.5k
  • 24
  • 32

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

Connectivity(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..

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

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.

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

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..
Source Link
Chao Xu
  • 4.5k
  • 24
  • 32

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

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.

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