# Finding a minimal cover of a subset of a finite cartesian product by cartesian products

Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves.

For example, given a product between $I=\{A,B,C\}$ and $J=\{1,2,3\}$, I may observe the subset $\{(A,2), (B,3), (B,2)\}$ and try to cover it with a minimal number of cartesian products.

Two ways to do so are $\{A\} \times \{2\} + B \times \{2,3\}$ and $\{A,B\}\times \{2\} + \{B\}\times \{3\}$, both requiring 2 products. A sub-optimal solution may be breaking it into 3 trivial products.

Can such an optimal cover be found efficiently (e.g., in polynomial time)?

• reminds me of this problem, "factoring cartesian join of bit vectors" (cstheory.SE, phrased much differently) which has connections to circuit theory lower bounds. what context does your problem arise? – vzn Nov 9 '15 at 16:50
• My context is network security. In a large network with many servers, a security policy defines which may speak with which. If such a policy is constructed incrementally over a long period of time, (as it usually is) the description of the security policy may be simplified by merging security rules together. I wish to find an optimal such simplification. – yuvalm2 Nov 9 '15 at 17:01
• Is it only the number of products you want to minimize? If so, what's wrong with using $I \times J$ as your cover? That will cover everything in your subset (and some more). Do you have a requirement that the solution must not only cover the subset, but must also avoid covering anything outside the subset? – D.W. Nov 9 '15 at 20:04
• Also, since this comes from a practical application (and so you probably are looking for practical solutions), can you give a sense of typical parameter sizes? e.g., the typical size of $|I|$, $|J|$, and your subset, to within an order of magnitude or so; or ranges of typical values? This might help evaluate which techniques are most likely to be effective. I'm reminded of logic minimization, DNF, and Karnaugh maps. – D.W. Nov 9 '15 at 21:33
• Perhaps another way to formulate this is the following: Given a bipartite graph $G = (L, R, E)$ find a minimum number of bipartite cliques (or bi-cliques) that cover $E$. Each clique corresponds to a unique product in your cartesian space. – Nicholas Mancuso Nov 10 '15 at 0:47