Efficient trick for maximal bipartite matching in bigger graph

Question

Problem: We are given two arrays A & B of integers. Now in each step we are allowed to remove any 2 non co-prime integers each from the two arrays. We have to find the maximal number of pairs that can be removed by these steps.

Bounds: length of A, B <=10⁵
every integer <=10⁹
Dinic's algorithm - O(V²E)
Edmonds-karp algorithm - O(VE²)
Hopcroft–Karp algorithm - O(E sqrt(V))

My approach up till now: This can be modeled as bipartite matching problem with two sets A and B and edges can be created between every non co-prime pair of integers from the corresponding set.
But the problem is that there can be O(V²) edges in the graph and most Bipartite matching and max-flow algorithms will be super slow for such large graphs.

I am looking for some problem specific or mathematical optimization that can solve the problem in reasonable time. To pass the test cases i need at most O(V log V) or O(V sqrt(V)) algorithm.

Thanks in advance.

Answer 1

You could try making a graph with vertices for:

1. A source
2. Every element in A
3. Every prime present in any number in A
4. Every element in B
5. A destination

Add directed edges with capacity 1 from source to elements in A, and from elements in B to destination.

Add directed edges with capacity 1 from each element x in A to every distinct prime in the prime factorisation of x.

Add directed edges with capacity 1 from each prime p to every element x in B where p divides x

Then solve for max flow from source to destination.

The numbers will have a small number of factors (at most 9 because 2.3.5.7.11.13.17.19.23.29 is bigger than 10**9), so you will have at most 1,800,000 edges in the middle.

This is much fewer than the 10,000,000,000 edges you could have had before (e.g. if all 100,000 entries in A and B were all even) so perhaps your max flow algorithm has a chance of meeting the time limit.