2020-09-182020-09-182018-081571-0653http://hdl.handle.net/2133/18963In this work, I present an optimization problem which consists of assigning entries of a stellar catalog to multiple entries of another stellar catalog such that the probability of such assignment is maximum. I show a way of modeling it as a Maximum Weighted Stable Set Problem which is further used to solve a real astronomical instance and I partially characterize the forbidden subgraphs of the resulting family of graphs given by that reduction. Finally, I prove that the problem is NP-Hard.application/pdf29–36engopenAccessCross-identificationComplexityMaximum Weighted Stable Set ProblemForbidden subgraphshttp://biblio-int.mincyt.gob.ar/ford/1.3article© 2018 Elsevier B.V. All rights reserved