Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916890658471936 |
|---|---|
| author | Conrado, Giovanna K. Goharshady, Amir K. Motwani, Harshit J. Novozhilov, Sergei |
| author_facet | Conrado, Giovanna K. Goharshady, Amir K. Motwani, Harshit J. Novozhilov, Sergei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_13279 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity Conrado, Giovanna K. Goharshady, Amir K. Motwani, Harshit J. Novozhilov, Sergei Data Structures and Algorithms Computational Complexity Discrete Mathematics 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. |
| title | Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2303.13279 |