Circulant graphs and GCD and LCM of Subsets

Given two sets $A$ and $B$ of integers, we consider the problem of finding a set $S\subseteq A$ of the smallest possible cardinality such the greatest common divisor of the elements of $S\cup B$ equals that of those of $A \cup B$\mathrm{.}Theparticularcasesof$B = \emptyset$and$#B = 1$ are of special interest and have some links with graph theory. We also consider the corresponding question for the least common multiple of the elements. We establish NP-completeness and approximation results for these problems by relating them to the Minimum Cover Problem.