Algorithm determining the smallest coprime subset

Question

Given a set A of n positive integers, determine a non-empty subset B consisting of as few elements as possible such that their GCD is 1 and output its size.

For example:
5
6 10 12 15 18

yields an output of "3", while:

5
2 4 6 8 10

equals "NONE" since no subset can be determined.

So it seems really basic but I'm still stuck with it. My thoughts on it are as follows: we know that having the multiples of some number already present in the set are useless since their divisors are the same times some factor k and we're going for the smallest subsest. Hence, for every n_i, we remove any kn_i where k is a positive int from further calculations.

That's where I get stuck, though. What should I do next? I can only think of a dumb, brute force approach of trying if there is already some 2-element subset, then 3-elem and so on. What should I check to determine it in some more clever way?

Answer 1

The problem is definitely a tough one to solve. I can't see any computationally efficient algorithm that would guaranteed find the solution in reasonable time.

One approach is: Form a list of ordered sets that would contain the prime factors of each element in the original set.

Now you need to find the minimum number of sets for which their intersection is zero.

To do that, first order these sets in your list so that the sets that have least number of intersections with other sets are towards the beginning. Now what are "least number of intersections"?

This is where heuristics come into play. It can be:
1. set having Less of MIN number of intersections with other elements.
2. set having Less of MAX number of intersections with other elements.
3. Any other more suitable definition.

Now you will need to expensively iterate through all the combinations maybe through recursion to determine the solution.

Answer 2

Suppose for each A,B (two elements) we calculate their greatest common divisor D. And then we store these D values somewhere as a map of the form: A,B -> D Let's say we also store the reverse map D -> A,B

If there's at least one D=1 then there we go - the answer is 2. Suppose now, there's no such D that D=1. What condition should be met for the answer to be 3? I think this one: there exist two D values say D1 and D2 such that GCD(D1, D2)=1. Right? So now instead of As and Bs, we've transformed our problem to the same problem over the set of all Ds and we've transformed the option of a the 2 answer to the option a 3 answer. Right?

I am not 100% sure just thinking out loud.

But this transformed problem is even worse as we have to store much more values. (combinations of N elements class 2).

Not sure, this problem you pose seems like a hard problem to me. I would be surprised if there exists a better approach than brute-force and would be interested to know it.

What you need to think on (and look for) is this: is there a way to express GCD(a1, a2, ... aN) if you know their pair-wise GCDs. If there's some sort of method or formula you can simplify a bit your search (for the smallest subset matching the desired criterion).

See also this link. Maybe it could help.

https://cs.stackexchange.com/questions/10249/finding-the-size-of-the-smallest-subset-with-gcd-1