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.