MINIMUM NETWORK INHIBITION ON PLANAR GRAPHS

• INSTANCE: Planar graph $G=\left(V,E\right)$, capacity function $c : E \rightarrow N$, destruction cost function $d: E \rightarrow N$, and budget B.

• SOLUTION: An attack strategy to the network, i.e., a function $\alpha: E \rightarrow [0,1]$ such that $\sum_{e \in E}\alpha(e)d(e) \leq B$.

• MEASURE: The capability left in the damaged network, i.e., the minimum cut in G with capacity c' defined as $c'(e)=\alpha(e)c(e)$.

  
  

• Good News: Admits an FPTAS [402].