2014/02/21 by Joachim von zur Gathen, Gathen, Joachim von zur, Igor E. Shparlinski +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Number Theory (math.NT) #cs.CC #math.NT
paper · pdf · doi:10.48550/arxiv.1402.5449
arxiv created 2014/02/21 · openalex publication_date 2014/02/21 · arxiv updated 2014/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two sets A and B of integers, we consider the problem of finding a set S ⊆ A of the smallest possible cardinality such the greatest common divisor of the elements of S ∪ B equals that of those of A ∪ B. The particular cases of B = ∅ 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.