Finding partition of a relation such that each element in partition set is a cartesian product

Question

Suppose we have sets A = {A₁,A₂.... A_n} and B = {B₁,B₂,...B_m}

and a relation R having elements like (A_i,B_j).

The aim is to make a partition set P of relation R such that each element (or cover of the partition) in the partition set is a cartesian product.

Example:

If R = {{A₁,B₁},{A₂,B₂},{A₁,B₂}}

then I want to make a partition set like

P = { { {A₁,B₁},{A₁,B₂} }, { {A₂,B₂} } }

Here both { {A₁,B₁},{A₁,B₂} } and {{A₂,B₂}} are cartesian products or we may say set of elements from A and B such that all elements Ai are matched with Bj in that set.

The union of these two sets make R and also { {A₁,B₁},{A₁,B₂} } and {{A₂,B₂}} are disjoint hence making P the partition set.

What algorithm/theorem should I follow to find a partition set like this? Note that R here will be a relation where always consisting of pairs as it's elements in which always first item will be from A and second from B. So {B₁,A₁} is not possible.

Other examples:

R = {{A₁,B₁},{A₂,B₂}} then P = {{A₁,B₁},{A₂,B₂}} because both {A₁,B₁} and {A₂,B₂} are independently cross products.

R = {{A₁,B₁},{A₁,B₂},{A₂,B₁},{A₂,B₂},{A₁,B₃}}

then P contains elements {{A₁,B₁},{A₁,B₂},{A₂,B₁},{A₂,B₂}} and {{A₁,B₃}}

Answer 1

You have a bipartite graph $G$ (with $A$ on one side and $B$ on the other, with edges determined by $R$). Then what you are asking for is known under the name biclique partition of $G$. You will find some literature about it online.

The problem of finding the smallest such partition (minimum cardinality biclique partition) is NP-hard, and I think it remains NP-hard in the class of bipartite graphs.