Some Complexity Considerations in the Combination of Belief Networks
  One topic that is likely to attract an increasing amount of attention within
the Knowledge-base systems research community is the coordination of
information provided by multiple experts. We envision a situation in which
several experts independently encode information as belief networks. A
potential user must then coordinate the conclusions and recommendations of
these networks to derive some sort of consensus. One approach to such a
consensus is the fusion of the contributed networks into a single, consensus
model prior to the consideration of any case-specific data (specific
observations, test results). This approach requires two types of combination
procedures, one for probabilities, and one for graphs. Since the combination of
probabilities is relatively well understood, the key barriers to this approach
lie in the realm of graph theory. This paper provides formal definitions of
some of the operations necessary to effect the necessary graphical
combinations, and provides complexity analyses of these procedures. The paper's
key result is that most of these operations are NP-hard, and its primary
message is that the derivation of ?good? consensus networks must be done
heuristically.
