Abstract

Given a directed graph G and a threshold for each node r, the rule of deterministic threshold cascading is that a node r fails if and only if it has at least 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 inapproximability result for the general case and a inapproximability result for the special case with the maximum threshold of 1.