Return to Question

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:

111000011100001101000001001111111111000
111000011100001101000000101111111111000
111111111111110010010100000011100000000
000111100011111100110000001100011111010
111111111111110010010010000011100000000
111000011100001101000000011111111111000
000111100011111100110000001100011111100
111111111111110010011000000011100000000
000111100011111100110000001100011111001

I want to find the maximum value of the product $(1+|C_1|)(1+|C_2|)$, where $C_1$ and $C_2$ are any two disjoint subsets of the column indexes of $A$, such that for every $i \in C_1$ and every $j \in C_2$ and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$. It is not required that $C_1 \cup C_2 = [n] = \{1, \ldots, n\}$.

For example, if we permute rows and columns of the above matrix we get:

111111111111111111000000000100100000000
111111111111111111000000000100010000000
111111111111111111000000000100001000000
111111111000000000111111111010000100000
111111111000000000111111111010000010000
111111111000000000111111111010000001000
000000000111111111111111111001000000100
000000000111111111111111111001000000010
000000000111111111111111111001000000001

and then it is clear that $\max{(1+|C_1|)(1+|C_2|)} = 10 \cdot 20 = 200$.

The matrix $A$ can be regarded as the biadjency matrix of a bipartite graph and $C_1$ and $C_2$ correspond to two complete bipartite supgraphs such that the union of their respective "row" parts gives the "row" part of the bipartite graph corresponding to $A$.

I could try all possible choices for $C_1$ and then evaluate the product based on the $C_2$ that follows, but the algorithm has a time complexity greater than $O(2^n)$.

Can we do better than that? Is there any measure (e.g. some entropy measure) to at least estimate the maximum value?

A possible generalization of the problem would be computing (or estimating) the maximum of the product $\prod_{r=1}^{q}{(1+|C_r|)}$ (with any $q \ge 2$ that maximizes the product) and $C_1, \ldots ,C_q$ disjoint, such that for every $i \in C_s$ and every $j \in C_t$, $1 \le s \lt t \le q$, and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$.

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:

111000011100001101000001001111111111000
111000011100001101000000101111111111000
111111111111110010010100000011100000000
000111100011111100110000001100011111010
111111111111110010010010000011100000000
111000011100001101000000011111111111000
000111100011111100110000001100011111100
111111111111110010011000000011100000000
000111100011111100110000001100011111001

I want to find the maximum value of the product $(1+|C_1|)(1+|C_2|)$, where $C_1$ and $C_2$ are any two disjoint subsets of the column indexes of $A$, such that for every $i \in C_1$ and every $j \in C_2$ and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$. It is not required that $C_1 \cup C_2 = [n] = \{1, \ldots, n\}$.

For example, if we permute rows and columns of the above matrix we get:

111111111111111111000000000100100000000
111111111111111111000000000100010000000
111111111111111111000000000100001000000
111111111000000000111111111010000100000
111111111000000000111111111010000010000
111111111000000000111111111010000001000
000000000111111111111111111001000000100
000000000111111111111111111001000000010
000000000111111111111111111001000000001

and then it is clear that $\max{(1+|C_1|)(1+|C_2|)} = 10 \cdot 20 = 200$.

The matrix $A$ can be regarded as the biadjacency matrix of a bipartite graph and $C_1$ and $C_2$ correspond to two complete bipartite subgraphs such that the union of their respective "row" parts gives the "row" part of the bipartite graph corresponding to $A$.

I could try all possible choices for $C_1$ and then evaluate the product based on the $C_2$ that follows, but the algorithm has a time complexity greater than $O(2^n)$.

Can we do better than that? Is there any measure (e.g. some entropy measure) to at least estimate the maximum value?

A possible generalization of the problem would be computing (or estimating) the maximum of the product $\prod_{r=1}^{q}{(1+|C_r|)}$ (with any $q \ge 2$ that maximizes the product) and $C_1, \ldots ,C_q$ disjoint, such that for every $i \in C_s$ and every $j \in C_t$, $1 \le s \lt t \le q$, and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$.

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:

111000011100001101000001001111111111000
111000011100001101000000101111111111000
111111111111110010010100000011100000000
000111100011111100110000001100011111010
111111111111110010010010000011100000000
111000011100001101000000011111111111000
000111100011111100110000001100011111100
111111111111110010011000000011100000000
000111100011111100110000001100011111001

I want to find the maximum value of the product $(1+|C_1|)(1+|C_2|)$, where $C_1$ and $C_2$ are any two disjoint subsets of the column indexes of $A$, such that for every $i \in C_1$ and every $j \in C_2$ and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} =1 $. It is not required that $C_1 \cup C_2 = [n] = \{1, \ldots, n\}$.

For example, if we permute rows and columns of the above matrix we get:

111111111111111111000000000100100000000
111111111111111111000000000100010000000
111111111111111111000000000100001000000
111111111000000000111111111010000100000
111111111000000000111111111010000010000
111111111000000000111111111010000001000
000000000111111111111111111001000000100
000000000111111111111111111001000000010
000000000111111111111111111001000000001

and then it is clear that $\max{(1+|C_1|)(1+|C_2|)} = 10 \cdot 20 = 200$.

The matrix $A$ can be regarded as the biadjency matrix of a bipartite graph and $C_1$ and $C_2$ correspond to two complete bipartite supgraphs such that the union of their respective "row" parts gives the "row" part of the bipartite graph corresponding to $A$.

I could try all possible choices for $C_1$ and then evaluate the product based on the $C_2$ that follows, but the algorithm has a time complexity greater than $O(2^n)$.

Can we do better than that? Is there any measure (e.g. some entropy measure) to at least estimate the maximum value?

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:

111000011100001101000001001111111111000
111000011100001101000000101111111111000
111111111111110010010100000011100000000
000111100011111100110000001100011111010
111111111111110010010010000011100000000
111000011100001101000000011111111111000
000111100011111100110000001100011111100
111111111111110010011000000011100000000
000111100011111100110000001100011111001

I want to find the maximum value of the product $(1+|C_1|)(1+|C_2|)$, where $C_1$ and $C_2$ are any two disjoint subsets of the column indexes of $A$, such that for every $i \in C_1$ and every $j \in C_2$ and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$. It is not required that $C_1 \cup C_2 = [n] = \{1, \ldots, n\}$.

For example, if we permute rows and columns of the above matrix we get:

111111111111111111000000000100100000000
111111111111111111000000000100010000000
111111111111111111000000000100001000000
111111111000000000111111111010000100000
111111111000000000111111111010000010000
111111111000000000111111111010000001000
000000000111111111111111111001000000100
000000000111111111111111111001000000010
000000000111111111111111111001000000001

and then it is clear that $\max{(1+|C_1|)(1+|C_2|)} = 10 \cdot 20 = 200$.

The matrix $A$ can be regarded as the biadjency matrix of a bipartite graph and $C_1$ and $C_2$ correspond to two complete bipartite supgraphs such that the union of their respective "row" parts gives the "row" part of the bipartite graph corresponding to $A$.

I could try all possible choices for $C_1$ and then evaluate the product based on the $C_2$ that follows, but the algorithm has a time complexity greater than $O(2^n)$.

Can we do better than that? Is there any measure (e.g. some entropy measure) to at least estimate the maximum value?

A possible generalization of the problem would be computing (or estimating) the maximum of the product $\prod_{r=1}^{q}{(1+|C_r|)}$ (with any $q \ge 2$ that maximizes the product) and $C_1, \ldots ,C_q$ disjoint, such that for every $i \in C_s$ and every $j \in C_t$, $1 \le s \lt t \le q$, and for every $1 \le k \le m$, either $a_{ki} = 1$ or $a_{kj} = 1$.