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)?

  • $\begingroup$ 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? $\endgroup$ – vzn Nov 9 '15 at 16:50
  • $\begingroup$ 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. $\endgroup$ – yuvalm2 Nov 9 '15 at 17:01
  • $\begingroup$ 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? $\endgroup$ – D.W. Nov 9 '15 at 20:04
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Nov 9 '15 at 21:33
  • 3
    $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Nov 10 '15 at 0:47

NM reformulates this problem in comments as finding minimum number of bipartite cliques (bi-cliques) that cover a bipartite graph. the two sets you mention are the 2 vertex sets of the bipartite graph. the cartesian products of subsets of the two vertex sets are bicliques. wikipedia states this is the bipartite dimension problem and is problem GT18 in Garey and Johnson, proved NP complete based on straightforward reformulation of set basis problem SP7.


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.