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

Lei Nie, Jingjie Liu, Haicang Zhang, and and Zhiwei Xu.
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 n1−ϵ

 inapproximability result for the general case and a View the MathML source

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