2023/03/23 by Giovanna Kobus Conrado, Amir K. Goharshady, Conrado, Giovanna K. +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computational Drug Discovery Methods #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2303.13279
openalex publication_date 2023/03/23 · openalex created_date 2023/03/25 · openalex updated_date 2026/07/28
We present efficient combinatorial parameterized algorithms for several classical graph-based counting problems in computational chemistry, including (i) Kekule structures, (ii) the Hosoya index, (iii) the Merrifield-Simmons index, and (iv) Graph entropy based on matchings and independent sets. All these problems were known to be #P-complete. Building on the intuition that molecular graphs are often sparse and tree-like, we provide fixed-parameter tractable (FPT) algorithms using treewidth as our parameter. We also provide extensive experimental results over the entire PubChem database of chemical compounds, containing more than 113 million real-world molecules. In our experiments, we observe that the molecules are indeed sparse and tree-like, with more than 99.9% of them having a treewidth of at most 5. This justifies our choice of parameter. Our experiments also illustrate considerable improvements over the previous approaches. Based on these results, we argue that parameterized algorithms, especially based on treewidth, should be adopted as the default approach for problems in computational chemistry that are defined over molecular graphs.