A Branch and Bound Algorithm for Counting Independent Sets on Grid Graphs

Abstract

A relevant problem in combinatorial mathematics is the problem of counting independent sets of a graph G, denoted by i(G). This problem has many applications in combinatorics, physics, chemistry and computer science. For example, in statistical physics, the computation of i(G) has been useful in studying the behavior of the particles of a gas on a space modeled by a grid structure. Regarding hard counting problems, the computation of i(G) for a graph G has been key to 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, which is to be selected for the reduction rule, must have four internal incident faces. The ramification process is used to build a computation tree. Our proposal consists of decomposing the initial grid graph until outerplanar graphs are obtained as the ‘basic subgrids’ associated with the leave nodes of the computation tree. The resulting time-complexity of our proposal is inferior to the time-complexity of other classic methods, such as the transfer matrix method.

Keywords

• grid graphs
• graph decomposition
• transfer matrix method
• branch and bound technique
• counting independent sets