Factoring Cartesian bitwise join of bit vectors

Question

(This question has been substantially revised in an attempt to word it clearly.)

I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a_i\}_{i\in[r]} \quad\text{and} \quad B=\{b_j\}_{j\in[s]} \;,$$ where each $a_i \in \{0, 1\}^n$ and each $b_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c_{i,j}\}_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where $$ c_{i,j} = a_i \vee b_j$$ where "$\vee$" is bitwise-OR.

Question. If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c_k)_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a_i)_{i\in[r]}$ and $B = (b_j)_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c_{\varphi(i,j)} = a_i \vee b_j$$ for all $(i,j) \in [r] \times [s]$?

---

This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$. The Cartesian bitwise join corresponds to the outer product of $A$ and $B$, $$ C \;=\; A B^\top \;=\; \begin{bmatrix} a_1 \vee b_1 & a_1 \vee b_2 &\cdots& a_1 \vee b_s \\ a_2 \vee b_1 & a_2 \vee b_2 & \cdots & a_2 \vee b_s \\ \vdots & \vdots & & \vdots \\ a_r \vee b_1 & a_r \vee b_2 & \cdots & a_r \vee b_s \end{bmatrix}\;,$$ except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?

(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z_2$, and multiplication is the bit-wise AND. )

---

One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.

• This problem arises in an EE & complexity theory context. I am looking for other cases or analysis of it.
• The problem is somewhat analogous to factoring but does not seem to have a unique factorization.
• Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.

Answer 1

Passing to the dual hypergraphs to look for products.

As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.

• Vertices are the elements of $[n]$;
• An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x_v = 1$.

(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where

• The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and
• A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x_e =1$;

— that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge". This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H_C$ obtained from a multiset $C$ now has a composite number of vertices $m$: we would like hypergraphs $H_A$ and $H_B$ such that $V(H_C)$ has some particular bijective correspondance with $V(H_A) \times V(H_B)$.

A diagonally restricted tensor product of hypergraphs.

Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.) The Cartesian bit-wise meet condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H_A) \times V(H_B) \to V(H_C)$$ such that the edge labelled $e \in [n]$ in $H_C$ contains only the vertices $\varphi(a,b) \in V(H_C)$ such that both $a \in V(H_A)$ and $b \in V(H_B)$ are contained in the respective edges labelled by $e$ in $H_A$ and $H_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.

• If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the tensor product of graphs, also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H_A) \times E(H_B)$ which contain all vertices $(a,b) \in V(H_A) \times V(H_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H_A \otimes H_B$.

• To re-obtain the Cartesian bit-wise join of $H_A$ and $H_B$, we must restrict to the diagonal edges $(e,e) \in E(H_A) \times E(H_B) = [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H_A$ and $H_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are searching for hypergraphs $H_A$ and $H_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.

The resulting reformualtion.

From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:

Is an edge-labelled hypergraph $H_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (i.e. taking only the diagonally labelled edges) of the tensor product $H_A \otimes H_B$ of two labelled hypergraphs $H_A$ and $H_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?

I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.

Answer 2

This problem is very similar to dominating set in bipartite graphs. Indeed, whenever $a_i \lor b_j = 0$, we know that $a_i = b_j = 0$. Remove all these inputs and constraints. Now we are left with sets $A',B'$ and edges containing vertices in $A'$ to vertices in $B'$. Any solution to this system of equations corresponds to a dominating set in this bipartite graph.

Finding a solution of minimal Hamming weight is the same as solving minimum dominating set, which is known to be NP-hard even for planar bipartite graphs of maximum degree 3, as shown by Jukka Suomela in this very site.