Covering a binary relation as a union of rectangles Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\subset Y$, and I don't care whether the $X_i$ are disjoint, whether the $Y_i$ are disjoint, or whether the $X_i\times Y_i$ are disjoint. (I'm calling each $X_i\times Y_i$ a &quot;rectangle&quot; but there's no geometry here, just sets.)
If I think of this as a generic set cover problem, then it looks like it might be NP-hard. (With respect to what variable though, $|R|$ maybe?)
But I'm really hoping that this version of the problem, using these really &quot;nice&quot; rectangular covering sets that intersect in predictable ways, might be easier. What is known about this problem? Does it have a standard name and a nice theory behind it? Maybe if we think of $R$ as a matrix or a bipartite graph...?
For what it's worth, in practice I'm interested in what I suspect are fairly easy problem instances, where $|X|\leq 15$, $|Y|\leq 15$, typically $|R|\leq 70$, and the optimal $n$ is probably $\leq 4$. I haven't tried greedy search yet, because I'm hoping for an even simpler solution.
...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions.
Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p