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

A relevant problem in combinatorial mathematics is the problem of counting independent sets of a graph <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. This problem has many applications in combinatorics, physics, chemistry and computer science. For example, in statistical physics, the computation of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> for a graph <i>G</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><msub><mi>G</mi><mrow><mi>m</mi><mo>,</mo><mi>n</mi></mrow></msub><mo>)</mo></mrow></semantics></math></inline-formula> for a grid graph with <i>m</i> rows and <i>n</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>G</mi><mrow><mi>m</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula>, 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.