A branch and bound algorithm for counting independent sets on grid graphs

The problem of counting independent sets of a graph G, denoted by i(G), is not only mathematically relevant and interesting, but also has many applications in physics, mathematics, and theoretical computer science. Regarding hard counting problems, the computation of i(G) for a graph G has been a key for determining the frontier between efficient counting and intractable counting procedures. In this article, a novel algorithm for counting independent sets on grid-like structures is presented.

We propose a novel algorithm for the computation of i(Gm,n) for a grid graph with m rows and n columns, based on the ‘Branch and Bound’ design technique. The splitting rule in our proposal is based on the well-known vertex reduction rule. The vertex in any subgraph from Gm,n to be selected for the vertex reduction rule must have degree 4. Our proposal consists of decomposing a grid graph until obtaining subgraphs without vertices of degree 4, which are called ‘basic subgrids’. We show how to compute efficiently the number of independent sets for those basic subgrids graphs, and we show which are the new graph topologies expressed by such basic subgrids.

The resulting time-complexity of our proposal for computing the number of independent sets for grid graphs is dramatically inferior to the time-complexity that the classic transfer matrix method requires for computing the same value.