Cheap and Secure Web Hosting Provider : See Now

[Solved]: Finding a minimal cover of a subset of a finite cartesian product by cartesian products

, , No Comments
Problem Detail: 

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

Asked By : yuvalm2

Answered By : vzn

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback