Finding minimal subsets of a finite integer set with gcd equal to the whole set - MathOverflow

Finding minimal subsets of a finite integer set with gcd equal to the whole set

2010-11-07T23:51:28Z

Given a finite non-empty set $N$ of integers, call a subset $M$ of $N$ good if $gcd(M)=gcd(N)$. The other subsets are called bad.

Does there exist an algorithm which computes a good subset of minimal size in polynomial time (polynomial in $|N|$)?

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.

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...

(Note that this question is about an important special case of an earlier question of mine; I hope it'll attract a few more people by being less technical).

Answer by Qingchun Ren for Finding minimal subsets of a finite integer set with gcd equal to the whole set

2010-11-08T01:28:49Z

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.

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.

Answer by Aaron Meyerowitz for Finding minimal subsets of a finite integer set with gcd equal to the whole set

2010-11-08T01:54:47Z

I think it would be NP complete. One NP complete problem is to determine if a graph has an Vertex Cover 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.

I am sure that there are other more elegant covering or satisfiability problems but that will do.

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.