  This paper analyzes the circumstances under which Bayesian networks can be
pruned in order to reduce computational complexity without altering the
computation for variables of interest. Given a problem instance which consists
of a query and evidence for a set of nodes in the network, it is possible to
delete portions of the network which do not participate in the computation for
the query. Savings in computational complexity can be large when the original
network is not singly connected. Results analogous to those described in this
paper have been derived before [Geiger, Verma, and Pearl 89, Shachter 88] but
the implications for reducing complexity of the computations in Bayesian
networks have not been stated explicitly. We show how a preprocessing step can
be used to prune a Bayesian network prior to using standard algorithms to solve
a given problem instance. We also show how our results can be used in a
parallel distributed implementation in order to achieve greater savings. We
define a computationally equivalent subgraph of a Bayesian network. The
algorithm developed in [Geiger, Verma, and Pearl 89] is modified to construct
the subgraphs described in this paper with O(e) complexity, where e is the
number of edges in the Bayesian network. Finally, we define a minimal
computationally equivalent subgraph and prove that the subgraphs described are
minimal.
