The Inverse Problems for Some Topological Indices in Combinatorial Chemistry

In the original paper, Goldman et al. (2000) launched the study of the inverse problems in combinatorial chemistry, which is closely related to the design of combinatorial libraries for drug discovery. Following their ideas, we investigate four other topological indices, i.e., the σ-index, the c-index, the Z-index, and the M₁-index, with a special emphasis on the σ-index. Like the Wiener index, these four indices are very popular in combinatorial chemistry and reflect many chemical and physical properties. We give algorithmic and analytical solutions for the inverse problems of the four indices. We also show that the SUBTREEVALUE reconstruction problem for the σ-index is NP-hard.