From Exponential to Linear Time: Counting Independent Sets on Polygonal Arrays

Abstract

This paper compares two approaches with different time complexities for counting independent sets on arrays of molecular graphs. A known method with exponential complexity of order O(2n), where n is the number of polygons in the array. Meanwhile, we propose a novel optimized approach based on the construction of a Hamiltonian path Hc on the array of polygons. This approach combines the Fibonacci and backward path rules to achieve a time complexity of order linear O(4?n), where n is the number of vertices in the array. This novel method not only drastically reduces the computational complexity but also demonstrates its practical applicability in the modeling and analysis of molecular graphs, such as benzenoid compounds, facilitating accurate estimates of the molecular properties and enabling the design of innovative materials.