## On the inapproximability of minimizing cascading failures under the deterministic threshold model

Information Processing Letters 114, no. 1 (2014): 1-4 (2014)

Given a directed graph *G * and a threshold L(r)

$$

for each node *r *, the rule of deterministic threshold cascading is that a node *r * fails if and only if it has at least L(r)

$$

failed in-neighbors. The cascading failure minimization problem is to find at most *k * edges to delete, such that the number of failed nodes is minimized. We prove an n^{1−ϵ}

$$

inapproximability result for the general case and a

$$

inapproximability result for the special case with the maximum threshold of 1.