Branch decompositions in networks analysis

Many models of social interaction on a network are based on concepts from Statistical Physics, such as percolation and spin kinetics under pairwise interactions. Sociophysics models thus inherit the hardness of analyzing the dynamics on one specific (quenched) network in exact terms. With frustration in spin interactions, for instance, the computation of ground states is NP-hard, thus unlikely feasible in polynomial time. In practice, the cavity method may provide good approximations by treating networks as tree-like. Here we find, however, that exact computation is possible in many medium-size networks due to existence of a branch decomposition of small width: the edge set of the network may be bipartitioned recursively with only few nodes shared by the two sides of the partition at each level.