2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Apr 30, 2021 at 13:35
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Chris Culter
    Commented Apr 30, 2021 at 23:36
  • $\begingroup$ Ah, that explains it. $\endgroup$
    – Neal Young
    Commented May 1, 2021 at 0:07

1 Answer 1

Reset to default
3
$\begingroup$

...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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.