Fault diagnosis is a vital aspect in the design of operational control systems for large-scale systems with stringent requirements on safety and reliability. In this paper, we develop graph representations for the failure propagation in large-scale systems. Using this model, we present efficient algorithms for failure source identification for single and multiple faults, for diagnosis of faulty alarms, and for forewarning and fault simulation. All these algorithms are analysed for their worst-case complexities. The treatment is algorithmic and graph theoretic and no reference is made to the underlying physical systems.