3
$\begingroup$

(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''$.
$\endgroup$
  • 1
    $\begingroup$ Why is $|C| = |A| \cdot |B|$ ? I can see $\le$, but not $=$. In other words, are the sizes of the desired $A, B$ also given ? $\endgroup$ – Suresh Venkat Oct 15 '12 at 22:31
  • 1
    $\begingroup$ @Suresh $|C| = |A| \cdot |B|$ by definition. The (formal) sets $A$,$B$ are known in advance. Here $|\cdot|$ is not Hamming weight, just length. $\endgroup$ – Yuval Filmus Oct 15 '12 at 22:45
  • 1
    $\begingroup$ what about the fact that there is always a trivial solution or that the solution is not unique? $\endgroup$ – Sasho Nikolov Oct 16 '12 at 3:49
  • 7
    $\begingroup$ i ventured to clarify, hope i kept the original intention. i would not normally do such a thorough re-edit, but vzn is not usually one to respond to requests for edits. $\endgroup$ – Sasho Nikolov Oct 16 '12 at 16:45
  • 2
    $\begingroup$ ... Repeating a (now deleted because of meta-discussion) comment — what are these deep proofs in complexity theory where you find that this operation occurs? Assuming my understanding of your problem is correct, it doesn't surprise me that it may play a role in some proofs, as outer products are a natural operation; but it would be nice to know your motivations for this problem, unless it is essentially an exercise in pure algebraic logic. $\endgroup$ – Niel de Beaudrap Oct 17 '12 at 18:32
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 for considering the dual hypergraph which was just musing minutes ago might work & looks promising, am suspecting might make the hypergraph product theory (some good refs on that) relevant. found suresh's ref to the dual hypergraph based on reading your Q/A list & your question on hypergraph coloring. hope to have more comments after further review.... $\endgroup$ – vzn Oct 17 '12 at 18:53
  • $\begingroup$ still have to dig into this but this is a ref turned up on hypergraph products earlier (before posting question) which has a somewhat new yet somewhat fleshed out theory incl a prime factorization thm! what do you think, does any of this fit? hypergraph products by gringmann .. note in all cases (there are a bunch) it uses a cartesian product of vertex sets. $\endgroup$ – vzn Oct 17 '12 at 20:58
  • 1
    $\begingroup$ @vzn: I think that in just about any (hyper)graph product of note, the vertex set will be the cartesian product of the vertex sets of the factors; that was my motivation for considering the dual hypergraph originally. As to unique "prime" factorization, I think you must look for products which lack that property, as the Cartesian bitwise meet/join certainly lack it. (Consider $A_1 = \{110,001\}$ and $B_1 = \{011,101\}$ versus $A_2 = \{111,000\}$ and $B_2 = \{011,101\}$; both yield a join of $$C = \begin{bmatrix} 111 & 111 \\ 011 & 101 \end{bmatrix}$$ expressed as an outer product.) $\endgroup$ – Niel de Beaudrap Oct 17 '12 at 21:35
  • $\begingroup$ as written on your now-deleted answer, am actually interested in the question/case of $C$ that are provably "prime" wrt factorization. conjecture that "important" $C$ exist that are "prime" wrt "cartesian bitwise join" factoring $\endgroup$ – vzn Oct 17 '12 at 22:47
  • $\begingroup$ My post didn't provide any sort of uniqueness guarantees. To "factor" the matrix $C$ in my previous comment, one would take as factors the bit-wise AND across the rows and columns, obtaining $A = \{111,001\}$ and $B = \{011, 101\}$, which you might notice is yet a third factorization. (I expect that it is an accident of the example that I've chosen that the row-vector factor is the same in each one.) And this is just with a single mapping of elements to coefficients; for larger $C$ there may be feasible factorizations for different mappings. It's not clear that you can prevent this in any way. $\endgroup$ – Niel de Beaudrap Oct 18 '12 at 0:34
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thx but dont follow & think it might not fit; your comment above is not correct, didnt mean $|\cdot|$ as length of the bitvector but as size of the bitvector set (number of bitvectors in the set). $C$ is given but not $A,B$. if you think this is right can you sketch out how this applies for a given $C$? am not saying my problem statement is free of ambiguity, there might be a clearer way to state it.... $\endgroup$ – vzn Oct 15 '12 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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