2
$\begingroup$

For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble thinking of a good general algorithm for this, and everything I've found online seems to relate to problems that are slightly different to what I'm going for. For example, given the multiset of integers A = {12, 15, 15, 16}, I would like the algorithm to return {15, 16}.

The first naive solution I could think of was to order the numbers in increasing order, take the first number into my set, then take any number after that which is coprime with all of the numbers in the set. This works for things such as {2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, but it would erroneously give {12} in my example above.

Besides that, the best idea I have is to create a list of sets of the factors of each number, at which point this problem can be reduced to the exact cover problem. However, I feel like this would have a relatively large amount of overhead, especially given the fact that the data sets I'm operating on won't be very large (~1000 elements somewhere in between 1 and 500).

Is there any algorithm I could apply here that would be more simple to implement (even if it is slightly slower) and would guarantee an optimal solution?

$\endgroup$
  • $\begingroup$ ±1 are coprime to everything (including themselves) and nothing else is coprime to itself, so starting with a multiset rather than a set only makes a trivial difference. $\;$ $\endgroup$ – user12859 Oct 15 '15 at 18:37
2
$\begingroup$

Your problem is equivalent in complexity to the maximum set packing problem. Unfortunately, maximum set packing is NP-hard. Therefore, you'll need to use one of the methods in Dealing with intractability: NP-complete problems.


Here's the gist of the equivalence. Each integer in your set A corresponds to a set of its prime factors; now you're looking for a maximum-size collection of those sets that are pairwise disjoint. That's exactly maximum set packing. This is only the gist of the idea; this reduction doesn't quite work, because as you noticed, factoring each element of A can take quite a bit of time (there's no known polynomial-time algorithm for factoring).

It's possible to fix up the reduction as follows. Given an instance of your problem, factor A into a coprime base. A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base. For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}. Note that the elements of the coprime base do not need to be prime. There are efficient algorithms for finding a coprime base for A. Now, associate to each number x in A the set of elements of the coprime base that are divisors of x. Then you have an instance of the maximum set packing problem.

(Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.)


So given that you basically have an instance of maximum set packing, what should you do? Well, maximum set packing has been well-studied, so you can use the literature on that problem. Here are some candidate approaches:

ILP: It's easy to formulate the maximum set packing problem as an instance of integer linear programming. You have a zero-or-one variable $x_i$ for each integer $i$ in A, with the idea that $x_i=1$ means that $i$ is included in the output list. You add a constraint $x_i+x_j \le 1$ for every pair of numbers $i,j$ that have a common factor. Then, you try to maximize the objective function $\sum_{i \in A} x_i$. Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find.

If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet. It'll be easy to implement. There's no guarantee that it'll be efficient -- it's an NP-hard problem, after all -- but it might work well enough in practice if the problems sizes are small enough.

Heuristics: You can use any of the known heuristics for set packing. See, e.g., https://en.wikipedia.org/wiki/Set_packing#Heuristics, or search the research literature.

Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set. (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.) If the numbers in A aren't too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective. Wikipedia doesn't say what the algorithm is, so you'll have to do some research in the literature.

$\endgroup$
2
$\begingroup$

Please, identify constraints on the size of multiset and its values.

If they are not very large, you can use Knapsack (Dynamic programming) method to solve this problem.

In this method, you can choose a number in the multiset or not. Therefore, one of the item, which must be considered in the dynamic programming solution, is the position of numbers in your multiset.

The other item is a value which holds LCM (lowest common multiple) of added numbers to an answer. This number, indeed, maintains the LCM of those numbers, which have been used in the current state.

As a result, the number which is going to be added as an element to the optimal set must not have any common factor with the LCM number.

something like that (consider this only a pseudo code): $dp [pos][LCM] = max (dp [pos - 1][LCM] , dp [pos -1][\frac{LCM}{factors\_of\_number [pos]}] + 1)$, where

  • $pos$ stands for the position of a number in a given multiset

  • $number [pos]$ means the value of a number in the position $pos$ of the multiset

  • $factors\_of\_number [pos]$ is the product of all prime numbers, by which $number [pos]$ is divisible; for example, if $number [pos]$ is equal to $12$, the set of prime numbers, which can make $12$, will be $\{2,3\}$, i.e., $factors\_of\_number [pos]$ will be $6 (= 2 \times 3)$
$\endgroup$
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – D.W. Oct 15 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.