Finding minimal subsets of a finite integer set with gcd equal to the whole set - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T08:52:18Z http://mathoverflow.net/feeds/question/45240 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45240/finding-minimal-subsets-of-a-finite-integer-set-with-gcd-equal-to-the-whole-set Finding minimal subsets of a finite integer set with gcd equal to the whole set Max 2010-11-07T23:51:28Z 2010-11-08T02:02:05Z <p>Given a finite non-empty set $N$ of integers, call a subset $M$ of $N$ <em>good</em> if $gcd(M)=gcd(N)$. The other subsets are called <em>bad</em>.</p> <blockquote> <p>Does there exist an algorithm which computes a good subset of minimal size in polynomial time (polynomial in $|N|$)?</p> </blockquote> <p>Using a greedy strategy, it is easy to find good subsets $M$ which are minimal with respect to inclusion (i.e. every proper subset of $M$ is bad). But it is not difficult to construct examples where such a greedy strategy may fail to find a set of globally minimal size. Take for example N={6=2*3, 10=2*5, 15=3*5, 1}. Then $gcd(N)=1$, and both {6,10,15} and {1} are good subsets. Both are minimal good subset wrt to inclusion. This can be easily generalized.</p> <p>So, something more advanced would needed. Obviously, one can test all subsets, but then one gets exponential runtime. Is there a better way? Or can one prove that there isn't? Maybe this is equivalent to efficiently factoring primes? As it is, I am not even sure whether this problem is in NP...</p> <p>(Note that this question is about an important special case of an <a href="http://mathoverflow.net/questions/44888/finding-globally-minimal-row-subsets-of-an-integer-matrix-which-generate-the-full" rel="nofollow">earlier question of mine</a>; I hope it'll attract a few more people by being less technical).</p> http://mathoverflow.net/questions/45240/finding-minimal-subsets-of-a-finite-integer-set-with-gcd-equal-to-the-whole-set/45245#45245 Answer by Qingchun Ren for Finding minimal subsets of a finite integer set with gcd equal to the whole set Qingchun Ren 2010-11-08T01:28:49Z 2010-11-08T01:28:49Z <p>I claim that the set cover problem (http://en.wikipedia.org/wiki/Set_cover_problem) can be reduced to this problem. So this problem is NP-hard.</p> <p>Given a universe $U$ and a family $S$ that covers $U$, correspond the elements of $U$ to distinct primes and correspond each $A\in{}S$ to the product of the primes that correspond to the elements of $U-A$. Then a subcover of minimum size is equivalent to a good subset of minimum size.</p> http://mathoverflow.net/questions/45240/finding-minimal-subsets-of-a-finite-integer-set-with-gcd-equal-to-the-whole-set/45247#45247 Answer by Aaron Meyerowitz for Finding minimal subsets of a finite integer set with gcd equal to the whole set Aaron Meyerowitz 2010-11-08T01:54:47Z 2010-11-08T02:02:05Z <p>I think it would be NP complete. One NP complete problem is to determine if a graph has an <a href="http://en.wikipedia.org/wiki/Vertex_cover_problem" rel="nofollow">Vertex Cover </a> of size $k$: given graph with m vertices and e edges is there a set of k vertices including at least on endpoint of each edge? To encode this in your problem, assign a unique prime $p_i$ to each edge $e_i$, let $P=\prod p_i$, and assign to each vertex $v$ the integer $\frac{P}{\prod_{v \in e_i}p_i}$. Then the $\gcd$ is $1$ and a subset with that $\gcd$ is a vertex cover of the edges.</p> <p>I am sure that there are other more elegant covering or satisfiability problems but that will do.</p> <p>I'd say leave the issue of factoring out of it by assuming that the factorizations are all known. Of course then you could replace each integer $2^a3^b5^c\cdots$ by a vector $[a,b,c,\cdots]$ and look at the entry-wise minimum over the whole set and over various subsets.</p>