如何在布尔数组中找到模式组？

Question

给定一个布尔值的2D数组,我想找到包含至少2列和至少2行的所有模式.问题与图中的派系有些接近.

在下面的示例中,绿色单元格表示"真实"位,灰色表示"假".模式1包含cols 1,3,4和5以及行1和2.模式2仅包含第2列和第4列以及第2,3,4行.

这背后的商业理念是在各种社交网络用户群之间找到相似性模式.在现实世界中,行数最多可达3E7,列数最多可达300.

除了蛮力匹配之外,无法找到解决方案.

请告知问题的正确名称,以便我可以阅读更多内容,或建议优雅的解决方案.

Answer 1

这（相当于）要求二分图中所有大于特定大小的bicliques （完整二分子图）。这里的行是图的一个部分 A 的顶点，列是另一部分 B 的顶点，只要 u 行、v 列的单元格在 u \in A 和 v \in B 之间就有一条边是绿色的。

尽管您说要查找所有模式，但您可能只想查找最大的模式，即无法通过添加更多行或列来扩展为更大模式的模式。（否则，对于任何 c >= 2 列和 r >= 3 行的模式，您还将得到超过 2^(c-2)*2^(r-3) 个可以形成的非最大模式通过删除一些行或列。）

但是，假设 P != NP，即使仅列出最大模式也会花费行数和列数呈指数级的时间。这是因为就绿色单元总数而言，找到最大（即最大可能）模式的问题已被证明是 NP 完全的：如果可以在多项式时间内列出所有最大模式，那么我们可以简单地这样做，并选择最大的，从而在多项式时间内解决这个 NP 完全问题。