Efficient Approximation for Restricted Biclique Cover Problems

Abstract

Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless $P=NP$, the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph $G=(L,R,E)$, where each node in L is assigned to an arbitrary subset of up to a constant f factors, while the nodes in R (the independent observations) are assigned to random subsets of the set of k factors where k can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations.

1. Introduction

We study the approximability of two variants of the minimum biclique cover problem, motivated by the problem of characterizing parsimonious models in computational biology settings.

Given a bipartite graph $G=(L,R,E)$, a biclique in G is a set of edges $H\subseteq E$ that induces a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques that cover all the edges of G. The biclique cover number or the biclique dimension of G is the minimum number of bicliques that cover E.

Covering a bipartite graph with a minimum number of bicliques is a fundamental graph theory problem that has received significant attention in theoretical computer science [1,2,3,4,5,6]. The computational problem has numerous applications, ranging from computational biology [7,8,9], data mining [10], and  machine learning [11], to automata theory [4], communication complexity [6], and graph drawing [12].

The problem of determining whether a bipartite graph G has a biclique cover of size k is known to be $\mathrm{NP}$-Complete even if the graph is a chordal bipartite graph [5,13]. Chalermsook et al. [1] recently showed that the biclique cover problem is also not approximable in polynomial time to less than an $O(|V{|}^{1-ϵ})$ or $O(|E{|}^{1/2-ϵ})$ factor for any $ϵ>0$ unless $P=NP$. This improved previous inapproximability results [3,4]. Moreover, unless $\mathrm{NP}\subseteq \mathrm{BPTIME}\left(2^{\mathrm{poly}(log(n\left)\right)}\right)$, there are also no polynomial time $O\left(\frac{|V|}{2^{{log}^{7/8+ϵ}(|V|)}}\right)$ or $O\left(\frac{\sqrt{|E|}}{2^{{log}^{7/8+ϵ}(|V|)}}\right)$ approximation algorithms [1]. These results are almost tight in terms of lower-order factors of $|V|$ as an $O\left(min(\frac{|V|}{\sqrt{log(|V|)}},|E|\frac{{(log(log(|E|))}^2}{{log}^3(|E|)})\right)$ approximation algorithm is known [1].

Given these strong impossibility results, theoretical work has focused on developing polynomial time solutions for specific graph subclasses, such as C4-free graph [13], and domino-free graphs [14]. Another line of research developed parametrized complexity results, showing that it is possible to determine in time $O\left(f\right(k\left)\mathrm{poly}\right(n\left)\right)$ whether a bipartite graph G admits a cover with at most k bicliques [2,7] where $f\left(k\right)$ is an exponential function of k, but it does not depend on n. Other work has focused on the version of the problem where bicliques are edge-disjoint or vertex-disjoint [1,2]. Dawande et al. [15] studied the size of maximum cardinality of bicliques in random bipartite graph. The related problem of clique cover in non-bipartite graphs has also received significant attention [5].

Finally, a problem related to our work here, is the local biclique cover problem [16], where for a given (not necessarily bipartite) graph G and a parameter f we want to determine whether there exists a biclique cover of the edges of G (using an arbitrary number of bicliques) in which each node belongs to at most f bicliques. Arora et al. [17] studied a generalization of clique cover with applications to community detection where nodes are limited to participate in a few cliques.

We note that the biclique cover problem is equivalent to the binary matrix factorization problem [10], where the goal is to decompose an $n\times m$ binary matrix A into a product of $n\times k$ and $k\times m$ binary matrices. The minimum k for which such a decomposition exists, known as the Boolean rank of A, equals the minimum biclique cover number of a bipartite graph G with adjacency matrix A. Biclique cover can also be seen as a form of biclustering [18].

Motivation

The two restricted biclique cover problems studied here are motivated by the application of minimum biclique cover to the fundamental inference problem of characterizing parsimonious models. We present combinatorial abstractions of two computational biology problems that motivates this work [7,8,9] . We note that similar applications are found in other fields  [10].

The goal of HLA (human leukecyte antigen) serology studies [9] is to identify antigens responsible for acceptance and rejections of transplanted tissues. For the combinatorial model, it is sufficient to know that an implant is rejected if it has an antigen that has a specificity in common with some antibody in the recipient serum. Thus, a donor and recipient are not compatible if the donor has an antigen that has specificity in common with at least one of the recipient antibodies. Given a set of donors and recipients, we construct a bipartite graph $G=(L,R,E)$, where L is the set of donors, R  is the set of recipients, and $v\in L$ is connected with $u\in R$ if v and u are not compatible. The goal is to determine the minimum number of (antigens, antibodies) pairs with common specificity that explains the observed compatibility structure between the sets of donors and recipients. It is easy to verify that a (antigens, antibodies) pair with common specificity defines a biclique in the graph G and therefore the minimum number of bicliques corresponds to the minimum number of pairs that explain the observed data.

A second problem is the Mod-Resc Parsimony Inference problem [7]. Here, the bipartite graph $G=(L,R,E)$ represents reproductive incompatibility between strains of male L, and female R insects. An edge $(u,v)$ indicates that a cross between $u\in L$ and $v\in R$ is incompatible. The biology model postulates that incompatibility is a result of a bacteria (mod-factor) in the male sperm and a lack of the corresponding (resc-factor) in the female. The goal is to find the minimum number of (mod, resc) factor pairs that explains the data. Since the edges of the graph correspond to incompatible pairs, it is easy to verify that a biclique corresponds to a factor, and a minimum biclique cover gives a parsimonious  model.

In these two applications, it is reasonable to assume that the total number of different factors (antigens or bacteria) is growing with the size of the sample. Thus, a parameterized solution, exponential in the total number of bicliques, is not practical. On the other hand, it is reasonable to assume that the number of different antigens or antibodies of a given person, or the number of different bacteria infecting one insect, is not a function of the total sample size. Furthermore, in  particular in the Mod-Resc model, evaluation considerations imply that the number of factors per sample must be very small, justifying the first restricted model we study here.This is also consistent with the observation in [8] that in their data for a weighted version of the biclique cover problem each node was covered by at most 2 weighted bicliques.

A second characteristic of the observed data is that it corresponds to independent samples. To  incorporate the effect of random samples, we distinguish between two cases. Two factors can be highly correlated. For example, in the case of HLA serology, two antigens may appear together in donors and their corresponding antibodies may appear together in recipients. In that case we cannot distinguish between the two factors, as they correspond to the same biclique. Otherwise, we can assume that appearances of factors are relatively independent in at least one of the two sets of nodes. This observation motivates the second, stochastic model we study here.

2. Overview of New Results

Motivated by the above applications, we study two variations of the biclique cover problem. We  present almost tight positive and negative results for each of the variants.

2.1. Model I: A Node belongs to a Small Number of Bicliques

In this model, we consider bipartite graphs with minimum biclique covers in which each node participates in only a small number of different bicliques. More formally, we introduce the $(f_L,f_R,k)$-biclique cover decision problem for bipartite graphs:

Problem 1

($(f_L,f_R,k)$-biclique cover problem). Given a bipartite graph $G=(L,R,E)$, and parameters $f_L,f_R$ and k, distinguish between the following two cases:

Yes-instance: There is a biclique cover of G with $\le k$ bicliques, such that $\forall u\in L$ (resp. $v\in R$), u belongs to at most $f_L$ distinct bicliques in the cover (resp. v belongs to at most $f_R$ distinct bicliques in the cover).

No-instance: No such cover exists.

When $f_L=f_R=f$, we write $(f,k)$-biclique cover instead of $(f,f,k)$-biclique cover.

Notice that this problem is related to the local biclique cover problem where one is only interested in minimizing the number of distinct bicliques covering each node without minimizing the total number of bicliques [16]. Clearly, if a graph satisfies the $(f_L,f_R,k)$-biclique cover condition it also satisfies the $(max(f_L,f_R))$-local biclique cover condition, but the converse is not always true.

Results 1.

Our first result (Section 3.3) shows that the $(f,k)$-biclique problem remains computationally hard even for small values of f. Specifically, we prove that the $(f,k)$-biclique problem is NP-Complete for any $f\ge 5$.

On the positive side, we first note that the $(1,k)$-biclique case is trivial since the graph must consist of disjoint bicliques. We present two results for the non-trivial $(2,k)$-biclique case. (1) For any graph with a $(2,k)$-biclique cover, we present a polynomial time algorithm that finds a biclique cover with at most $\approx 2.83k$ bicliques. (2) For any graph with a $(2,k)$-biclique cover, we present a polynomial time algorithm that covers at least a $1-\frac{1}{e}$ fraction of the edges of the graph with k bicliques. These algorithms do not guarantee that each node is covered by at most 2 bicliques.

2.2. Model II: A One-Side Stochastic Model

In this model, we capture the fact that nodes represent independent observations, but the bipartite graph has more structure than a standard random bipartite graph. This structure is dictated by the semi-random assignment of factors to nodes.

Formally, we define the $(f,\overline{p},k)$-biclique cover problem, for a constant f, a vector of k probabilities $\overline{p}$, and an arbitrary large number of factors k. An input to the $(f,\overline{p},k)$-biclique cover problem is a bipartite graph $G=(L,R,E)$ generated by the following process: Factors are assigned arbitrarily to nodes in L, subject to a limit of f factors per node. Nodes in R are assigned factors by a random process in which each node is assigned factor i with probability $p_i$, independent of any other choice. A node $u\in L$ and a node $v\in R$ are connected if they share a factor. Given the observed graph $G=(L,R,E)$, and the parameters f, $\overline{p}$ and k, we want to find a k-biclique cover of the graph.

Results 2.

We show that for an arbitrary large constant f, and under some simple conditions on the distribution $\overline{p}$, there is a $O\left(\right(|L|+{|R|)}^{O\left(1\right)})$ time algorithm that w.h.p. obtains a k-biclique cover of the graph, as long as $|R|\ge clog(|L|)$ for some large enough constant $c>0$. Here, the $O\left(1\right)$ depends only on the constant f.

For an arbitrary probability vector $\overline{p}$, we present an algorithm that in $O\left(\right(|L|+{|R|)}^{O\left(1\right)})$ time with high probability finds a set of bicliques of size k covering at least a $1-\frac{1}{e}$ fraction of the edges, or $O(klog(|R|\left)\right)$ bicliques covering all edges of G, as long as $|R|\ge clog(|L|)$ for some large enough constant $c>0$. Here, the $O\left(1\right)$ depends on the distribution $\overline{p}$ and f but not on the size of the graph.

3. Model I: $(f,k)$-Biclique Cover

In this section, we study the $(f,k)$-biclique problem introduced. For the rest of the paper we use $N\left(u\right)$ to indicate the neighborhood of any node $u\in L\cup R$. Also, we represent (bipartite) subgraphs of G with capital letters, and we use $A=(L_A,R_A)$ to indicate that subgraph A has nodes $L_A$ (resp. $R_A$) in the left (resp. right) side of the graph.

3.1. $(1,k)$-Biclique Cover

First, we observe that the $(1,k)$-biclique problem can be trivially solved in polynomial time.

Lemma 1.

A bipartite graph $G=(L,R,E)$ can be covered with a $(1,k)$-biclique cover iff it has $\le k$ connected components and each of them is a biclique.

Proof. 

Suppose each connected component of G is a biclique. It is easy to see that then all edges can be covered by using each connected component as the biclique in the cover. Also, each node is covered by a single biclique.

Then, assume G is a yes-instance. Let $B_1,\dots B_t$, be the set of bicliques covering all the edges of G, in the solution. Notice that the bicliques define a partition of the nodes in G as each node can belong to a single biclique. We show that there is no edge that connects two nodes in two distinct bicliques, and  hence the graph consists of $t\le k$ connected components, each a complete subgraph. Suppose to get a contradiction that $(u,v)\in E$ is an edge connecting the nodes in $B_i,B_j$ for $i\ne j$. Since $(u,v)$ does not belong to any of the two bicliques, the edge must be covered by a third biclique. However, all edges of u are covered by a single biclique. ☐

This condition can be easily checked in polynomial time.

3.2. Results for the $(2,k)$-Biclique Cover

In this section, we assume that we are given in input a bipartite graph $G=(L,R,E)$ and a parameter k such that G is a yes-instance of the $(2,k)$-biclique cover problem. Our goal it to compute approximate solution to the following two optimization problems: covering all edges of G with as few bicliques as possible and covering as many edges of G as possible with k bicliques. We denote the union of the sets of node by $V=L\cup R$.

3.2.1. Maximize Edge Coverage with k Bicliques

We prove the following result:

Theorem 1.

There exists a $O\left(min\left({|V|}^3+k^{15}{|E|,k|V|}^7|E|\right)\right)$ time algorithm that given in input a bipartite graph $G=(L,R,E)$ and a parameter k, where G is a yes-instance of the $(2,k)$-biclique cover problem, it outputs a set of at most k bicliques in G covering at least $(1-\frac{1}{e})|E|$ edges of G.

We first provide an overview of the main ideas on which Algorithm 1, which maximizes the number of edges covered with k bicliques, is based. The algorithm has four steps. First, we use a kernelization method to obtain a smaller graph $G^{\prime }$ which has a $(2,k)$-biclique cover iff G has a $(2,k)$-biclique cover. Then, we exploit the properties of the $(2,k)$-biclique covers for the kernelized graph $G^{\prime }$ to identify a set ${\mathcal{B}}^{\prime }$ of all large enough bicliques that are part of any cover of $G^{\prime }$. Then, we  will show how to enumerate the set ${\mathcal{C}}^{\prime }$ containing all possible small bicliques of any cover of $G^{\prime }$ not in ${\mathcal{B}}^{\prime }$. We will keep a mapping from bicliques in the smaller graph $G^{\prime }$ to bicliques in the original graph G. Then, we cast the problem of selecting $\le k$ bicliques as a monotone submodular maximization problem hence showing that we can cover at least $(1-\frac{1}{e})|E|$ edges of the original graph G with k bicliques.

We now prove formally Theorem 1, showing an algorithm that outputs a set of at most k bicliques in G covering at least $(1-\frac{1}{e})|E|$ edges of G. We describe each step of Algorithm 1 in details.

• Step 1: Kernelization.

We apply the kernelization technique introduced by Fleischner et al. [2] for showing the parametrized complexity of biclique cover, which we now recall.

Given an instance $(G,k)$ of biclique cover, the kernelization obtains an instance $(G^{\prime },k)$ where $G^{\prime }$ is constructed by applying the following two rules to G: (1) remove all nodes from G with no neighbors; (2) for each set of vertices that have the same neighborhood in G, keep only one of them. We call $G^{\prime }$ the kernelized graph of G if $G^{\prime }$ is constructed from G by applying the two rules. Fleischner et al. [2] show that G admits a k-biclique cover iff $G^{\prime }$ admits a k-biclique cover. We now show that using the same kernelization, G admits a $(f_L,f_R,k)$-biclique cover iff $G^{\prime }$ admits a $(f_L,f_R,k)$-biclique cover.

Lemma 2.

$G=(L,R,E)$ is a yes-instance of the $(f_L,f_R,k)$-biclique cover problem iff the kernelized graph $G^{\prime }=(L^{\prime },R^{\prime },E^{\prime })$ of G is a yes-instance of the $(f_L,f_R,k)$-biclique cover problem.

Proof. 

The lemma is a corollary of the results for general kernelization of biclique cover [2,7].

Notice that nodes with no neighbors can be ignored without complications. We show that one application of the rule that removes one node u if another node v has the same neighborhood transforms yes-instances into yes-instances and no-instances to no-instance. The result will follow then by induction (over the number of application of the rule). Let $G^{\prime }$ be the graph obtained by removing $v\in L$ from G when there is a $v\ne u\in L$ s.t. $N\left(u\right)=N\left(v\right)$ (the case with $v\in R$ is similar and omitted).

Consider a $(f_L,f_R,k)$-biclique cover of G. Removing a node v from G and from all the bicliques involving v gives a graph that can be covered with $\le k$ bicliques each covering at most $f_L$ nodes on the left side and $f_R$ on the right side.

Consider a $(f_L,f_R,k)$-biclique cover of $G^{\prime }$. As node u has the same neighbors of v, we can extend each of the (at most $f_L$ bicliques) covering u to include v on the left side. This preserves the fact that they are bicliques. Also v is covered by at most $f_L$ bicliques, and in total we use k bicliques. The nodes on the right side are still covered by the same number of bicliques. ☐

The algorithm first applies the kernelization to obtain the bipartite graph $G^{\prime }=(L^{\prime },R^{\prime },E^{\prime })$. This  can be done in time $O(|V{|}^3)$. We define $V^{\prime }=L^{\prime }\cup R^{\prime }$. We will store a mapping $\mathtt{kern}:V^{\prime }\to 2^V$ that records for each node in $v\in V^{\prime }$ the set $\mathtt{kern}\left(v\right)$ of nodes in V that had the same neighborhood and of which v is the only node left in $G^{\prime }$ – i.e., $\mathtt{kern}\left(v\right)$ is an equivalence class of the nodes with the same neighborhood. Notice that for each node $v\in V^{\prime }$, $\mathtt{kern}\left(v\right)$ contains at least one node and that all nodes in G with non-zero degree are in a unique $\mathtt{kern}\left(v\right)$ set.

Algorithm 1 ApproxMaxCover($G=(L,R,E),k$)

Assumes G is a yes-instance for $(2,k)$-biclique cover.  — Step 1 —  Let $G^{\prime }=(L^{\prime },R^{\prime },E^{\prime })$ be the graph obtained applying the Fleischner et al. [2] kernelization.  Store  mapping $\mathtt{kern}$.  Let $V^{\prime }=L^{\prime }\cup R^{\prime }$  if $|V^{\prime }|\ge 2k^2$ then      report no $(2,k)$-biclique cover exists for G and quit.  end if  — Step 2 —  Let ${\mathcal{B}}^{\prime }\leftarrow \varnothing$.  For all $A\subseteq V^{\prime }$ such that $G\left[A\right]=K_{3,4}$ or $G\left[A\right]=K_{4,3}$. Let $A_L=A\cap L^{\prime }$ and $A_R=A\cap R^{\prime }$ Let $A_L\leftarrow {\bigcap }_{v\in A_R}N\left(v\right)$ Let $A_R\leftarrow {\bigcap }_{v\in A_L}N\left(v\right)$ Let $A^{\prime }=(A_L,A_R)$ and add biclique $A^{\prime }$ to the set ${\mathcal{B}}^{\prime }$  if $|{\mathcal{B}}^{\prime }|\ge k$ then      report no $(2,k)$-biclique cover exists for G and quit.  end if  — Step 3 —  Let ${\mathcal{C}}^{\prime }$ be the set containing all bicliques of $G^{\prime }$ of the form: All the bicliques $\left(\right\{u\}$,$N\left(u\right))$ for $u\in L^{\prime }$ or $\left(N\right(u),\{u\left\}\right)$ for $u\in R^{\prime }$ All the bicliques ($\{u,v\}$, $N\left(u\right)\cap N\left(v\right)$) for $u,v\in L^{\prime }$ or $\left(N\right(u)\cap N(v),\{u,v\left\}\right)$ for $u,v\in R^{\prime }$ And all the $K_{3,3}$ in $G^{\prime }$.  — Step 4 —  Let $\mathcal{B}=\{\mathtt{kern}\left(B^{\prime }\right)|B^{\prime }\in {\mathcal{B}}^{\prime }\}$.  Let $\mathcal{C}=\{\mathtt{kern}\left(C^{\prime }\right)|C^{\prime }\in {\mathcal{C}}^{\prime }\}$.  Let $\mathcal{O}=\mathcal{B}$.  while $|\mathcal{O}|<k$ do      Select $C\in \mathcal{C}$ s.t. the number of edges covered in G by the union of the bicliques in $\mathcal{O}\cup \left\{C\right\}$ is maximized.      Add C to $\mathcal{O}$.  end while  return$\mathcal{O}$.

First, notice that given a biclique $B^{\prime }=(B_L^{\prime },B_R^{\prime })$ of $G^{\prime }$, we can construct a biclique $B=(B_L,B_R)$ of G using the mapping $\mathtt{kern}$: $B_L={\bigcup }_{v\in B_L^{\prime }}\mathtt{kern}\left(v\right)$ and $B_R={\bigcup }_{v\in B_R^{\prime }}\mathtt{kern}\left(v\right)$. It is possible to observe that $(B_L,B_R)$ is a biclique in G if $(B_L^{\prime },B_R^{\prime })$ is a biclique in $G^{\prime }$. Given a biclique $B^{\prime }$ in $G^{\prime }$, we write $\mathtt{kern}\left(B^{\prime }\right)$ for the biclique B in $G^{\prime }$ obtained in this way.

The following properties of the kernelized graph $G^{\prime }$ of G will be exploited in the rest of the paper.

Lemma 3.

Let $G=(L,R,E)$ be a yes-instance of the $(2,k)$-biclique cover problem and let $G^{\prime }=(L^{\prime },R^{\prime },E^{\prime })$ be the kernelized version of the graph G. Then the following statements are true:

• $G^{\prime }$ admits a $(2,k)$-biclique cover.
• $|L^{\prime }\cup R^{\prime }|\le O\left(k^2\right)$.
• In any $(2,k)$-biclique cover of $G^{\prime }$ there are no two nodes on the same side of the graph covered by the exact same set of bicliques.

Proof. 

The first statement is a corollary of Lemma 2. Notice that all nodes on the same side of $G^{\prime }$, by construction, have distinct neighborhoods. Hence, they cannot be covered by the same set of 2 bicliques in any $(2,k)$-biclique cover. Finally, since each node in one side is covered by distinct subsets of at most 2 bicliques out of k, there are at most $2k^2=O\left(k^2\right)$ nodes in $G^{\prime }$. ☐

• Step 2: Identifying Large Bicliques in the Cover.

We call $K_{l,r}$ biclique any biclique that has exactly l nodes in the left side of the bipartite graph and exactly r nodes in the right side. For a graph G and a set of vertices A, we call $G\left[A\right]$ the induced subgraph containing all nodes A and the edges between them.

We will also use the following notation. Given a $(2,k)$-biclique cover $\mathcal{B}$ of the graph G, where $\mathcal{B}$ is a set of bicliques covering all the edges of G, we define $F_{\mathcal{B}}\left(u\right)$ as the set of bicliques covering the node u in the cover $\mathcal{B}$. We have $1\le |F_{\mathcal{B}}\left(u\right)|\le 2$. We will omit $\mathcal{B}$ from $F(·)$ when it is clear which cover we are discussing.

We now make a series of important observations for the structure of the $(2,k)$-biclique cover of the kernelized graph $G^{\prime }$ of a $(2,k)$-biclique cover yes-instance G.

Lemma 4.

Let G be a yes-instance for the $(2,k)$-biclique cover problem and let $G^{\prime }$ be the kernelized graph of G. Suppose $A\subseteq L^{\prime }$ (resp. $A\subseteq R^{\prime }$) is such that $|A|\ge 3$. Let $\mathcal{B}$ be a $(2,k)$-biclique cover of $G^{\prime }$. If there is a single biclique $B\in \mathcal{B}$ that covers all the nodes in A, then, in the cover $\mathcal{B}$, all nodes $S\subseteq R^{\prime }$ ($S\subseteq L^{\prime }$) connected to all nodes in A are covered by the same biclique B.

Proof. 

Fix a solution $\mathcal{B}$ of the $(2,k)$-biclique cover of $G^{\prime }$. Let B be the biclique that covers all nodes in A in the solution $\mathcal{B}$. We prove the case for $A\subseteq L^{\prime }$, the other case is similar.

First, fix three distinct nodes $a_1,a_2,a_3$ in A. All the nodes are covered by biclique B. Notice that by the third item of Lemma 3, each node in A is covered by a different set of (at most 2) bicliques in $\mathcal{B}$. Hence, there is no other single biclique $B^{\prime }$ that covers two nodes in A (otherwise there will be two nodes both covered by the pair $B,B^{\prime }$ of bicliques).

Now consider a node $v\in R^{\prime }$ connected to all nodes in A. If v is not part of biclique B, in the biclique cover $\mathcal{B}$, all the edges $(a_i,v)\in E$ for $i\in \left[3\right]$ are covered by a distinct biclique. This is a contradiction, as v is covered by at most 2 bicliques in $\mathcal{B}$. ☐

We use the previous lemma to prove the following useful result.

Lemma 5.

Let $G^{\prime }=(L^{\prime },R^{\prime },E^{\prime })$ be the kernelized graph of a $(2,k)$-biclique cover yes-instance G. Suppose that $A\subseteq L^{\prime }\cup R^{\prime }$ is such that $G^{\prime }\left[A\right]$ is a $K_{3,4}$ biclique (or a $K_{4,3}$ biclique). Let $A_L=A\cap L^{\prime }$ and $A_R=A\cap R^{\prime }$. Let $A_L^{\prime }={\bigcap }_{v\in A_R}N\left(v\right)$ and let $A_R^{\prime }={\bigcap }_{v\in A_L^{\prime }}N\left(v\right)$. Then the biclique $A^{\prime }=(A_L^{\prime },A_R^{\prime })$ is part of any$(2,k)$-biclique cover of $G^{\prime }$ and it is the unique biclique that covers all nodes in A.

Proof. 

Suppose to get a contradiction that in a given $(2,k)$-biclique cover $\mathcal{B}$ of $G^{\prime }$ there is no such unique biclique $A^{\prime }$ covering all nodes in A. From now on in this proof, when we use $F\left(u\right)$, we refer to $F_{\mathcal{B}}\left(u\right)$, i.e., the set of bicliques covering u in the cover $\mathcal{B}$.

W.l.o.g., we assume that $|A_L|=3$ and $|A_R|=4$. The proof follows similarly in the opposite case.

Notice that if any set of at least 3 nodes in either side of A is covered by the same biclique $B\in \mathcal{B}$ then, B covers all nodes in A. This is because, by Lemma 4, if three nodes in side $L^{\prime }$ in A (resp. $R^{\prime }$) are covered by B then all nodes in side $R^{\prime }$ in A (resp. $L^{\prime }$) are covered by B, and this implies that the all nodes in side $L^{\prime }$ (resp. $R^{\prime }$) are covered by B.

Consider any node $u\in A$. If $|F(u)|=1$, than there is a contradiction. In fact, all neighbors of u are covered by a single biclique and hence we get that more than 3 on one side are covered by the same biclique. By the previous argument than there is a biclique covering all nodes in A. So we assume for the rest of the proof that $|F(u)|=2$ for all nodes $u\in A$. Fix a node u in $A\cap L^{\prime }$ and let $B_1,B_2$ be the two distinct bicliques covering the node u in $\mathcal{B}$. All nodes in $A\cap R^{\prime }$ are covered by either $B_1$ or $B_2$.

We now show that there is no node $v\in A\cap R^{\prime }$ such that $F\left(v\right)=\{B_1,B_2\}$. In fact, if such a node exists, then there are no assignments of $B_1$ and $B_2$ to nodes in $A\cap R^{\prime }$ such that all nodes in $A\cap R^{\prime }$ belong to one of the two bicliques but no bicliques covers 3 nodes in $A\cap R^{\prime }$ (recall that if a biclique covers 3 nodes in $A\cap R^{\prime }$ we get a contradiction because then all nodes in $A\cap L^{\prime }$ are covered by the same biclique and hence the fourth node in $A\cap R^{\prime }$ is covered as well by that biclique). Also similarly, this implies that $B_1$ and $B_2$ both cover exactly two distinct nodes $A\cap R^{\prime }$. Let $r_1,\dots r_4\in A\cap R^{\prime }$. W.l.o.g., we assume that $F\left(r_1\right)=\{B_1,C_1\}$ and $F\left(r_2\right)=\{B_1,C_2\}$, $F\left(r_3\right)=\{B_2,D_1\}$ and $F\left(r_4\right)=\{B_2,D_2\}$ where by kernelization we have $C_1\ne C_2$ and $D_1\ne D_2$.

Now, we have that all nodes in $A\cap L^{\prime }\backslash \left\{u\right\}$ do not belong to both $B_1$ and $B_2$. For sake of contradiction, let, w.l.o.g., $v\in A\cap L\backslash \left\{u\right\}$ be a node that belongs to $B_1$. We know that v does not belong to $B_2$ (by kernelization). So $\{B_1,D_1,D_2\}\subseteq F\left(v\right)$, as it is connected to $r_3,r_4$ and hence $F\left(v\right)>2$, giving a contradiction.

This implies, for any node $v\in A\cap L^{\prime }\backslash \left\{u\right\}$ to be connected to all nodes in $A\cap R^{\prime }$, that the following conditions are met: $\{C_1,C_2\}=\{D_1,D_2\}$ and $F\left(v\right)=\{C_1,C_2\}$. By kernelization, this gives a contradiction, as two distinct nodes in $A\cap L^{\prime }\backslash \left\{u\right\}$ belong to the same set of bicliques.

We have shown that in any $(2,k)$-biclique cover $\mathcal{B}$ of $G^{\prime }$ there is at least one biclique $A^{\prime }$ covering all nodes in A. Now notice that there can be only one biclique covering all nodes in A, as otherwise there will be two nodes with the same set of bicliques in the cover on the same side of the graph. Hence, $A^{\prime }$ is the unique biclique covering all nodes in A in any $(2,k)$-biclique cover. Finally, by applying Lemma 4 to all nodes connected to each node in $A\cap L^{\prime }$ (resp. $A\cap R^{\prime }$), we know that the unique biclique $A^{\prime }$ is $(A_L^{\prime },A_R^{\prime })$, as in the statement of the lemma. ☐

The previous lemma means that if A is a $K_{3,4}$ (or $K_{4,3}$) of $G^{\prime }$ then the biclique $A^{\prime }$ obtained as in the statement is part of any optimal solution. Also notice that clearly if in a given $(2,k)$-biclique cover of $G^{\prime }$ there is a biclique of size at least 3 in the smallest side, and at least 4 in the largest side, this biclique induces a $K_{3,4}$ (or $K_{4,3}$) in $G^{\prime }$.

Hence, by enumerating all $K_{3,4}$ and $K_{4,3}$ in $G^{\prime }$ in polynomial time we can find a set ${\mathcal{B}}^{\prime }$ of bicliques in $G^{\prime }$ such that: ${\mathcal{B}}^{\prime }$ contains all large enough bicliques—i.e., with $\ge 3$ nodes (resp. $\ge 4$) in the smaller (resp. larger) side that are part of all $(2,k)$-covers of $G^{\prime }$; and no biclique not in ${\mathcal{B}}^{\prime }$ which is large enough (again it contains a $K_{3,4}$ or a $K_{4,3}$) is part of any $(2,k)$-biclique cover. This is done in Step 2 of Algorithm 1.

• Step 3: Small Bicliques

We know that all the bicliques necessary to cover the remaining edges of $G^{\prime }$ (besides the one in ${\mathcal{B}}^{\prime }$) need to involve at most 3 nodes in the smaller side. We can then enumerate a set ${\mathcal{C}}^{\prime }$ of bicliques, in  polynomial time, containing a super-graph of each biclique not in ${\mathcal{B}}^{\prime }$ that is part of any $(2,k)$-biclique cover. It is possible to verify that at the end of Step 3 of the algorithm, ${\mathcal{C}}^{\prime }$ contains at least one biclique that covers all edges of any biclique with at most 3 nodes in the smallest side of the biclique. Step 3 runs in polynomial time.

• Step 4: Max Coverage

Finally, we have a set ${\mathcal{B}}^{\prime }$, which contains bicliques that are necessary part of any optimal solution of $G^{\prime }$ and a set ${\mathcal{C}}^{\prime }$ of bicliques $G^{\prime }$ that are sufficient to cover all edges of $G^{\prime }$ not covered by bicliques in ${\mathcal{B}}^{\prime }$.

Let $\mathcal{B}$ be the set of bicliques of G obtained by $\mathcal{B}=\{\mathtt{kern}\left(B^{\prime }\right)|B^{\prime }\in {\mathcal{B}}^{\prime }\}$ (recall the definition of the mapping). Similarly we obtain the set $\mathcal{C}$ from ${\mathcal{C}}^{\prime }$.

The algorithm will output all the bicliques in $\mathcal{B}$. For $t=|\mathcal{B}|\le k$ the algorithm will obtain the remaining $k^{\prime }=k-t$ bicliques in the following way. First, let $\mathcal{O}=\mathcal{B}$. The algorithm will add greedily a single biclique from $\mathcal{C}$ to $\mathcal{O}$ for $k^{\prime }$ times choosing each time the biclique that maximizes the number of newly covered edges in $G^{\prime }$. It is easy to see that, since this function is monotone submodular and $k^{\prime }$ additional bicliques are sufficient to cover all edges not covered by $\mathcal{B}$, at least $(1-\frac{1}{e})|E|$ of the edges of G are covered at the end of the process. We can now complete the proof of Theorem 1.

Proof of Theorem 1.

Notice that by the previous considerations, the set $\mathcal{O}$ at the end of Algorithm 1 contains at most k bicliques, and these bicliques covers $(1-\frac{1}{e})|E|$ edges of G.

The algorithm requires $O(|V{|}^3)$ time for the kernelization. Then, the remaining graph $G^{\prime }$ has at most $n=min(2k^2,|V|)$ nodes and at most $m=min(4k^4,k|E|)$ edges, by Lemma 3.

The most expensive operation is enumerating all the $K_{3,4}$, $K_{4,3}$ of the graph which can be done in $O\left(n^7\right)$ time. Hence, Step 2 takes $O\left(n^{7}m\right)$ time.

Step 3 takes at most $O\left(n^6\right)$ time.

Finally, Step 4 does at most k iterations over a set of size $O\left(n^6\right)$ each step of the iteration taking at most $O(|E|)$ time.

The total is hence $O(|V{|}^3+k{n}^7|E|)$, and the result follows. ☐

3.2.2. Covering All Edges with the Minimum Number of Bicliques

In this section we prove Theorem 2, the existence of an algorithm that outputs a set of at most $H\left(9\right)k$ bicliques covering all edges of the graph.

Theorem 2.

There exists a $O\left(min\left({|V|}^3+k^{15}{|E|,k|V|}^7|E|\right)\right)$ time algorithm that given in input a bipartite graph $G=(L,R,E)$ and a parameter k, where G is a yes-instance of the $(2,k)$-biclique cover problem, outputs: a set of at most $H\left(9\right)k$ bicliques in G covering all edges of G.

Here, $H\left(i\right)={\sum }_{1\le j\le i}{j}^{-1}$ is the i-th harmonic number and $H\left(9\right)\approx 2.83$.

For this problem, we use similar techniques described before. We outline the main differences from Algorithm 1. As before, we will construct the set ${\mathcal{B}}^{\prime }$, which contains large bicliques that are part of any optimal solution. In this set, besides the bicliques including a $K_{3,4}$ (or $K_{4,3}$), we will identify as well certain bicliques with size $K_{2,a}$ for $a\ge 5$ and $K_{1,b}$ for $b\ge 10$ (and the cases $K_{a,2}$, $K_{b,1}$).

This will ensure that all remaining bicliques necessary for covering all edges in $G^{\prime }$ will have at most 9 edges in $G^{\prime }$ (i.e., they will be $K_{3,3}$, $K_{2,a}$, $K_{a,2}$ for $a\le 4$ and $K_{1,b}$, $K_{b,1}$ for $b\le 9$.)

Then, we cast the problem of selecting the minimum number of bicliques in ${\mathcal{C}}^{\prime }$ that cover all remaining edges of $G^{\prime }$ (besides the one in ${\mathcal{B}}^{\prime }$) as a set cover problem with sets of size at most 9. For this problem, it is known that the greedy algorithm gives a $H\left(9\right)$ approximation factor showing that all remaining edges in $G^{\prime }$ are covered with additional $\le H\left(9\right)(k-k^{\prime })$ bicliques plus the $k^{\prime }\le k$ in ${\mathcal{B}}^{\prime }$ for a total of $\le H\left(9\right)k$ bicliques.

Finally, from the biclique cover of $G^{\prime }$, we can reconstruct the biclique cover in G with the same techniques of the previous section, outputting a cover with at most $H\left(9\right)k$ bicliques.

Properties of the Kernelized Graph of a $(2,k)$-Biclique Cover Yes-Instance

We show some additional properties of the kernelized graph of a $(2,k)$-biclique cover yes-instance that will be exploited by the algorithm. In this subsection, we always assume $G^{\prime }$ is the kernelized graph of $(2,k)$-biclique cover yes-instance G.

Lemma 6.

Let $(L_A,R_A)$ be a $K_{2,5}$ biclique in $G^{\prime }$ such that $L_A$ is not included in any $K_{3,4}$ biclique in $G^{\prime }$. Then, in any $(2,k)$-biclique cover $\mathcal{B}$, there is always a unique biclique that covers all the nodes in $L_A$ and no other node in the left side. (A similar result holds for $K_{5,2}$ bicliques.)

Proof. 

We first show that in any $K_{2,5}$ biclique $(L_A,R_A)$, all nodes in the small side $L_A$ need to belong to the same biclique in any $(2,k)$-biclique cover.

Fix a $(2,k)$-biclique cover $\mathcal{B}$. $F\left(u\right)$ refers to the set of bicliques covering u in the cover $\mathcal{B}$.

Let $L_A=\{u,v\}$. Suppose to get a contradiction that $F\left(u\right)\cap F\left(v\right)=\varnothing$, then each node in $R_A$ contains one biclique from $F\left(u\right)$ and one from $F\left(v\right)$. It is possible to verify that at most $2\times 2=4$ distinct sets of size at most 2 can be formed by taking one element from $F\left(u\right)$ and one from $F\left(v\right)$. Hence, there are two nodes in $R_A$ that are covered by the same set of bicliques, giving a contradiction as the graph is kernelized.

So we know that there is a biclique $A\in F\left(u\right)\cap F\left(v\right)$. Consider a node $x\in R_A$ such that $A\notin F\left(x\right)$. It is easy to see that there can be only one such node, as this node must be covered by the other biclique of $F\left(u\right)$ and the other biclique of $F\left(v\right)$ not equal to A. Again, for the kernelization, only one such node can exist.

So at least 4 nodes in $R_A$ belong to a unique biclique. Finally, notice that if there is another node in the side of $L_A$ in the same biclique, that would form a $K_{3,4}$ biclique. ☐

Lemma 7.

Let $(L_A,R_A)$ be a $K_{1,10}$ biclique in $G^{\prime }$ such that $R_A$ is not in any $K_{2,5}$ biclique including the node in $L_A$ in the left part of the biclique. Then, in any optimal solution, there is a single biclique that covers the node in $L_A$ and no other node on that side.

Proof. 

Fix a $(2,k)$-biclique cover $\mathcal{B}$. $F\left(u\right)$ refers to the set of bicliques covering u in the cover $\mathcal{B}$.

Let $u\in L_A$. If $F\left(u\right)=A$, then all node in $R_A$ belong to A and we can apply Lemma 4. Let  $F\left(u\right)=\{A,B\}$, we have that all nodes in $R_A$ belong either to A or to B or both. W.l.o.g., let A be the more common of the two. We have that A appears at least 5 times. So, if any other node in u side belongs to A, that would form a $K_{2,5}$ biclique. ☐

Algorithm

We now state how the algorithm for this problem constructs the set ${\mathcal{B}}^{\prime }$. First, we add to ${\mathcal{B}}^{\prime }$ all bicliques including a $K_{3,4}$, as done in Step 2 of Algorithm 1. Then, we add to ${\mathcal{B}}^{\prime }$ all bicliques of the form $\left(\right\{u,v\},N(u)\cap N(v\left)\right)$ (and similar form $\left(N\right(u)\cap N(v\left)\right),\{u,v\}$) for $u\ne v\in L^{\prime }$ such that $u,v$ are part of a $K_{2,5}$ and not of a $K_{3,4}$. Finally, we add bicliques $\left(\right\{u\},N(u\left)\right)$ (and the form $\left(N\right(u),\{u\left\}\right)$) such that $u\in L^{\prime }$ has at least 10 edges not covered by the bicliques added before.

We claim the following property for ${\mathcal{B}}^{\prime }$.

Lemma 8.

There is a $(2,k)$-biclique cover of $G^{\prime }$ which contains all bicliques in ${\mathcal{B}}^{\prime }$ and only other bicliques with at most 9 edges.

Proof. 

The lemma follows by combining Lemmas 5 and 6. By Lemma 5, we know that there is no other biclique in any $(2,k)$-biclique cover with at least 3 nodes on the smaller side and at least 4 on the largest side.

Suppose there is a $(2,k)$-biclique cover of $G^{\prime }$ containing all bicliques of ${\mathcal{B}}^{\prime }$ and another biclique $B=(L_B,R_B)\notin {\mathcal{B}}^{\prime }$ of the form $K_{2,a}$ for $a\ge 5$. If nodes in $L_B$ are part of a $K_{3,4}$ biclique, we get a contradiction, as we have two nodes in $L_B$ that are both covered by the biclique B and the other biclique in ${\mathcal{B}}^{\prime }$ identified by the algorithm (by kernelization this is not possible). So we know that $L_B$ is not part of a $K_{3,4}$ biclique. However, in this case, by construction of the algorithm, there is another biclique ${\mathcal{B}}^{\prime }$ covering $L_B$, so again we get a contradiction. (The same proof works for the $K_{a,2}$ case for $a\ge 5$).

Finally notice that, by construction, at most 9 edges of each node are left uncovered by bicliques in ${\mathcal{B}}^{\prime }$ so there is a $(2,k)$-biclique cover that includes all bicliques in ${\mathcal{B}}^{\prime }$ and other bicliques with at most 9 edges each. ☐

Finally, notice that we can enumerate the set ${\mathcal{C}}^{\prime }$ of all bicliques with at most 9 edges necessary to cover the edges left uncovered by the bicliques in ${\mathcal{B}}^{\prime }$ in time $O\left(n^6\right)$, where n is the number of nodes in the graph $G^{\prime }$.

The proof of Theorem 2 follows by the properties of set cover.

3.3. NP-Complete Result for $f\ge 5$

Theorem 3.

$(f,k)$-biclique cover is NP-Complete for any $f\ge 5$.

3.4. Proof of Theorem 3

Recall that the $(\mathsf{\Delta },k)$-clique vertex partition problem is defined as follows. Given a graph  $G=(V,E)$, with maximum degree $\le \mathsf{\Delta }$ and an integer k, determine whether there is a partition of nodes in V in $t\le k$ subsets $C_1,\dots ,C_t$, such that each subset $C_i$ is a clique.

Král et al. [19] showed a reduction to clique vertex partition from the NP-Complete Clause-Linked Planar 3-SAT problem [20]. The latter is the following decision problem: given a CNF formula, where each clause contains either 2 or 3 literals and each literal appears in exactly 3 clauses (twice negated and once positive), determine whether the formula is satisfiable.

Král et al. [19] showed that given such formula $\varphi$ we can construct a graph $G_{\varphi }=(V_{\varphi },E_{\varphi })$ such that nodes in $V_{\varphi }$ can be partitioned in $|X|+3|C|$ cliques iff $\varphi$ is satisfiable (where X and C are the sets of variables and clauses of $\varphi$, respectively). The graph $G_{\varphi }$ is constructed as follows. For each variable $x\in X$, create the subgraph $G_x=(\{x,x^{+},x_1^{-},x_2^{-}\},\{x{x}^{+},x{x}_1^{-},x{x}_2^{-},x_1^{-}{x}_2^{-}\})$. For each clause $c\in C$, create a 7-node cycle $G_c$. If the clause c has 3 literals x,y,z, fix three non pairwise adjacent nodes: $c\left(x\right)$, $c\left(y\right)$, $c\left(z\right)$ in the cycle (e.g., let $c\left(x\right)$ be at distance two from $c\left(y\right)$, and let $c\left(y\right)$ be at distance two from $c\left(z\right)$ and let $c\left(z\right)$ be at distance three from $c\left(x\right)$). If the clause has two variables, ignore $c\left(z\right)$. Now, for  each literal x if c is the clause in which it appears positive, let the $c\left(x\right)$ node in $G_c$ be coincident with the node $x^{+}$ in $G_x$. For the clauses in which x appears negated, we similarly use nodes $x_1^{-}$ and  $x_2^{-}$.

The following result is a corollary of those of Král et al. [19].

Lemma 9.

$(\mathsf{\Delta },k)$-clique vertex partition is NP-Complete for $\mathsf{\Delta }\ge 4$.

Proof. 

By Král et al. [19], we know that $\varphi$ is satisfiable iff the nodes in $V_{\varphi }$ can be partitioned in $|X|+3|C|$ cliques. Notice that graph $G_{\varphi }$ has maximum degree $\mathsf{\Delta }\le 4$. Hence, $(4,k)$-clique vertex partition is NP-Complete as well. ☐

Now, using the reduction of Orlin [5], we show that $(\mathsf{\Delta },k)$-clique vertex partition can be reduced to $(\mathsf{\Delta }+1,\mathsf{\Delta }+1,k^{\prime })$-biclique cover for some $k^{\prime }\ge k$.

Given a graph $G=(V,E)$, construct a bipartite graph $B_G=(L,R,E_B)$ as follows. For each node $v_i\in V$, create two nodes $x_i\in L,y_i\in R$. Moreover, for each edge $v_i{v}_j\in E$, make two nodes $x_{ij}\in L$ and $y_{ij}\in R$. For each $v_i\in V$. we have $x_i{y}_i\in E_B$. Also for each edge $v_i{v}_j\in E$. we have the following edges in $E_B$$x_i{y}_j,x_{ij}{y}_j,x_i{y}_{ij},x_{ij}{y}_{ij}$. Orlins [5] showed that a graph G admits a clique vertex partition in k cliques iff the edges of $B_G$ can be cover by at most $k+|E|$ bicliques. The following lemma can also be  shown.

Lemma 10.

Let G be a graph with maximum degree at most Δ, and let $B_G$ the corresponding bipartite graph defined before, there exists a $(\mathsf{\Delta }+1,k+|E|)$-biclique cover of $B_G$ iff there is k-clique vertex partition of G.

Proof. 

Suppose there is no k-clique vertex partition of G. Then, by Orlins [5], we know that there is no biclique cover of the edges of $B_G$ with $k+|E|$ bicliques (irrespectively of how many bicliques a node belongs). Suppose there is a k-clique vertex partition of nodes in G. Let C be any set in the partition. Then, it is possible to see that $B_C=(\{x_i|v_i\in C\},\{y_i|v_i\in C\})$ is a biclique in $B_G$ and that k such bicliques covers all edges of the form $x_i{y}_i$. Also, as the sets in the partition are disjoint, each node in $V\left(B_G\right)$ belongs to at most one such biclique.

Now, consider the edges of the form $x_i{y}_j\in E_B$, for $v_i{v}_j\in E$. Any such edge can be covered with the biclique $B_{ij}=(\{x_{ij},x_i\},\{y_j,y_{ij}\})$. Notice that by using $|E|$ such bicliques we can complete the cover of all the remaining edges in $E_B$ (including the edges of the form $x_{ij}{y}_{ij}$). Now, each node of the form $x_{ij}$ (or $y_{ij}$) belongs to only one biclique in this cover. Nodes $x_i$ belong to one biclique of the form $B_C$ as well as other $deg\left(v_i\right)$ bicliques of the form $B_{ij}$ such that $v_i{v}_j\in E$. So we have that each node is part of at most $\mathsf{\Delta }+1$ bicliques because of the degree of G. ☐

Theorem 3 is a corollary of the above lemma.

4. Model II: One-Side Stochastic Model

We recall the definition of the model. In the $(f,\overline{p},k)$-biclique cover model, there is a constant f, a  vector of k probabilities $\overline{p}=p_1,\dots p_k$, and a number of factors k. The input is a graph $G=(L,R,E)$ where each node in L is assigned to $\le f$ factors from $\left[k\right]$ arbitrary and each node in R is assigned independently to factor i with probability $0<p_i<1$. A node $u\in L$ and a node $v\in R$ are connected iff they share a common factor.

We show that, under certain conditions on the parameters f and $\overline{p}$, we can recover an optimal or close to optimal $(f,k,k)$-biclique cover of the graph.

We will make the following two assumptions throughout the section. First, let $L_i\subseteq L$ be the set of nodes assigned to factor i in L. We will always assume that for no pair $i\ne j\in \left[k\right]$, $L_i\subseteq L_j$. Notice that if $L_i\subseteq L_j$ for $i\ne j$ then the biclique of factor i is completely covered by the biclique of factor j and there is a equivalent $(f,\overline{p^{\prime }},k-1)$-biclique cover model without the factor i.

Let $p_m={min}_{i\in \left[k\right]}\left(p_i\right)$, $p_M={max}_{i\in \left[k\right]}\left(p_i\right)$. Second, we assume that the right side R is sufficiently large w.r.t. the left side. In particular we assume $|R|>C_{f,p_m,p_M}log(|L|)$ for a sufficiently large constant $C_{f,p_m,p_M}$ which depends on $f,p_m,p_M$ only. This is to allow extracting enough information from the random assignment in the right part.

In the rest of the section, we present two results. First, we show that under an additional condition on the constants $\overline{p}$ that ensures that no factor has much higher probability than another factor and that no factor has too large a probability, then an exact $(f,\overline{p},k)$-biclique cover can be obtained in polynomial time. We then show that for any vector of constants $\overline{p}$, it is possible to obtain an approximate cover.

4.1. Optimal $(f,\overline{p},k)$-Biclique Cover

We first state the additional condition on $\overline{p}$:

$$\frac{p_m}{2}>1-{(1-p_M)}^{2f-1}(1+(2f-1)p_M)$$

(1)

Notice that for any f there is a non-empty set of vectors $\overline{p}$ for which the condition holds. For instance, it holds for any vector s.t. $0<p_m=p_M<c_f$ where $c_f<1$ is constant depending on f. We will prove the following theorem.

Theorem 4.

Let $G=(L,R,E)$ be the graph obtained by the $(f,\overline{p},k)$-biclique cover model, such that $|R|\ge \mathsf{\Omega }(log(|L|\left)\right)$ and where the condition in Equation (1) holds for $\overline{p}$. There exists a $O(k|L{|}^{f+1}|E|)$ time algorithm that given G, f, k and $p_m$ outputs a $(f,k,k)$-biclique cover of G w.h.p. In the paper, we say that an event happens with high probability if it happens with probability $\ge 1-{|V|}^c$ for some constant $c>0$.

Main Ideas

Before entering into the details of the proof here we present the main ideas of the proof. First, we  show that, under the condition in Equation (1) and for $|R|\ge \mathsf{\Omega }(log(|L|\left)\right)$, it is possible to distinguish in polynomial time w.h.p., whether in any given set $S\subseteq L$ there exists at least a factor $i\in \left[k\right]$, such that all nodes in S belong to the $L_i$ (are assigned to the factor). In particular, we show that this is possible by just looking at the number of the common neighbors of all the nodes in S.

We will then assume to have an oracle $\mathcal{I}:2^L\to \{0,1\}$ that returns, w.h.p. $\mathcal{I}\left(S\right)=1$, iff there is factor to which all nodes in S belong.

We will show that there is an algorithm that makes a polynomial numbers of calls to this oracle and finds an $(f,k,k)$-biclique cover of G. We stress that this algorithm could be used also for other probabilistic models where the function $\mathcal{I}$ can be computed with sufficient accuracy.

The intuition of the algorithm is that we can construct each biclique in the cover, one at a time, once we identify a set of nodes $S\subseteq L$ such that there exists a unique factor $i\in \left[k\right]$ to which all nodes in S belong. Furthermore, we show that for any factor there is at least one set of size $\le f$ of nodes in L for which this happens. We can then identify each biclique in polynomial time, w.h.p.

We now proceed to prove formally the results the this model.

4.1.1. Determining Whether Nodes in $S\subseteq L$ Share a Common factor

Recall that in this section we assume we are given a bipartite graph $G=(L,R,E)$ obtained by the $(f,\overline{p},k)$-biclique cover where the condition Equation (1) holds, $|R|\ge \mathsf{\Omega }(log(|L|\left)\right)$ and no $L_i$ set is subset of $L_j$ for two distinct factors $i,j\in \left[k\right]$.

First, we show that, given a set $S\subseteq L$, it is possible to distinguish based on the graph G whether there is at least a common factor assigned to all nodes in S. In this section, we use $F\left(u\right)$ to indicate the set of bicliques covering node u in the model (i.e., each biclique corresponds to the nodes with one  factor).

Lemma 11.

Given a set $S\subseteq L$, if ${\bigcap }_{u\in S}F\left(u\right)=\varnothing$ then the probability that

$$|\bigcap _{u\in S}N\left(u\right)|>(1+ϵ)2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}))|R|$$

for $0<ϵ<1$ is smaller than $exp(-1/3{ϵ}^{2}C|R|)$, for some constant C not dependent on $|R|$.

Proof. 

Let $X_w$ be the indicator variable of the event that $\forall u\in S$$(u,w)\in E$.

We claim that the probability of $X_w$ is upper-bounded by twice the probability of the following event: w is part of at least two bicliques selected from a set $F^{\prime }$ of cardinality at most $2f$. Suppose in fact that w is part of a single biclique B, then as ${\bigcap }_{u\in S}F\left(u\right)=\varnothing$, w cannot be connected to all nodes in S. w  must be part of at least two bicliques. Now, fix a single node $u\in S$. $|F(u)|\le f$, and w is part of at least one biclique in $F\left(u\right)$. If w is part of two bicliques in $F\left(u\right)$, then our bound holds (use $F^{\prime }=F\left(u\right)$ as a the sets from which the bicliques must be selected). If w is part of a single biclique $B\in F\left(u\right)$, then fix $v\in S$, a node such that $B\notin F\left(v\right)$ (the node exists for the empty intersection in S). We have that w is part of another biclique from $F\left(v\right)$ with $|F(v)|\le f$. In this case, w is part of at least two bicliques from the set $F^{\prime }=F\left(v\right)\cup F\left(u\right)$ of size at most $2f$. By union bound on these two cases

$$\mathrm{Pr}\left(X_w\right)\le 2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}))$$

where the inequality comes from the fact that the probability is maximized when the set $F^{\prime }$ contains exactly $2f$ bicliques of maximum probability $p_M$, the probability of selecting at least 2 bicliques is the opposite of the probability of not selecting 0 of 1 biclique.

Let X be the random variable that measures the cardinality of $|{\bigcap }_{u\in S}N\left(u\right)|$. Then, it is easy to see  that

$$\mathbf{E}\left[X\right]\le |R|2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}),$$

and by the Chernoff bound, for $0<ϵ<1$, we have

$$\mathrm{Pr}\left(X>(1+ϵ)\mathbf{E}\left[X\right]\right)<exp(-1/3{ϵ}^{2}2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}|R|\left)\right).$$

 ☐

Similarly, we can show

Lemma 12.

Let $S\subseteq L$ such that ${\bigcap }_{u\in S}F\left(u\right)\ne \varnothing$ then the probability that $|{\bigcap }_{u\in S}N\left(u\right)|<(1-ϵ)p_m|R|$ for $0<ϵ<1$ is smaller than $exp(-1/3{ϵ}^2{p}_m|R|)$.

Proof. 

Let $X_w$ be the indicator variable of the event that $\forall u\in S$, we have $(u,w)\in E$. Let A be one of the common biclique of the nodes. We have

$$\mathrm{Pr}\left(X_w\right)\ge \mathrm{Pr}\left(A\in F\left(w\right)\right)=p_A\ge p_m,$$

the result follows by the Chernoff bound. ☐

Lemma 13.

Let $p_m>2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1})$, given a set $S\subseteq L$, then there is a constant $0<ϵ<1$ and a constant $c>0$ such that, for $|R|\in \mathsf{\Theta }(log(|L|\left)\right)$ with probability $\ge 1-exp(-c|R|)$

$$|\bigcap _{u\in S}F\left(u\right)|>0$$

if and only if $|{\bigcap }_{u\in S}N\left(u\right)|\ge (1-ϵ)p_m|R|$.

Proof. 

If $p_m>2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}$ then there is an $ϵ>0$ for which $(1-ϵ)p_m>(1+ϵ)2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}$.

Notice that $(1/3){ϵ}^2{p}_m>1/3{ϵ}^{2}2(1-{(1-p_M)}^{2f}-2f{p}_M{(1-p_M)}^{2f-1}$.

Then we can apply the previous lemma and show that that with probability at least

$$1-exp(-(1/3){ϵ}^2{p}_m|R|)$$

we have $|{\bigcap }_{u\in S}N\left(u\right)|\ge (1-ϵ)p_m|R|$ iff $|{\bigcap }_{u\in S}F\left(u\right)|>0.$ ☐

Given the previous results, we can implement a function $I\left(S\right)$ that given a set S determines correctly, in time $O(|E|)$, whether $|{\bigcap }_{u\in S}F\left(u\right)|>0$ with probability at least

$$1-exp(-(1/3){ϵ}^2{p}_m|R|).$$

4.1.2. Algorithm Based on the Oracle I

In this section, we will assume that there is a function $I\left(S\right)$ that returns $I\left(S\right)=1$ iff $|{\bigcap }_{u\in S}F\left(u\right)|>0$. We will assume that the function returns the correct answers all times. Given the previous results, since we make $O(|L{|}^c)$ calls to such function, this happens w.h.p. as long as $|R|\ge C_{f,p_m,p_M}log(|L|)$ for such sufficiently large constant $C_{f,p_m,p_M}$ depending on $f,p_m,p_M$.

The algorithm is presented in Algorithm 2.

Algorithm 2 OptCoverOneSideRandom($G=(L,R,E),f,p_m,k$)

Mark all edges in E as uncovered.  Let $\mathcal{B}\leftarrow \varnothing$ be the set of bicliques in the cover  while $\exists u\in L$ adjacent to an uncovered edge do      — Step 1 —      $L_B\leftarrow \left\{u\right\}$.      — Step 2 —      while $\exists S\subseteq L\backslash L_B$ s.t. $1\le |S|\le f$, $\mathcal{I}(S\cup L_B)=1$ and there is no biclique in $\mathcal{B}$ that covers all nodes in $S\cup L_B$ do          $L_B\leftarrow L_B\cup S$.      end while      — Step 3 —      for $\forall v\in L$ do          if $v\notin L_B$ and $\mathcal{I}(L_B\cup v)=1$ then             $L_B\leftarrow L_B\cup \left\{u\right\}$.          end if      end for      — Step 4 —      $R_B={\bigcap }_{u\in L_B}N\left(u\right)$      $B\leftarrow (L_B,R_B)$      $\mathcal{B}\leftarrow \mathcal{B}\cup B$      Mark all edges in B as covered.  end while  return $\mathcal{B}$

Intuition of the Algorithm

The main idea of the algorithm is to isolate a single new biclique B at a time from the optimal cover $\mathcal{B}$ given by the model. We do so by finding any subset $L_B\subseteq L$ of left nodes such that: any node in S belong to biclique B; and there is no other biclique to which all nodes in S belongs. Then we will identify all the left nodes that belong to biclique B.

Correctness of the Algorithm

We first show the following lemma.

Lemma 14.

For any biclique $B=(L_B,R_B)$ in the cover $\mathcal{B}$ given by the model, there is a set of $S\subseteq L$ of size at most f such that ${\bigcap }_{u\in S}F\left(u\right)=B$.

Proof. 

Consider a node $u\in L_B$. This node can belong to at most other $f-1$ bicliques $B_1,\dots B_c\in \mathcal{B}$ with $c\le f-1$. Notice that for any biclique $B_i$ there exists a node $u_i$ s.t. $B\in F\left(u_i\right)$ and $B_i\notin F\left(u_i\right)$ (by assumption in the model left nodes in biclique B are not a subset of biclique $B_i$). Hence the set $S=\{u,u_1,\dots u_c\}$ (where $u_i$ might not be distinct) has the property that ${\bigcap }_{u\in S}F\left(u\right)=B$ and $|S|\le f$. ☐

We now show that Algorithm 2 is correct.

Theorem 5.

The Algorithm 2 computes a biclique cover for the graph G with k bicliques.

Proof. 

We show this by induction on the order of the bicliques determined by the algorithm. More  precisely, we will show that for any $k^{\prime }\ge 0$, there exists an optimal cover containing all the first $k^{\prime }$ bicliques determined by the algorithm. The base case for $k^{\prime }=0$ is obvious (no clique has been determined). Suppose the statement holds for the first $k^{\prime }-1$ bicliques. If the algorithm ends without adding another biclique, this concludes the proof. Otherwise, let B be the $k^{\prime }$-th biclique determined. Notice that for the algorithm to not stop, this means that a node $u\in L$ had at least an edge uncovered. So we know that u must belong to another biclique in an optimal cover. We will now show that until the end of Step 3, the set $L_B$ preserves the property that there is a biclique B in the optimal cover (not already found) containing all nodes in $L_B$. This is clearly true at the beginning (Step 1). In Step 2, we check this property explicitly. Notice that in Step 3 we add nodes in $L_B$ only if they maintain the property $\mathcal{I}(L_B\cup v)=1$, so the property continues to hold.

We now show that at the end of Step 3 there is a unique biclique not in the cover determined so far that covers all nodes in $L_B$ in the optimal solution. Suppose there exists a set of 2 or more distinct new bicliques that covers all the nodes in the set $L_B$ obtained after the end of Step 3. Notice that by Lemma 14 there is set $S\subseteq L$ of size $|S|\le f$ such that only one of the two bicliques covers all nodes in S. S respects the condition of the while, so we would not have exited the loop of Step 2 giving a contradiction. Hence, at the end of Step 2, there is a unique new biclique B, such that all nodes in $L_B$ belong to the biclique.

Hence, it follows that all left nodes of biclique B are found in Step 3, (they intersect because of biclique B, and the loop greedily adds all nodes that intersect).

Finally, during Step 4, it is clear that we construct a biclique B that covers all the edges covered by the biclique in the optimal solution with left side given by $L_B$. So there is an optimal solution that contains the biclique B computed. ☐

Time Complexity

Notice that the outer loop can be executed only $O\left(k\right)$ times (once for each biclique found). In Step 2, the loop is executed at most $O\left(n\right)$ times and requires at most $O(|L{|}^f)$ calls to $\mathcal{I}$ each of cost $O(|E|)$ for a total of $O(|L{|}^{f+1}|E|)$. Step 3 requires $O(|L|)$ calls to $\mathcal{I}$ for a total of $O(L|E|)$. Finally, Step 4 costs $O(|E|)$. The total cost is $O(k|L{|}^{f+1}|E|)$.

The correctness of Theorem 4 follows from the previous results.

4.2. Approximate Biclique Cover

In this section, we show that for any constants in $\overline{p}$ subject only to $0<p_i<1$ for $i\in \left[k\right]$ we can construct an approximate solution to the problem.

Theorem 6.

Let $G=(L,R,E)$ be the graph obtained by the $(f,\overline{p},k)$-biclique cover model, such that $|R|\ge \mathsf{\Omega }(log(|L|\left)\right)$. There exists a $O\left(\right(|L|+{|R|)}^{{\alpha }_{f,p_m,p_M}})$ time algorithm where ${\alpha }_{f,p_m,p_M}$ is a constant depending only on $f,p_m,p_M$ but not on the size of the graph, such that, given G, f, k, and $p_m$ the algorithm outputs 1) a set of $k^{\prime }=O(log(|L|+|R|\left)k\right)$ bicliques covering all edges of G; and 2) a set of k bicliques covering $(1-\frac{1}{e})|E|$ edges of G.

Before entering into the details of the proof, we present the main idea of the algorithm, which  is the following. There exists a constant $c_{f,p_m,p_M}$ depending on $f,p_m,p_M$ such that if we sample u.a.r. a set $S\subseteq R$ of size $|S|=c_{f,p_m,p_M}log(|L|)$ we have that for each factor $i\in \left[k\right]$ there is a set $S_i\subseteq S$ such that $|S_i|\ge c^{\prime }log(|L|)$ for some constant $c^{\prime }<c_{f,p_m,p_M}$ and all nodes in $S_i$ belong to the factor i. Moreover, it is possible to show that the set of common neighbors of $S_i$ in L is, w.h.p., exactly the set of nodes $L_i$. Given such set $S_i$, we can reconstruct the biclique $B_i$ that covers all nodes with factor i. Now, we can list all subsets $S^{\prime }\subseteq S$ of size $\le c^{\prime }log(|L|)$ in polynomial time and construct a single candidate biclique $B^{\prime }$ from each subset $S^{\prime }$. We have that k of these bicliques cover all edges of G, so we can cast the problem as a maximum coverage problem and find a set of k bicliques covering $(1-\frac{1}{e})|E|$ edges or as a set cover problem and find a set of $log(|E|)k$ bicliques covering all edges.

Algorithm

We now outline the algorithm (Algorithm 3). Suppose we are given a bipartite graph $G=(L,R,E)$ obtained by the $(f,\overline{p},k)$-biclique cover model.

Algorithm 3 ApproxCoverOneSideRandom($G=(L,R,E),f,p_m,p_M,k$)

Let $$\overline{c}=max\left(16p_m^{-1},2p_m^{-1}{log}_{{(1-{(1-p_M)}^f)}^{-1}}\left(3\right)\right)$$  Sample a set $S\subseteq R$ of $\overline{c}log(|L|)$ nodes u.a.r. from R (without replacement).  Let $\mathcal{C}\leftarrow \varnothing$  for Each subset $S^{\prime }\subseteq S$ do      Let $L^{\prime }\leftarrow {\bigcap }_{v\in S^{\prime }}N\left(v\right)$.      Let $S^{\prime \prime }\leftarrow {\bigcap }_{v\in L^{\prime }}N\left(v\right)$.      Let B be the set of the edges covered by biclique $(L^{\prime },S^{\prime \prime })$.      $\mathcal{C}\leftarrow \mathcal{C}\cup B$.  end for  Apply the greedy max coverage (or set cover) algorithm using $\mathcal{C}$ as the input sets and E as the universe set to cover.

Let $p_m={min}_i{p}_i$ and $p_M={max}_i{p}_i$. Let $\overline{c}$ be a constant to be determined subsequently. The algorithm first samples a subset S of R by selecting $clog(|L|)$ u.a.r. nodes in R without replacement. In the next lemma, we show that, for each biclique $B_i$ (in the cover defining the model), we have a large number of nodes in S covered by that biclique.

Lemma 15.

Suppose for $\overline{c}\ge 16p_m^{-1}$ a set of S of $\overline{c}log(|L|)$ nodes is drawn u.a.r. without replacement. No biclique $i\in \left[k\right]$, $B_i=(L_i,R_i)$ of the model is such that $|R_i\cap S|<\frac{1}{2}\overline{c}{p}_{m}log(|L|)$ with probability at least $1-\frac{1}{|L|}$.

Proof. 

Consider a single biclique $B_t$, $t\in \left[k\right]$. Let $X_i$ be an indicator random variable of the event that the i-th node drawn in S is covered by B in the cover of the model. Let $X={\sum }_{i=1}^{\overline{c}log(|L|)}{X}_i$. Notice that as nodes in R are assigned to biclique $B_t$ independently with probability $p_t$, and the sampling without replacement maintains the independence, we have $\mathbf{E}\left[X\right]=\overline{c}log(|L|)p_t\ge \overline{c}log(|L|)p_m$ and by Chernoff bound

$$\mathrm{Pr}\left(X<\frac{1}{2}\overline{c}log(|L|)p_m\right)\le exp(-\frac{1}{8}\overline{c}{p}_{m}log(|L|)).$$

For $\overline{c}\ge 16p_m^{-1}$, we have

$$\mathrm{Pr}\left(X<\frac{1}{2}\overline{c}log(|L|)p_m\right)\le {|L|}^{-2},$$

and hence by union bound as $k\le |L|$ with probability $\ge 1-\frac{1}{|L|}$ no biclique appears in less than $\frac{1}{2}\overline{c}log(|L|)p_m$ nodes in S. ☐

Then, we show that if a subset $S^{\prime }\subseteq S\subseteq R$ of size $>c^{\prime }log\left(n\right)$, where $c^{\prime }$ is a constant, is such that all nodes of $S^{\prime }$ belong to biclique $B_i$ then no node $v\in L$ is connected to all nodes in $S^{\prime }$, w.h.p, unless it belongs to the same biclique.

Lemma 16.

Suppose $c^{\prime }\ge {log}_{{(1-{(1-p_M)}^f)}^{-1}}\left(3\right)$. Fix a set $S^{\prime }\subseteq S$ of size $c^{\prime }log(|L|)$ of nodes in R. Suppose that all nodes in S are such that they all belong to biclique $B_t=(L_t,R_t)$ in the cover defining the model, then

$$\bigcap _{v\in S^{\prime }}N\left(v\right)=L_t,$$

with probability $\ge 1-\frac{1}{{|L|}^2}$.

Proof. 

Notice that $L_t\subseteq {\bigcap }_{v\in S^{\prime }}N\left(v\right)$, as all nodes in $L_t$ are connected to nodes in $S^{\prime }$ by definition. We prove that a given node $v\in L\backslash L_t$ is connected to all nodes in $S^{\prime }$ with probability $\le \frac{1}{{|L|}^3}$. Notice that all bicliques are assigned to nodes in R independently. So consider a node $u\in L$ such that $B_t\notin F\left(u\right)$.

$$\begin{array}{ccc}\hfill \mathrm{Pr}\left(u\in {\displaystyle \bigcap _{v\in S^{\prime }}}N\left(v\right)\right)& =\hfill & {\displaystyle \prod _{v\in S^{\prime }}}\mathrm{Pr}\left(F\left(u\right)\cap F\left(v\right)\ne \varnothing \right)\hfill \\ & =\hfill & {\displaystyle \prod _{v\in S^{\prime }}}\left(1-\mathrm{Pr}\left(F\left(u\right)\cap F\left(v\right)=\varnothing \right)\right)\hfill \\ & =\hfill & {\displaystyle \prod _{v\in S^{\prime }}}\left(1-{\displaystyle \prod _{B_t\in F\left(u\right)}}(1-p_t)\right)\hfill \\ & \le \hfill & {\displaystyle \prod _{v\in S^{\prime }}}\left(1-{(1-p_M)}^f)\right)\hfill \\ & \le \hfill & {\left(1-{(1-p_M)}^f)\right)}^{c^{\prime }log(|L|)}\hfill \\ & \le \hfill & {|L|}^{-3}\hfill \end{array}$$

(2)

By union bound on the n nodes in L, the result follows. ☐

Now, we fix a constant $\overline{c}$ such that $\frac{1}{2}\overline{c}{p}_m\ge {log}_{{(1-{(1-p_M)}^f)}^{-1}}\left(3\right)$ and such that the requirement of Lemma 15 is satisfied.

It is easy to see that for all $i\in k$ the bicliques in the optimal cover there is a set $S_i^{\prime }\subset S$ that by Lemma 16 w.h.p. is such that for $L_i^{\prime }={\bigcap }_{v\in S_i^{\prime }}N\left(v\right)$, $S_i^{″}={\bigcap }_{v\in L_i^{\prime }}N\left(v\right)$, the biclique $(L_i^{\prime },S_i^{″})$ covers more edges than the i-th biclique in the cover defining the model, w.h.p.

Notice that we can obtain all subsets $S^{\prime }\subseteq S$ in polynomial time $O\left(2^{\overline{c}log(|L|)}\right)={O(|L|}^{\overline{c}})$.

The correctness of Algorithm 3 follows from the fact that the set $\mathcal{C}$ contains w.h.p. each biclique from the cover defining the model, and the set $\mathcal{C}$ has size $O(|L|+{|E|)}^{{\alpha }_{f,p_m,p_M}})$ for some constant ${\alpha }_{f,p_m,p_M}$ depending on $f,p_m,p_M$ but not on the size of the graph or the number of bicliques.

5. Conclusions

We have studied two natural restrictions to the well-known problem of biclique cover in bipartite graphs that are motivated by practical applications in computational biology and other fields. For these restrictions, we have shown some non-trivial optimal or approximation algorithms which run in polynomial time.

As a future work, it would be interesting to determine whether $(f,k)$-biclique cover is NP-Complete for $2\le f\le 4$ and to determine inapproximability results for general values of f.