## Treecost-based Preprocessing for Probabilistic Networks

##### Summary

Probabilistic inference is an important problem in probability theory and concerns the process of computing the probability distribution of variables, given
the evidence of other variables. An often used algorithm for this problem is the junction-tree propagation algorithm. To minimise the time to process all
the probabilities by means of the algorithm, an optimal tree decomposition is required. A good parameter that measures the optimality of a tree decomposition
is treecost. Unfortunately, computing the tree decomposition with minimal treecost is NP-hard Nevertheless, it can be simpli?ed by applying
reduction rules that shrink the graph. These rules are familiar from treewidth, which is a well-studied parameter compared to treecost. In this thesis, a set of
reduction rules are introduced and proven to be valid. This set includes rules that remove vertices and separate the graph by its components. Thereafter,
experiments are conducted on input graphs, which are real-life probabilistic networks. Results of the experiment show that the graphs are reduced signi?cantly,
due to these reduction rules. This, in turn, decreases the time to solve probabilistic inference. Prior knowledge about graph theory and complexity theory is assumed for this thesis.