# Algorithm that finds concise representations of sets of pairs using Cartesian products

I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.

Suppose as an input you have a list of two-dimensional data points (xi, yi). Your goal is to "simplify" this data by providing an output that is equivalent to the input, but grouped together using structures like this: ({x1, x2, .., xn}, {y1, y2, .., ym}), which denotes a set of all (xa, yb) where a ∈ {1, 2, .., n} and b ∈ {1, 2, .., m}. A perfect result is to have as few of these structures + remaining data points as possible.

Some points to consider:

• The output can be a combination of simple data points and such structures.
• The structures in the output should be mutually exclusive.
• It may as well be that there is no way to simplify a given input.

Example 1:

Input: (1, 1), (1, 2), (2, 1), (2, 2), (4, 5) Output: ({1, 2}, {1, 2}), (4, 5)

Example 2:

Input: (1, 1), (1, 2), (1, 3), (4, 5) Output: ({1}, {1, 2, 3}), (4, 5)

Example 3:

Input: (1, 2), (2, 2), (3, 2), (2, 1), (2, 3) Output: ({1, 2, 3}, {2}), ({2}, {1, 3})

• Your parameter is closely related to the partition number in communication complexity. The only difference is that the partition number counts the number of combinatorial rectangles (your product sets) needed to partition both the 1s (elements in your set) and the 0s (elements not in your set). – Yuval Filmus Sep 2 '15 at 18:24
• Modeling the points as a bipartite graph $B=(X,Y,E)$ such that an edge is a point, your problem is just the biclique decomposition'' problem which asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edges of $B$. – Bangye Sep 3 '15 at 1:19
• I don't know, but can't you probably use k-means clustering: en.wikipedia.org/wiki/K-means_clustering? – mistapink Sep 3 '15 at 5:55

For a given set $S$ of points, we construct a bipartite graph $B=(X\cup Y,E)$ such that there is an edge $(x,y)\in E$ iff there is a point $(x,y)\in S$. The biclique decomposition problem asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edge set $E$ of $B$. Since a biclique in $B$ corresponds to a structure defined in this problem, an algorithm that solves the biclique composition problem also solves this problem.

Conversely, we can also transform the biclique decomposition problem into this problem as follows. Given a bipartite graph $B=(X\cup Y,E)$, where $X=\{x_1,x_2,\ldots x_p\}$ and $Y=\{y_1,y_2,\ldots y_q\}$, we create a set $S$ of points such that $(x_i,y_j)\in E$ iff there is a point $(i,j)\in S$. Consequently, the problem is equivalent to the biclique decomposition problem. However, the biclique decomposition problem is NP-hard, and therefore it is unlikely to solve it efficiently on general bipartite graphs. Note that the problem is equivalent to biclique cover'' if the structures are allowed to be overlapped, i.e., a point can be in more than one structure.

EDIT : bangye's answer above was correct. construct a bipartite graph where each edge is one of your points, each vertex on the left is one abscissa, and the vertices on the right are the ordinates. then apply some biclique decomposition algorithm.

if I understood your notation well, where $(\{1,2\},\{5,6\}),(3,3)$ means $2$ groups, the first with $4$ points ($x = 1$ or $2$ and $y = 5$ or $6$) and the second with $1$ point.

• input : $N$ points, all with integer coordinates

• output : $M$ groups, containing all the information (and no more) of the $N$ points, and we want to minimize $M$

the naive algorithm would be :

• simply start with $M = N$ groups, each containing only one $x$ and one $y$

• then, if possible, group $2$ of these $M$ groups to get $M-1$ groups

• repeat that while necessary

but unfortunately, this doesn't work, we won't minimize $M$ this way.

consider an entry of $3$ points, disposed as a right triangle $(1,1),(1,2),(2,1)$. you can divide it in $2$ groups in $2$ different ways : $$(\{1,2\},1),(1,2) \qquad\text{ or }\qquad (1,\{1,2\}),(2,1)$$

• What is your answer now, the part above or below the line? (When editing, please make sure to always have one answer in each revision. Older version are archived.) – Raphael Sep 7 '15 at 10:51
• this is my answer, I needed 30 min to understand that bangye's answer was correct and how to construct the bipartite graph, and I prefer to not delete my description of dramblys's notation and problem and the naive algorithm to solve it. – reuns Sep 7 '15 at 16:19

While there doesn't exist a non NP-Hard optimal algorithm, here is one way to solve it. I'm going to assume 0-based indexing of the $x_i$s and $y_j$s to simplify below.

Encode the $x$'s using $s+1=\lceil \log n\rceil$ Boolean variables; let's call these $a_0...a_s$ Encode the $y$'s using $t+1=\lceil \log m\rceil$ Boolean variables; let's call these $b_0...b_t$

Then (x,y) maps to a conjunction of literals: E.g. Assuming we have 16 x values, and 16 y values: x0 == 0000, x1=0001, etc. y0 = 0000, y1=0001, ... (x0,y1) = (0000,0001) or $\overline{a_3a_2a_1a_0b_3b_2b_1}b_0$.

Then you can represent all your values as a DNF. (x0,y1) OR (x1,y1) OR ... in literal form.

After that you then want to "compress" the output, that is you want to find the smallest equivalent DNF (this is called logic minimization). There are numerous ways to do this, see e.g. Espresso. From the resulting DNF you then need to go back to your desired output form. In your case, don't cares get expanded in terms of the sets. Thus if we had $\overline{a_3}\overline{a_2}b_3b_2b_1$ this would be: {(0,1,2,3),(14,15)}

Note that when performing the logic minimization, the "out-of-range" values, should make up the Don't Care set. Thus, if there were 15 values for x and 15 values for y, the DC set would be {1111*, *1111}. This is because we don't care what the DNF value is for these inputs, since they are out of range anyway.

• What is "a non NP-Hard optimal algorithm"? – Raphael Sep 7 '15 at 10:50
• See en.wikipedia.org/wiki/… for the general complexity for circuit minimization. – MotiN Sep 7 '15 at 11:23
• I am familiar with the basics, and it's no surprise that the term "NP-Hard optimal algorithm" does not appear anywhere in that article, as it does not make much sense. An algorithm can not be "NP-hard". – Raphael Sep 7 '15 at 13:52