Troubleshooting: NP-hardness and solution methods

 Troubleshooting is one of the areas where Bayesian networks are successfully applied [9]. In this paper we show that the generally defined troubleshooting task is NP-hard. We propose a heuristic function that exploits the conditional independence of all actions and questions given the fault of the device. It can be used as a lower bound of the expected cost of repair in heuristic algorithms searching an optimal troubleshooting strategy. In the paper we describe two such algorithms: the depth first search algorithm with pruning and the AO^* algorithm. RID="*" ID="*" The authors were supported through grant #87.2 of National Centre for IT Research, Denmark and through grant MSMT VS96008 from the Ministry of Education, Youth and Sports of the Czech Republic. We would like to thank Finn Verner Jensen for inspiring us to work on the discussed problem and for many valuable comments on this paper. We are grateful to Claus Skaanning for the detailed explanation of the BATS troubleshooter approach and to anonymous reviewers for helpful suggestions.