Complexity and compilability of diagnosis and recovery of graph-based systems

This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. (c) 2005 Wiley Periodicals, Inc.