<p>...aha, found it! This is the <a href="https://en.wikipedia.org/wiki/Bipartite_dimension" rel="nofollow noreferrer">bipartite dimension</a> problem, and yes it is NP-hard without further assumptions.</p>
<p>Previously asked here: <a href="https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p">https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p</a></p>

CC BY-SA 4.0
2021-04-30T05:13:04.800Z
2021-04-30T05:13:04.800Z
Chris Culter
<p>Given finite sets <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> and a subset <span class="math-container">$R\subset X\times Y$</span>, I want to express <span class="math-container">$R$</span> as a union <span class="math-container">$R=\bigcup_{i=1}^n X_i\times Y_i$</span> with <span class="math-container">$n$</span> as small as possible. Here, each <span class="math-container">$X_i\subset X$</span> and <span class="math-container">$Y_i\subset Y$</span>, and I don't care whether the <span class="math-container">$X_i$</span> are disjoint, whether the <span class="math-container">$Y_i$</span> are disjoint, or whether the <span class="math-container">$X_i\times Y_i$</span> are disjoint. (I'm calling each <span class="math-container">$X_i\times Y_i$</span> a &quot;rectangle&quot; but there's no geometry here, just sets.)</p>
<p>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, <span class="math-container">$|R|$</span> maybe?)</p>
<p>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 <span class="math-container">$R$</span> as a matrix or a bipartite graph...?</p>
<p>For what it's worth, in practice I'm interested in what I suspect are fairly easy problem instances, where <span class="math-container">$|X|\leq 15$</span>, <span class="math-container">$|Y|\leq 15$</span>, typically <span class="math-container">$|R|\leq 70$</span>, and the optimal <span class="math-container">$n$</span> is probably <span class="math-container">$\leq 4$</span>. I haven't tried greedy search yet, because I'm hoping for an even simpler solution.</p>

CC BY-SA 4.0
2021-04-30T13:35:11.170Z
Doesn't SET COVER reduce trivially to your problem?  Given a collection $C$ of sets over universe $U$, take $R= U \times \{1\}$, take $X_i = C_i$ (the $i$th set in $C$), and take $Y_1 = \{1\}$.  Then the solutions to your problem of "size" $n$ correspond to the set covers of size $n$.  What am I missing?
Neal Young
CC BY-SA 4.0
2021-04-30T23:36:49.260Z
@NealYoung In my problem, the $X_i$ and $Y_i$ aren't given. Solutions are allowed to range over all subsets of $X$ and $Y$.
Chris Culter
CC BY-SA 4.0
2021-05-01T00:07:42.737Z
Ah, that explains it.
Neal Young
<np-hardness><co.combinatorics><set-cover><bipartite-graphs><covering-problems>
Covering a binary relation as a union of rectangles
Chris Culter
# Covering a binary relation as a union of rectangles

(Asked by: username_0 on 2021-04-30)

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 "rectangle" 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 "nice" 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.

**Tags:** np-hardness, co.combinatorics, set-cover, bipartite-graphs, covering-problems
> **Comments:**
> **username_1**: Doesn't SET COVER reduce trivially to your problem?  Given a collection $C$ of sets over universe $U$, take $R= U \times \{1\}$, take $X_i = C_i$ (the $i$th set in $C$), and take $Y_1 = \{1\}$.  Then the solutions to your problem of "size" $n$ correspond to the set covers of size $n$.  What am I missing?  
> **username_0**: @NealYoung In my problem, the $X_i$ and $Y_i$ aren't given. Solutions are allowed to range over all subsets of $X$ and $Y$.  
> **username_1**: Ah, that explains it.  

---

## 1 answers

### Answer by username_0 on 2021-04-30. Score: 3

...aha, found it! This is the [bipartite dimension](https://en.wikipedia.org/wiki/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>


---

