# Efficient Approximation for Restricted Biclique Cover Problems
### 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 leukocyte 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.