The Algorithm In Detail

To solve an arbitrary network we first determine the set $\Omega$ of all $S_\mathrm{\scriptscriptstyle sep}$ we will use for the problem. We choose

$$\Omega\left(N\right)=\left\{S_\mathrm{\scriptscriptstyle sep... ...rt S_\mathrm{\scriptscriptstyle cl}\cup s\right\Vert>N\right\}$$ (10)

where $S_\mathrm{\scriptscriptstyle cl}$ is the cluster $S_\mathrm{\scriptscriptstyle sep}\cup S_\mathrm{\scriptscriptstyle mar}\cup S_\mathrm{\scriptscriptstyle oth}$ and $s$ denotes a single node. This choice limits the state space of $S_\mathrm{\scriptscriptstyle cl}$ to $N$, which more or less determines the computation time. If we choose, for example, $N=2^5$ for the Ising grid in Figure  assuming binary nodes, only the configuration in Figure a would be included in $\Omega$. Choosing $N=2^8$ puts the configurations in Figure b-d and a few others not shown into $\Omega$, but not Figure a, since that separator is already embedded in larger ones (e.g. Figure d). In other words: $\Omega\left(N\right)$ is the set of all $S_\mathrm{\scriptscriptstyle sep}$ for which $\left\Vert S_\mathrm{\scriptscriptstyle sep}\cup S_\mathrm{\scriptscriptstyle mar}\cup S_\mathrm{\scriptscriptstyle oth}\right\Vert$ is not larger than $N$, but if we add a single node it would cross that boundary.

We will compute bounds for all $S_\mathrm{\scriptscriptstyle mar}$ for which there can be found a separator in $\Omega$. We reserve memory for $p_+\left(S_\mathrm{\scriptscriptstyle mar}\right)$ and $p_-\left(S_\mathrm{\scriptscriptstyle mar}\right)$ and initialize them to one and zero respectively. Note that if we have a bound over $S_\mathrm{\scriptscriptstyle mar}$ it is still worthwhile to compute bounds over subsets of $S_\mathrm{\scriptscriptstyle mar}$ (e.g. Figure b and d). In contrast to a joint probability table, the bounds on marginals over subsets cannot be computed simply by summing over the marginal of $S_\mathrm{\scriptscriptstyle mar}$, since we have only bounds and not the real values.