Branch decompositions for computing exact percolation properties and Ising partition functions of networks

Abstract

Tree-like approximation is commonly used in computing dynamic properties of quenched finite network realizations. Such properties include expected percolation cluster sizes, epidemic thresholds, and Ising/Potts densities of states. That method is exact only when the network is a tree: removal of one node leaves the network disconnected and this separation recursively holds on the connected components obtained, until reaching the base case of a component with one edge only. Here we consider the generalization of recursive separation by allowing a set of up to k nodes as a separator in each step. With the recursion tree denoted as a branch decomposition of the given network, the maximum separator size k occurring is called branch-width w. In this talk, we discuss (i) how to find branch decompositions of low width w and (ii) how to use these decompositions in obtaining exact results on percolation, Ising model and other processes running on networks.