Inapproximability of Maximum Weighted Edge
Biclique and Its Applications
Jinsong Tan
Department of Computer and Information Science
School of Engineering and Applied Science
University of Pennsylvania, Philadelphia, PA 19104, USA
jinsong@seas.upenn.edu
Abstract. Given a bipartite graph G = (V1, V2, E) where edges take
on both positive and negative weights from set S , the maximum weighted
edge biclique problem, or S-MWEB for short, asks to find a bipartite sub-
graph whose sum of edge weights is maximized. This problem has various
applications in bioinformatics, machine learning and databases and its
(in)approximability remains open. In this paper, we show that for a wide
range of choices of S , specifically when
˛ ∈ Ω(ηδ−1/2)∩O(η1/2−δ)
(where η = max{|V1|, |V2|}, and δ ∈ (0, 1/2]), no polynomial time algo-
rithm can approximate S-MWEB within a factor of nǫ for some ǫ > 0
unless RP = NP. This hardness result gives justification of the heuristic
approaches adopted for various applied problems in the aforementioned
areas, and indicates that good approximation algorithms are unlikely to
exist. Specifically, we give two applications by showing that: 1) finding
statistically significant biclusters in the SAMBA model, proposed in [18]
for the analysis of microarray data, is nǫ-inapproximable; and 2) no poly-
nomial time algorithm exists for the Minimum Description Length with
Holes problem [4] unless RP = NP.
1 Introduction
Let G = (V1, V2, E) be an undirected bipartite graph. A biclique subgraph in G
is a complete bipartite subgraph of G and maximum edge biclique (MEB) is the
problem of finding a biclique subgraph with the most number of edges. MEB is
a well-known problem and received much attention in recent years because of
its wide range of applications in areas including machine learning [14], manage-
ment science [16] and bioinformatics, where it is found particularly relevant in
the formulation of numerous biclustering problems for biological data analysis
[5,2,18,19,17], and we refer readers to the survey by Madeira and Oliveira [13]
for a fairly extensive discussion on this. Maximum edge biclique is shown to be
NP-hard by Peeters [15] via a reduction from 3SAT. Its approximability status,
on the other hand, remains an open question despite considerable efforts [7,8,12]
1. In particular, Feige and Kogan [8] conjectured that maximum edge biclique
1 Note it might be easy to confuse the MEB problem with the Bipartite Clique problem
discussed by Khot in [12]. Bipartite Clique, which also known as Balanced Complete
http://arxiv.org/abs/0704.0468v2
2 Jinsong Tan
is hard to approximate within a factor of nǫ for some ǫ > 0. In this paper, we
consider a weighted formulation of this problem defined as follows
Definition 1. S-Maximum Weighted Edge Biclique (S-MWEB)
Instance: A complete bipartite graph G = (V1, V2, E) (throughout the paper, let
η = max{|V1|, |V2|} and n = |V1|+ |V2|), a weight function wG : E → S, where
S is a set consisting of both positive and negative integers.
Question: Find a biclique subgraph of G where the sum of weights on edges is
maximized.
A few comments are in order. First note it is not a lose of generality but a
technical convenience to require the graph be complete, one can always think of
an incomplete bipartite graph as complete where non-edges are assigned weight
0. Also note we require that both positive and negative weights be in S at the
same time because otherwise S-MWEB becomes a trivial problem.
Our study of S-MWEB is motivated by the problem of finding statistically
significant biclusters in microarray data analysis in the SAMBA model [18]
and the Minimum Description Length with Holes (MDLH) problem [3,4,10];
detailed discussion of the two problems can be found in Sect. 4. Our main
technical contribution of this paper is to show that if S satisfies the condition
|minS
| ∈ Ω(ηδ−1/2) ∩O(η1/2−δ), where δ > 0 is any arbitrarily small constant,
then no polynomial time algorithm can approximate S-MWEB within a factor
of nǫ for some ǫ > 0 unless RP = NP. This result enables us to answer open
questions regarding the hardness of the SAMBA model and the MDLH prob-
lem. Since maximum edge biclique can be characterized as a special case of
S-MWEB with S = {−η, 1}, the nǫ-inapproximability result also provides inter-
esting insights into the conjectured nǫ-inapproximability [8] of maximum edge
biclique.
The rest of the paper is organized in three sections. In Sect. 2, we present
the main technical result by proving the aforementioned inapproximability of S-
MWEB. We give applications of this by answering hardness questions regarding
two applied problems in Sect. 3. We conclude this work by raising a few open
problems in the last section.
2 Approximating S-Maximum Edge Biclique is Hard
We start this section by giving two lemmas about CLIQUE, which will be used
in establishing inapproximability for the biclique problems we consider later.
Lemma 1 is a recent result by Zuckerman [20], obtained by a derandomization
of results of H̊astad [11]; Lemma 2 follows immediately from Lemma 1.
Lemma 1. ([20]) It is NP-hard to approximate CLIQUE within a factor of
n1−ǫ, for any ǫ > 0.
Bipartite Subgraph [8], aims to maximize the number of vertices of a balanced sub-
graph whereas MEB aims to maximize the total weights on edges in a (not necessarily
balanced) subgraph.
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 3
Lemma 2. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate CLIQUE within a factor of n1−ǫ with probability at least 1
poly(n)
unless
RP = NP.
2.1 A Technical Lemma
We first describe the construction of a structure called {γ, {α, β}}-Product,
which will be used in the proof of our main technical lemma.
Definition 2. ({γ, {α, β}}-Product)
Input: An instance of S-MWEB on complete bipartite graph G = V1×V2, where
γ ∈ S and α < γ < β; an integer N .
Output: Complete bipartite graph GN = V N1 × V N2 constructed as follows: V N1
and V N2 are N duplicates of V1 and V2, respectively. For each edge (i, j) ∈ GN ,
let (φ(i), φ(j)) be the corresponding edge in G. If wG(φ(i), φ(j)) = γ, assign
weight α or β to (i, j) independently and identically at random with expectation
being γ, denote the weight by random variable X. If wG(φ(i), φ(j)) 6= γ, then
keep the weight unchanged. Call the weight function constructed this way w(·).
For any subgraph H of GN , denote by wγ(H) (resp., w−γ(H)) the total
weight of H contributed by former-γ-edges (resp., other edges). Clearly, w(H) =
wγ(H) + w−γ(H).
With a graph product constructed in this randomized fashion, we have the fol-
lowing lemma.
Lemma 3. Given an S-MWEB instance G = (V1, V2, E) where γ ∈ S, and a
number δ ∈ (0, 1
]; let η = max (|V1|, |V2|), N = η
δ(3−2δ)+3
δ(1+2δ) , GN = (V N1 , V
2 , E)
be the {γ, {α, β}}-product of G and S ′ = (S ∪ {α, β})− {γ}. If
1. |β − α| = O((Nη) 12−δ); and
2. there is a polynomial time algorithm that approximates the S ′-MWEB
instance within a factor of λ, where λ is some arbitrary function in the size of
the S ′-MWEB instance
then there exists a polynomial time algorithm that approximates the S-MWEB
instance within a factor of λ, with probability at least 1
poly(n)
Proof. For notational convenience, we denote η
−δ by f(η) throughout the proof.
Define random variable Y = X − γ, clearly E[Y ] = 0. Suppose there is a poly-
nomial time algorithm A that approximates S ′-MWEB within a factor of λ, we
can then run A on GN , the output biclique G∗B corresponds to N
2 bicliques in
G (not necessarily all distinct). Let G∗A be the most weighted among these N
subgraphs of G, in the rest of the proof we show that with high probability, G∗A
is a λ-approximation of S-MWEB on G.
Denote by E1 the event that G
B does not imply a λ-approximation on G.
Let H be the set of subgraphs of GN that do not imply a λ-approximation on G,
4 Jinsong Tan
clearly, |H| ≤ 4Nη. Let H ′ be an arbitrary element in H, we have the following
inequalities
Pr {E1} ≤ Pr
at least one element in H is a λ-approximation of GN
≤ 4Nη · Pr
H ′ is a λ-approximation of GN
= 4Nη · Pr{E2}
where E2 is the event that H
′ is a λ-approximation of GN .
Let the weight of an optimal solution U1×U2 of G be K, denote by UN1 ×UN2
the correspondingN2-duplication in GN . Let x1 and x2 be the number of former-
γ-edges in H ′ and UN1 × UN2 , respectively. Suppose E2 happens, then we must
w−γ(H
′) + x1γ ≤ N2(Kλ − 1)
w−γ(H
′) + wγ(H
′) ≥ 1
(w−γ(U
1 × UN2 ) + wγ(UN1 × UN2 ))
where the first inequality follows from the fact that we only consider integer
weights. Since w−γ(U
1 × UN2 ) = N2K − x2γ, it implies
(wγ(H
′)− x1γ)−
(wγ(U
1 × UN2 )− x2γ) ≥ N2
so we have the following statement on probability
Pr{E2} ≤ Pr
(wγ(H
′)− x1γ)− 1λ(wγ(U
1 × UN2 )− x2γ) ≥ N2
Let z1 (resp., z2 and z3) be the number of edges in E(H
′) − E(UN1 × UN2 )
( resp., E(UN1 × UN2 ) − E(H ′) and E(UN1 × UN2 ) ∩ E(H ′) ) transformed from
former-γ-edges in G. We have
(wγ(H
′)− x1γ)− 1λ(wγ(U
1 × UN2 )− x2γ) ≥ N2
i=1 Yi −
j=1 Yj +
k=1 Yk ≥ N2
i=1 Yi +
j=1 (−Yj) +
k=1 Yk ≥ N2
i=1 Yi ≥
j=1 (−Yj) ≥
k=1 Yk ≥
i=1 Yi ≥
j=1 (−Yj) ≥
k=1 Yk ≥
i∈{1,2,3}
3zi(c1f(Nη))
(Hoeffding bound)
≤ 3 · exp
−c2 · N
η3−2δ
(zi ≤ η2N2)
where c1, c2 are constants (c2 > 0). Now if we set N = η
+θ for some θ, we
Pr {E1} ≤ 4Nη · Pr {E2} ≤ 3 · exp
ln 4 · η
(1+2δ)
+θ − c2 · η(1+2δ)θ
For this probability to be bounded by 1
as η is large enough, we need to have
+θ < (1+2δ)θ. Solving this inequality gives θ > 2
δ(1+2δ)
. Therefore, for any
δ ∈ (0, 1
], by setting N = η
δ(3−2δ)+3
δ(1+2δ) , we have Pr{E1}, i.e. the probability that
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 5
the solution returned by A does not imply a λ-approximation of G, is bounded
from above by 1
once input size is large enough. This gives a polynomial time
algorithm that approximates S-MWEB within a factor of λ with probability at
least 1
This lemma immediately leads to the following corollary.
Corollary 1. Following the construction in Lemma 3, if S ′-MWEB can be ap-
proximated within a factor of nǫ
, for some ǫ′ > 0, then there exists a polyno-
mial time algorithm that approximates S-MWEB within a factor of nǫ, where
ǫ = (1 +
δ(3−2δ)+3
δ(1+2δ)
)ǫ′, with probability at least 1
poly(n)
Proof. Let |G| and |GN | be the number of nodes in the S-MWEB and S ′-MWEB
problem, respectively. Since λ = |GN |ǫ′ ≤ |G|(1+
δ(3−2δ)+3
δ(1+2δ)
, our claim follows
from Lemma 3. ⊓⊔
2.2 {−1, 0, 1}-MWEB
In this section, we prove inapproximability of {−1, 0, 1}-MWEB by giving a
reduction from CLIQUE; in subsequence sections, we prove inapproximability
results for more general S-MWEB by constructing randomized reduction from
{−1, 0, 1}-MWEB.
Lemma 4. The decision version of the {−1, 0, 1}-MWEB problem is NP-complete.
Proof. We prove this by describing a reduction from CLIQUE. Given a CLIQUE
instance G = (V,E), construct G′ = (V ′, E′) such that V ′ = V1∪V2 where V1, V2
are duplicates of V in that there exist bijections φ1 : V1 → V and φ2 : V2 → V .
E′ = E1 ∪ E2 ∪E3
E1 = {(u, v) | u ∈ V1, v ∈ V2 and (φ1(u), φ2(v)) ∈ E}
E2 = {(u, v) | u ∈ V1, v ∈ V2, φ1(u) 6= φ2(v) and (φ1(u), φ2(v)) /∈ E}
E3 = {(u, v) | u ∈ V1, v ∈ V2, and φ1(u) = φ2(v)}
Clearly, G′ is a biclique. Now assign weight 0 to edges in E1, −1 to edges in
E2 and 1 to edges in E3. We then claim that there is a clique of size k in G if
and only if there is a biclique of total edge weight k in G′.
First consider the case where there is a clique of size k in G, let U be the set
of vertices of the clique, then taking the subgraph induced by φ−11 (U)× φ
2 (U)
in G′ gives us a biclique of total weight k.
Now suppose that there is a biclique U1×U2 of total weight k in G′. Without
loss of generality, assume U1 and U2 correspond to the same subset of vertices in
2 Note we are slightly abusing notation here by always representing the size of a given
problem under discussion by n. Here n refers to the size of S ′-MWEB (resp. S-
MWEB) when we are talking about approximation factor nǫ
(resp. nǫ). We adopt
the same convention in the sequel.
6 Jinsong Tan
V because if (φ1(U1)−φ2(U2))∪ (φ2(U2)−φ1(U1)) is not empty, then removing
(U1 −U2)∪ (U2 −U1) will never decrease the total weight of the solution. Given
φ1(U1) = φ2(U2), we argue that there is no edge of weight −1 in biclique U1×U2;
suppose otherwise there exists a weight −1 edge (i1, j2) (i1 ∈ U1, and j2 ∈ U2),
then the corresponding edge (j1, i2) (j1 ∈ U1, and i2 ∈ U2) must be of weight
−1 too and removing i1, i2 from the solution biclique will increase total weight
by at least 1 because among all edges incident to i1 and i2, (i1, i2) is of weight 1,
(i1, j2) and (i2, j1) are of weight −1 and the rest are of weights either 0 or −1.
Therefore, we have shown that if there is a solution U1 × U2 of weight k in
G′, U1 and U2 correspond to the same set of vertices U ∈ V and U is a clique of
size k. It is clear that the reduction can be performed in polynomial time and
the problem is NP, and thus NP-complete. ⊓⊔
Given Lemma 1, the following corollary follows immediately from the above
reduction.
Theorem 1. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate problem {−1, 0, 1}-MWEB within a factor of n1−ǫ unless P = NP.
Proof. It is obvious that the reduction given in the proof of Lemma 4 preserves
inapproximability exactly, and given that CLIQUE is hard to approximate within
a factor of n1−ǫ unless P = NP, the theorem follows. ⊓⊔
Theorem 2. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate {−1, 0, 1}-MWEB within a factor of n1−ǫ with probability at least 1
poly(n)
unless RP = NP.
Proof. If there exists such a randomized algorithm for {−1, 0, 1}-MWEB, com-
bining it with the reduction given in Lemma 4, we obtain an RP algorithm for
CLIQUE. This is impossible unless RP = NP. ⊓⊔
2.3 {−1, 1}-MWEB
Lemma 5. If there exists a polynomial time algorithm that approximates {−1, 1}-
MWEB within a factor of nǫ, then there exists a polynomial time algorithm that
approximates {−1, 0, 1}-MWEB within a factor of n5ǫ with probability at least
poly(n)
Proof. We prove this by constructing a {γ, {α, β}}-Product from {−1, 0, 1}-
MWEB to {−1, 1}-MWEB by setting γ = 0, α = −1 and β = 1. Since δ = 1
according to Corollary 1, it is sufficient to set N = η4 so that the probability of
obtaining a n5ǫ-approximation for {−1, 0, 1}-MWEB is at least 1
poly(n)
Theorem 3. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate {−1, 1}-MWEB within a factor of n 15−ǫ with probability at least 1
poly(n)
unless RP = NP.
Proof. This follows directly from Theorem 2 and Lemma 5. ⊓⊔
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 7
2.4 {−η
, 1}-MWEB and {−ηδ−
2 , 1}-MWEB
In this section, we consider the generalized cases of the S-MWEB problem.
Theorem 4. For any δ ∈ (0, 1
], there exists some constant ǫ such that no poly-
nomial time algorithm can approximate {−η 12−δ, 1}-MWEB within a factor of
nǫ with probability at least 1
poly(n)
unless RP = NP. The same statement holds
for {−ηδ− 12 , 1}-MWEB.
Proof. We prove this by first construct a {γ, {α, β}}-Product from {−1, 1}-
MWEB to {−η 12−δ, 1}-MWEB by setting γ = −1, α = −(Nη) 12−δ and β = 1. By
Corollary 1, we know that for any δ ∈ (0, 1
], if there exists a polynomial time al-
gorithm that approximates {−η 12−δ, 1}-MWEB within a factor of nǫ, then there
exists a polynomial time algorithm that approximates {−1, 1}-MWEB within a
factor of n
δ(3−2δ)+3
δ(1+2δ)
with probability at least 1
poly(n)
. So invoking the hardness
result in Theorem 3 gives the desired hardness result for {−η 12−δ, 1}-MWEB.
The same conclusion applies to {−1, η 12−δ}-MWEB by setting γ = 1, α = −1
and β = (Nη)
−δ. Since η is a constant for any given graph, we can simply divide
each weight in {−1, η 12−δ} by η 12−δ. ⊓⊔
Theorem 4 leads to the following general statement.
Theorem 5. For any small constant δ ∈ (0, 1
], if
∣ ∈ Ω(ηδ−1/2)∩O(η1/2−δ),
then there exists some constant ǫ such that no polynomial time algorithm can ap-
proximate S-MWEB within a factor of nǫ with probability at least 1
poly(n)
unless
RP = NP.
3 Two Applications
In this section, we describe two applications of the results establish in Sect. 3 by
proving hardness and inapproximability of problems found in practice.
3.1 SAMBA Model is Hard
Microarray technology has been the latest technological breakthrough in biolog-
ical and biomedical research; in many applications, a key step in analyzing gene
expression data obtained through microarray is the identification of a bicluster
satisfying certain properties and with largest area (see the survey [13] for a fairly
extensive discussion on this).
In particular, Tanay et. al. [18] considered the Statistical-Algorithmic Method
for Bicluster Analysis (SAMBA) model. In their formulation, a complete bipar-
tite graph is given where one side corresponds to genes and the other size cor-
responds to conditions. An edges (u, v) is assigned a real weight which could be
either positive or negative, depending on the expression level of gene u in condi-
tion v, in a way such that heavy subgraphs corresponds to statistically significant
8 Jinsong Tan
biclusters. Two weight-assigning schemes are considered in their paper. In the
first, or simple statistical model, a tight upper-bound on the probability of an
observed biclusters in computed; in the second, or refined statistical model, the
weights are assigned in a way such that a maximum weight biclique subgraph
corresponds to a maximum likelihood bicluster.
The Simple SAMBA Statistical Model: LetH = (V ′1 , V
2 , E
′) be a subgraph
of G = (V1, V2, E), E′ = {V ′1 × V ′2} − E′ and p =
|V1||V2|
. The simple statistical
model assumes that edges occur independently and identically at random with
probability p. Denote by BT (k, p, n) the probability of observing k or more
successes in n binomial trials, the probability of observing a graph at least as
dense as H is thus p(H) = BT (|E′|, p, |V ′1 ||V ′2 |). This model assumes p < 12 and
|V ′1 ||V ′2 | ≪ |V1||V2|, therefore p(H) is upper bounded by
p∗(H) = 2|V
1 ||V
2 |p|E
′|(1− p)|V
1 ||V
2 |−|E
The goal of this model is thus to find a subgraph H with the smallest p∗(H).
This is equivalent to maximizing
− log p∗(H) = |E′|(−1− log p) + (|V ′1 ||V ′2 | − |E′|)(−1− log (1− p))
which is essentially solving a S-MWEB problem that assigns either positive
weight (−1 − log p) or negative weight (−1 − log (1 − p)) to an edge (u, v), de-
pending on whether gene u express or not in condition v, respectively. The
summation of edge weights over H is defined as the statistical significance of H .
Since 1
≤ p < 1
, asymptotically we have
−1−log (1−p)
−1−log p
∈ Ω( 1
log η
) ∩ O(1).
Invoking Theorem 5 gives the following.
Theorem 6. For the Simple SAMBA Statistical model, there exists some ǫ > 0
such that no polynomial time algorithm, possibly randomized, can find a bicluster
whose statistical significance is within a factor of nǫ of optimal unless RP = NP.
The Refined SAMBA Statistical Model: In the refined model, each edge
(u, v) is assumed to take an independent Bernoulli trial with parameter pu,v,
therefore p(H) = (
(u,v)∈E′ pu,v)(
(u,v)∈E′(1 − pu,v)) is the probability of ob-
serving a subgraph H . Since p(H) generally decreases as the size of H increases,
Tanay et al. aims to find a bicluster with the largest (normalized) likelihood ra-
tio L(H) =
(u,v)∈E′ pc)(
(u,v)∈E′(1− pc))
, where pc > max(u,v)∈E pu,v is a
constant probability and chosen with biologically sound assumptions. Note this
is equivalent to maximizing the log-likelihood ratio
logL(H) =
(u,v)∈E′
(u,v)∈E′
1− pc
1− pu,v
With this formulation, each edge is assigned weight either log pc
> 0 or
log 1−pc
1−pu,v
< 0 and finding the most statistically significant bicluster is equiva-
lent to solving S-MWEB with S = {log 1−pc
1−pu,v
, log pc
}. Since pc is a constant
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 9
and 1
≤ pu,v < pc, we have log (1−pc)−log (1−pu,v)log pc−log pu,v ∈ Ω(
log η
) ∩ O(1). Invoking
Theorem 5 gives the following.
Theorem 7. For the Refined SAMBA Statistical model, there exists some ǫ > 0
such that no polynomial time algorithm, possibly randomized, can find a bicluster
whose log-likelihood is within a factor of nǫ of optimal unless RP = NP.
3.2 Minimum Description Length with Holes (MDLH) is Hard
Bu et. al [4] considered the Minimum Description Length with Holes problem
(defined in the following); the 2-dimensional case is claimed NP-hard in this
paper and the proof is referred to [3]. However, the proof given in [3] suffers
from an error in its reduction3, thus whether MDLH is NP-complete remains
unsettled. In this section, by employing the results established in the previous
sections, we show that no polynomial time algorithm exists for MDLH, under
the slightly weaker (than P 6= NP) but widely believed assumption RP 6= NP.
We first briefly describe the Minimum Description Length summarization
with Holes problem; for a detailed discussion of the subject, we refer the readers
to [3,4].
Suppose one is given a k-dimensional binary matrix M , where each entry is
of value either 1, which is of interest, or of value 0, which is not of interest. Be-
sides, there are also k hierarchies (trees) associated with each dimension, namely
T1, T2, ..., Tk, each of height l1, l2, ..., lk respectively. Define level l = maxi(li).
For each Ti, there is a bijection between its leafs and the ’hyperplanes’ in the
ith dimension (e.g. in a 2-dimensional matrix, these hyperplanes corresponds to
rows and columns). A region is a tuple (x1, x2, ..., xk), where xi is a leaf node
or an internal node in hierarchy Ti. Region (x1, x2, ..., xk) is said to cover cell
(c1, c2, ..., ck) if ci is a descendant of xi, for all 1 ≤ i ≤ k. A k-dimensional l-level
MDLH summary is defined as two sets S and H , where 1) S is a set of regions
covering all the 1-entries in M ; and 2) H is the set of 0-entries covered (unde-
sirably) by S and to be excluded from the summary. The length of a summary
is defined as |S|+ |H |, and the MDLH problem asks the question if there exists
a MDLH summary of length at most K, for a given K > 0.
In an effort to establish hardness of MDLH, we first define the following
problem, which serves as an intermediate problem bridging {−1, 1}-MWEB and
MDLH.
Definition 3. (Problem P)
Instance: A complete bipartite graph G = (V1, V2, E) where each edge takes on
a value in {−1, 1}, and a positive integer k.
Question: Does there exist an induced subgraph (a biclique U1 × U2) whose
total weight of edges is ω, such that |U1|+ |U2|+ ω ≥ k.
Lemma 6. No polynomial time algorithm exists for Problem P unless RP = NP.
3 In Lemma 3.2.1 of [3], the reduction from CLIQUE to CEW is incorrect.
10 Jinsong Tan
Proof. We prove this by constructing a reduction from {−1, 1}-MWEB to Prob-
lem P as follows: for the given input biclique G = (V1, V2, E), make N duplicates
of V1 and N duplicates of V2, where N = (|V1| + |V2|)2. Connect each copy of
V1 to each copy of V2 in a way that is identical to the input biclique, we then
claim that there is a size k solution to {−1, 1}-MWEB if and only if there is a
size N2k solution to Problem P .
If there is a size k solution to {−1, 1}-MWEB, then it is straightforward that
there is a solution to Problem P of size at leastN2k. For the reverse direction, we
show that if no solution to {−1, 1}-MWEB is of size at least k, then the maximum
solution to Problem P is strictly less than N2k. Note a solution UN1 × UN2 to
Problem P consists of at most N2 (not necessarily all distinct) solutions to
{−1, 1}-MWEB, and each of them can contribute at most (k − 1) in weight to
UN1 ×UN2 , so the total weight gained from edges is at most N2(k− 1). And note
the total weight gained from vertices is at most N(|V1|+ |V2|) = N
N , therefore
the weight is upper bounded by N
N +N2(k − 1) < N2k and this completes
the proof.
As a conclusion, we have a polynomial time reduction from {−1, 1}-MWEB
to Problem P . Since no polynomial time algorithm exists for {−1, 1}-MWEB
unless RP = NP, the same holds for Problem P . ⊓⊔
Theorem 8. No polynomial time algorithm exists for MDLH summarization,
even in the 2-dimension 2-level case, unless RP = NP.
Proof. We prove this by showing that Problem P is a complementary problem
of 2-dimensional 2-level MDLH.
Let the input 2DmatrixM be of size n1×n2, with a tree of height 2 associated
with each dimension. Without loss of generality, we only consider the ’sparse’
case where the number of 1-entries is less than the number of 0-entries by at
least 2 so that the optimal solution will never contain the whole matrix as one
of its regions. Let S be the set of regions in a solution. Let R and C be the set
of rows and columns not included in S. Let Z be the set of all zero entries in M .
Let z be the total number of zero entries in the R × C ’leftover’ matrix and let
w be the total number of 1-entries in it. MDLH tries to minimize the following:
(n1 − |R|) + (n2 − |C|) + (|Z| − z) + w = (n1 + n2 + |Z|)− (|R|+ |C|+ z − w)
Since (n1 + n2 + |Z|) is a fixed quantity for any given input matrix, the 2-
dimensional 2-level MDLH problem is equivalent to maximizing (|R|+|C|+z−w),
which is precisely the definition of Problem P .
Therefore, 2-dimensional 2-level MDLH is a complementary problem to Prob-
lem P and by Lemma 6 we conclude that no polynomial time algorithm exists
for 2-dimensional 2-level MDLH unless RP = NP. ⊓⊔
4 Concluding Remarks
Maximum weighted edge biclique and its variants have received much atten-
tion in recently years because of it wide range of applications in various fields
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 11
including machine learning, database, and particularly bioinformatics and com-
putational biology, where many computational problems for the analysis of mi-
croarray data are closely related. To tackle these applied problems, various kinds
of heuristics are proposed and experimented and it is not known whether these
algorithms give provable approximations. In this work, we answer this question
by showing that it is highly unlikely (under the assumption RP 6= NP) that good
polynomial time approximation algorithm exists for maximum weighted edge
biclique for a wide range of choices of weight; and we further give specific appli-
cations of this result to two applied problems. We conclude our work by listing
a few open questions.
1. We have shown that {Θ(−ηδ), 1}-MWEB is nǫ-inapproximable for δ ∈
); also it is easy to see that (i) the problem is in P when δ ≤ −1, where
the entire input graph is the optimal solution; (ii) for any δ ≥ 1, the problem is
equivalent to MEB, which is conjectured to be nǫ-inapproximable [8]. Therefore
it is natural to ask what is the approximability of the {−nδ, 1}-MWEB problem
when δ ∈ (−1,− 1
] and δ ∈ [ 1
, 1]. In particular, can this be answered by a better
analysis of Lemma 3?
2. We are especially interested in {−1, 1}-MWEB, which is closely related
to the formulations of many natural problems [1,3,4,18]. We have shown that
no polynomial time algorithm exists for this problem unless RP = NP, and we
believe this problem is NP-complete, however a proof has eluded us so far.
References
1. N. Bansal, A. Blum, and S. Chawla. Correlation clustering, Machine Learning,
56:89-113, 2004.
2. A. Ben-Dor, B. Chor, R. Karp, and Z. Yakhini. Discovering local structure in
gene expression data: The Order-Preserving Submatrix Problem. In Proceedings of
RECOMB’02, 49-57, 2002.
3. S. Bu. The summarization of hierarchical data with exceptions. Master The-
sis, Department of Computer Science, University of British Columbia, 2004.
http://www.cs.ubc.ca/grads/resources/thesis/Nov04/Shaofeng Bu.pdf
4. S. Bu, L. V. S. Lakshmanan, R. T. Ng. MDL Summarization with Holes. In Pro-
ceedings of VLDB’05, 433-444, 2005.
5. Y. Cheng, and G. Church. Biclustering of expression data. In Proceedings of
ISMB’00, 93-103. AAAI Press, 2000.
6. M. Dawande, P. Keskinocak, J. M. Swaminathan, and S. Tayur. On Bipartite and
multipartite clique problems. Journal of Algorithms, 41(2):388-403, 2001.
7. U. Feige. Relations between average case complexity and approximation complex-
ity. In Proceedings of STOC’02, 534-543, 2002.
8. U. Feige and S. Kogan. Hardness of approximation of the Balanced Complete
Bipartite Subgraph problem. Technical Report MCS04-04, The Weizmann Institute
of Science, 2004.
9. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-completeness. Freeman, San Francisco, 1979.
10. P. Fontana, S. Guha and J. Tan. Recursive MDL Summarization and Approxima-
tion Algorithms. Preprint, 2007.
http://www.cs.ubc.ca/grads/resources/thesis/Nov04/Shaofeng_Bu.pdf
12 Jinsong Tan
11. J. H̊astad. Clique is hard to approximate within n1−ǫ. Acta Mathematica, 182:105-
142, 1999.
12. S. Khot. Ruling out PTAS for Graph Min-Bisection, Densest Subgraph and Bipar-
tite Clique. In Proceedings of FOCS’04, 136-145, 2004.
13. S. C. Madeira, and A. L. Oliveira. Biclustering algorithms for biological data anal-
ysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinfor-
matics, 1:24-45, 2004.
14. N. Mishra, D. Ron, and R. Swaminathan. On finding large conjunctive clusters. In
Proceedings of COLT’03, 448-462, 2003.
15. R. Peeters. The maximum edge biclique problem is NP-complete. Discrete Applied
Mathematics, 131:651-654, 2003.
16. J. M. Swaminathan and S. Tayur. Managing Broader Product Lines Through De-
layed Differentiation Using Vanilla Boxes. Management Science, 44:161-172, 1998.
17. J. Tan, K. Chua, L. Zhang, and S. Zhu. Algorithmic and Complexity Issues of
Three Clustering Methods in Microarray Data Analysis Algorithmica, 48(2): 203-
219, 2007.
18. A. Tanay, R. Sharan, and R. Shamir. Discovering statistically significant biclusters
in gene expression data. Bioinformatics, 18, Supplement 1:136-144, 2002.
19. L. Zhang, and S. Zhu. A New Clustering Method for Microarray Data Analysis.
In Proceedings of CSB’02, 268-275, 2002.
20. D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique
and Chromatic Number. In Proceedings of STOC’06, 681-690, 2006.
	Inapproximability of Maximum Weighted Edge Biclique and Its Applications
	Jinsong Tan

  Given a bipartite graph $G = (V_1,V_2,E)$ where edges take on {\it both}
positive and negative weights from set $\mathcal{S}$, the {\it maximum weighted
edge biclique} problem, or $\mathcal{S}$-MWEB for short, asks to find a
bipartite subgraph whose sum of edge weights is maximized. This problem has
various applications in bioinformatics, machine learning and databases and its
(in)approximability remains open. In this paper, we show that for a wide range
of choices of $\mathcal{S}$, specifically when $| \frac{\min\mathcal{S}} {\max
\mathcal{S}} | \in \Omega(\eta^{\delta-1/2}) \cap O(\eta^{1/2-\delta})$ (where
$\eta = \max\{|V_1|, |V_2|\}$, and $\delta \in (0,1/2]$), no polynomial time
algorithm can approximate $\mathcal{S}$-MWEB within a factor of $n^{\epsilon}$
for some $\epsilon > 0$ unless $\mathsf{RP = NP}$. This hardness result gives
justification of the heuristic approaches adopted for various applied problems
in the aforementioned areas, and indicates that good approximation algorithms
are unlikely to exist. Specifically, we give two applications by showing that:
1) finding statistically significant biclusters in the SAMBA model, proposed in
\cite{Tan02} for the analysis of microarray data, is
$n^{\epsilon}$-inapproximable; and 2) no polynomial time algorithm exists for
the Minimum Description Length with Holes problem \cite{Bu05} unless
$\mathsf{RP=NP}$.

Introduction
Let G = (V1, V2, E) be an undirected bipartite graph. A biclique subgraph in G
is a complete bipartite subgraph of G and maximum edge biclique (MEB) is the
problem of finding a biclique subgraph with the most number of edges. MEB is
a well-known problem and received much attention in recent years because of
its wide range of applications in areas including machine learning [14], manage-
ment science [16] and bioinformatics, where it is found particularly relevant in
the formulation of numerous biclustering problems for biological data analysis
[5,2,18,19,17], and we refer readers to the survey by Madeira and Oliveira [13]
for a fairly extensive discussion on this. Maximum edge biclique is shown to be
NP-hard by Peeters [15] via a reduction from 3SAT. Its approximability status,
on the other hand, remains an open question despite considerable efforts [7,8,12]
1. In particular, Feige and Kogan [8] conjectured that maximum edge biclique
1 Note it might be easy to confuse the MEB problem with the Bipartite Clique problem
discussed by Khot in [12]. Bipartite Clique, which also known as Balanced Complete
http://arxiv.org/abs/0704.0468v2
2 Jinsong Tan
is hard to approximate within a factor of nǫ for some ǫ > 0. In this paper, we
consider a weighted formulation of this problem defined as follows
Definition 1. S-Maximum Weighted Edge Biclique (S-MWEB)
Instance: A complete bipartite graph G = (V1, V2, E) (throughout the paper, let
η = max{|V1|, |V2|} and n = |V1|+ |V2|), a weight function wG : E → S, where
S is a set consisting of both positive and negative integers.
Question: Find a biclique subgraph of G where the sum of weights on edges is
maximized.
A few comments are in order. First note it is not a lose of generality but a
technical convenience to require the graph be complete, one can always think of
an incomplete bipartite graph as complete where non-edges are assigned weight
0. Also note we require that both positive and negative weights be in S at the
same time because otherwise S-MWEB becomes a trivial problem.
Our study of S-MWEB is motivated by the problem of finding statistically
significant biclusters in microarray data analysis in the SAMBA model [18]
and the Minimum Description Length with Holes (MDLH) problem [3,4,10];
detailed discussion of the two problems can be found in Sect. 4. Our main
technical contribution of this paper is to show that if S satisfies the condition
|minS
| ∈ Ω(ηδ−1/2) ∩O(η1/2−δ), where δ > 0 is any arbitrarily small constant,
then no polynomial time algorithm can approximate S-MWEB within a factor
of nǫ for some ǫ > 0 unless RP = NP. This result enables us to answer open
questions regarding the hardness of the SAMBA model and the MDLH prob-
lem. Since maximum edge biclique can be characterized as a special case of
S-MWEB with S = {−η, 1}, the nǫ-inapproximability result also provides inter-
esting insights into the conjectured nǫ-inapproximability [8] of maximum edge
biclique.
The rest of the paper is organized in three sections. In Sect. 2, we present
the main technical result by proving the aforementioned inapproximability of S-
MWEB. We give applications of this by answering hardness questions regarding
two applied problems in Sect. 3. We conclude this work by raising a few open
problems in the last section.
2 Approximating S-Maximum Edge Biclique is Hard
We start this section by giving two lemmas about CLIQUE, which will be used
in establishing inapproximability for the biclique problems we consider later.
Lemma 1 is a recent result by Zuckerman [20], obtained by a derandomization
of results of H̊astad [11]; Lemma 2 follows immediately from Lemma 1.
Lemma 1. ([20]) It is NP-hard to approximate CLIQUE within a factor of
n1−ǫ, for any ǫ > 0.
Bipartite Subgraph [8], aims to maximize the number of vertices of a balanced sub-
graph whereas MEB aims to maximize the total weights on edges in a (not necessarily
balanced) subgraph.
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 3
Lemma 2. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate CLIQUE within a factor of n1−ǫ with probability at least 1
poly(n)
unless
RP = NP.
2.1 A Technical Lemma
We first describe the construction of a structure called {γ, {α, β}}-Product,
which will be used in the proof of our main technical lemma.
Definition 2. ({γ, {α, β}}-Product)
Input: An instance of S-MWEB on complete bipartite graph G = V1×V2, where
γ ∈ S and α < γ < β; an integer N .
Output: Complete bipartite graph GN = V N1 × V N2 constructed as follows: V N1
and V N2 are N duplicates of V1 and V2, respectively. For each edge (i, j) ∈ GN ,
let (φ(i), φ(j)) be the corresponding edge in G. If wG(φ(i), φ(j)) = γ, assign
weight α or β to (i, j) independently and identically at random with expectation
being γ, denote the weight by random variable X. If wG(φ(i), φ(j)) 6= γ, then
keep the weight unchanged. Call the weight function constructed this way w(·).
For any subgraph H of GN , denote by wγ(H) (resp., w−γ(H)) the total
weight of H contributed by former-γ-edges (resp., other edges). Clearly, w(H) =
wγ(H) + w−γ(H).
With a graph product constructed in this randomized fashion, we have the fol-
lowing lemma.
Lemma 3. Given an S-MWEB instance G = (V1, V2, E) where γ ∈ S, and a
number δ ∈ (0, 1
]; let η = max (|V1|, |V2|), N = η
δ(3−2δ)+3
δ(1+2δ) , GN = (V N1 , V
2 , E)
be the {γ, {α, β}}-product of G and S ′ = (S ∪ {α, β})− {γ}. If
1. |β − α| = O((Nη) 12−δ); and
2. there is a polynomial time algorithm that approximates the S ′-MWEB
instance within a factor of λ, where λ is some arbitrary function in the size of
the S ′-MWEB instance
then there exists a polynomial time algorithm that approximates the S-MWEB
instance within a factor of λ, with probability at least 1
poly(n)
Proof. For notational convenience, we denote η
−δ by f(η) throughout the proof.
Define random variable Y = X − γ, clearly E[Y ] = 0. Suppose there is a poly-
nomial time algorithm A that approximates S ′-MWEB within a factor of λ, we
can then run A on GN , the output biclique G∗B corresponds to N
2 bicliques in
G (not necessarily all distinct). Let G∗A be the most weighted among these N
subgraphs of G, in the rest of the proof we show that with high probability, G∗A
is a λ-approximation of S-MWEB on G.
Denote by E1 the event that G
B does not imply a λ-approximation on G.
Let H be the set of subgraphs of GN that do not imply a λ-approximation on G,
4 Jinsong Tan
clearly, |H| ≤ 4Nη. Let H ′ be an arbitrary element in H, we have the following
inequalities
Pr {E1} ≤ Pr
at least one element in H is a λ-approximation of GN
≤ 4Nη · Pr
H ′ is a λ-approximation of GN
= 4Nη · Pr{E2}
where E2 is the event that H
′ is a λ-approximation of GN .
Let the weight of an optimal solution U1×U2 of G be K, denote by UN1 ×UN2
the correspondingN2-duplication in GN . Let x1 and x2 be the number of former-
γ-edges in H ′ and UN1 × UN2 , respectively. Suppose E2 happens, then we must
w−γ(H
′) + x1γ ≤ N2(Kλ − 1)
w−γ(H
′) + wγ(H
′) ≥ 1
(w−γ(U
1 × UN2 ) + wγ(UN1 × UN2 ))
where the first inequality follows from the fact that we only consider integer
weights. Since w−γ(U
1 × UN2 ) = N2K − x2γ, it implies
(wγ(H
′)− x1γ)−
(wγ(U
1 × UN2 )− x2γ) ≥ N2
so we have the following statement on probability
Pr{E2} ≤ Pr
(wγ(H
′)− x1γ)− 1λ(wγ(U
1 × UN2 )− x2γ) ≥ N2
Let z1 (resp., z2 and z3) be the number of edges in E(H
′) − E(UN1 × UN2 )
( resp., E(UN1 × UN2 ) − E(H ′) and E(UN1 × UN2 ) ∩ E(H ′) ) transformed from
former-γ-edges in G. We have
(wγ(H
′)− x1γ)− 1λ(wγ(U
1 × UN2 )− x2γ) ≥ N2
i=1 Yi −
j=1 Yj +
k=1 Yk ≥ N2
i=1 Yi +
j=1 (−Yj) +
k=1 Yk ≥ N2
i=1 Yi ≥
j=1 (−Yj) ≥
k=1 Yk ≥
i=1 Yi ≥
j=1 (−Yj) ≥
k=1 Yk ≥
i∈{1,2,3}
3zi(c1f(Nη))
(Hoeffding bound)
≤ 3 · exp
−c2 · N
η3−2δ
(zi ≤ η2N2)
where c1, c2 are constants (c2 > 0). Now if we set N = η
+θ for some θ, we
Pr {E1} ≤ 4Nη · Pr {E2} ≤ 3 · exp
ln 4 · η
(1+2δ)
+θ − c2 · η(1+2δ)θ
For this probability to be bounded by 1
as η is large enough, we need to have
+θ < (1+2δ)θ. Solving this inequality gives θ > 2
δ(1+2δ)
. Therefore, for any
δ ∈ (0, 1
], by setting N = η
δ(3−2δ)+3
δ(1+2δ) , we have Pr{E1}, i.e. the probability that
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 5
the solution returned by A does not imply a λ-approximation of G, is bounded
from above by 1
once input size is large enough. This gives a polynomial time
algorithm that approximates S-MWEB within a factor of λ with probability at
least 1
This lemma immediately leads to the following corollary.
Corollary 1. Following the construction in Lemma 3, if S ′-MWEB can be ap-
proximated within a factor of nǫ
, for some ǫ′ > 0, then there exists a polyno-
mial time algorithm that approximates S-MWEB within a factor of nǫ, where
ǫ = (1 +
δ(3−2δ)+3
δ(1+2δ)
)ǫ′, with probability at least 1
poly(n)
Proof. Let |G| and |GN | be the number of nodes in the S-MWEB and S ′-MWEB
problem, respectively. Since λ = |GN |ǫ′ ≤ |G|(1+
δ(3−2δ)+3
δ(1+2δ)
, our claim follows
from Lemma 3. ⊓⊔
2.2 {−1, 0, 1}-MWEB
In this section, we prove inapproximability of {−1, 0, 1}-MWEB by giving a
reduction from CLIQUE; in subsequence sections, we prove inapproximability
results for more general S-MWEB by constructing randomized reduction from
{−1, 0, 1}-MWEB.
Lemma 4. The decision version of the {−1, 0, 1}-MWEB problem is NP-complete.
Proof. We prove this by describing a reduction from CLIQUE. Given a CLIQUE
instance G = (V,E), construct G′ = (V ′, E′) such that V ′ = V1∪V2 where V1, V2
are duplicates of V in that there exist bijections φ1 : V1 → V and φ2 : V2 → V .
E′ = E1 ∪ E2 ∪E3
E1 = {(u, v) | u ∈ V1, v ∈ V2 and (φ1(u), φ2(v)) ∈ E}
E2 = {(u, v) | u ∈ V1, v ∈ V2, φ1(u) 6= φ2(v) and (φ1(u), φ2(v)) /∈ E}
E3 = {(u, v) | u ∈ V1, v ∈ V2, and φ1(u) = φ2(v)}
Clearly, G′ is a biclique. Now assign weight 0 to edges in E1, −1 to edges in
E2 and 1 to edges in E3. We then claim that there is a clique of size k in G if
and only if there is a biclique of total edge weight k in G′.
First consider the case where there is a clique of size k in G, let U be the set
of vertices of the clique, then taking the subgraph induced by φ−11 (U)× φ
2 (U)
in G′ gives us a biclique of total weight k.
Now suppose that there is a biclique U1×U2 of total weight k in G′. Without
loss of generality, assume U1 and U2 correspond to the same subset of vertices in
2 Note we are slightly abusing notation here by always representing the size of a given
problem under discussion by n. Here n refers to the size of S ′-MWEB (resp. S-
MWEB) when we are talking about approximation factor nǫ
(resp. nǫ). We adopt
the same convention in the sequel.
6 Jinsong Tan
V because if (φ1(U1)−φ2(U2))∪ (φ2(U2)−φ1(U1)) is not empty, then removing
(U1 −U2)∪ (U2 −U1) will never decrease the total weight of the solution. Given
φ1(U1) = φ2(U2), we argue that there is no edge of weight −1 in biclique U1×U2;
suppose otherwise there exists a weight −1 edge (i1, j2) (i1 ∈ U1, and j2 ∈ U2),
then the corresponding edge (j1, i2) (j1 ∈ U1, and i2 ∈ U2) must be of weight
−1 too and removing i1, i2 from the solution biclique will increase total weight
by at least 1 because among all edges incident to i1 and i2, (i1, i2) is of weight 1,
(i1, j2) and (i2, j1) are of weight −1 and the rest are of weights either 0 or −1.
Therefore, we have shown that if there is a solution U1 × U2 of weight k in
G′, U1 and U2 correspond to the same set of vertices U ∈ V and U is a clique of
size k. It is clear that the reduction can be performed in polynomial time and
the problem is NP, and thus NP-complete. ⊓⊔
Given Lemma 1, the following corollary follows immediately from the above
reduction.
Theorem 1. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate problem {−1, 0, 1}-MWEB within a factor of n1−ǫ unless P = NP.
Proof. It is obvious that the reduction given in the proof of Lemma 4 preserves
inapproximability exactly, and given that CLIQUE is hard to approximate within
a factor of n1−ǫ unless P = NP, the theorem follows. ⊓⊔
Theorem 2. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate {−1, 0, 1}-MWEB within a factor of n1−ǫ with probability at least 1
poly(n)
unless RP = NP.
Proof. If there exists such a randomized algorithm for {−1, 0, 1}-MWEB, com-
bining it with the reduction given in Lemma 4, we obtain an RP algorithm for
CLIQUE. This is impossible unless RP = NP. ⊓⊔
2.3 {−1, 1}-MWEB
Lemma 5. If there exists a polynomial time algorithm that approximates {−1, 1}-
MWEB within a factor of nǫ, then there exists a polynomial time algorithm that
approximates {−1, 0, 1}-MWEB within a factor of n5ǫ with probability at least
poly(n)
Proof. We prove this by constructing a {γ, {α, β}}-Product from {−1, 0, 1}-
MWEB to {−1, 1}-MWEB by setting γ = 0, α = −1 and β = 1. Since δ = 1
according to Corollary 1, it is sufficient to set N = η4 so that the probability of
obtaining a n5ǫ-approximation for {−1, 0, 1}-MWEB is at least 1
poly(n)
Theorem 3. For any constant ǫ > 0, no polynomial time algorithm can approx-
imate {−1, 1}-MWEB within a factor of n 15−ǫ with probability at least 1
poly(n)
unless RP = NP.
Proof. This follows directly from Theorem 2 and Lemma 5. ⊓⊔
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 7
2.4 {−η
, 1}-MWEB and {−ηδ−
2 , 1}-MWEB
In this section, we consider the generalized cases of the S-MWEB problem.
Theorem 4. For any δ ∈ (0, 1
], there exists some constant ǫ such that no poly-
nomial time algorithm can approximate {−η 12−δ, 1}-MWEB within a factor of
nǫ with probability at least 1
poly(n)
unless RP = NP. The same statement holds
for {−ηδ− 12 , 1}-MWEB.
Proof. We prove this by first construct a {γ, {α, β}}-Product from {−1, 1}-
MWEB to {−η 12−δ, 1}-MWEB by setting γ = −1, α = −(Nη) 12−δ and β = 1. By
Corollary 1, we know that for any δ ∈ (0, 1
], if there exists a polynomial time al-
gorithm that approximates {−η 12−δ, 1}-MWEB within a factor of nǫ, then there
exists a polynomial time algorithm that approximates {−1, 1}-MWEB within a
factor of n
δ(3−2δ)+3
δ(1+2δ)
with probability at least 1
poly(n)
. So invoking the hardness
result in Theorem 3 gives the desired hardness result for {−η 12−δ, 1}-MWEB.
The same conclusion applies to {−1, η 12−δ}-MWEB by setting γ = 1, α = −1
and β = (Nη)
−δ. Since η is a constant for any given graph, we can simply divide
each weight in {−1, η 12−δ} by η 12−δ. ⊓⊔
Theorem 4 leads to the following general statement.
Theorem 5. For any small constant δ ∈ (0, 1
], if
∣ ∈ Ω(ηδ−1/2)∩O(η1/2−δ),
then there exists some constant ǫ such that no polynomial time algorithm can ap-
proximate S-MWEB within a factor of nǫ with probability at least 1
poly(n)
unless
RP = NP.
3 Two Applications
In this section, we describe two applications of the results establish in Sect. 3 by
proving hardness and inapproximability of problems found in practice.
3.1 SAMBA Model is Hard
Microarray technology has been the latest technological breakthrough in biolog-
ical and biomedical research; in many applications, a key step in analyzing gene
expression data obtained through microarray is the identification of a bicluster
satisfying certain properties and with largest area (see the survey [13] for a fairly
extensive discussion on this).
In particular, Tanay et. al. [18] considered the Statistical-Algorithmic Method
for Bicluster Analysis (SAMBA) model. In their formulation, a complete bipar-
tite graph is given where one side corresponds to genes and the other size cor-
responds to conditions. An edges (u, v) is assigned a real weight which could be
either positive or negative, depending on the expression level of gene u in condi-
tion v, in a way such that heavy subgraphs corresponds to statistically significant
8 Jinsong Tan
biclusters. Two weight-assigning schemes are considered in their paper. In the
first, or simple statistical model, a tight upper-bound on the probability of an
observed biclusters in computed; in the second, or refined statistical model, the
weights are assigned in a way such that a maximum weight biclique subgraph
corresponds to a maximum likelihood bicluster.
The Simple SAMBA Statistical Model: LetH = (V ′1 , V
2 , E
′) be a subgraph
of G = (V1, V2, E), E′ = {V ′1 × V ′2} − E′ and p =
|V1||V2|
. The simple statistical
model assumes that edges occur independently and identically at random with
probability p. Denote by BT (k, p, n) the probability of observing k or more
successes in n binomial trials, the probability of observing a graph at least as
dense as H is thus p(H) = BT (|E′|, p, |V ′1 ||V ′2 |). This model assumes p < 12 and
|V ′1 ||V ′2 | ≪ |V1||V2|, therefore p(H) is upper bounded by
p∗(H) = 2|V
1 ||V
2 |p|E
′|(1− p)|V
1 ||V
2 |−|E
The goal of this model is thus to find a subgraph H with the smallest p∗(H).
This is equivalent to maximizing
− log p∗(H) = |E′|(−1− log p) + (|V ′1 ||V ′2 | − |E′|)(−1− log (1− p))
which is essentially solving a S-MWEB problem that assigns either positive
weight (−1 − log p) or negative weight (−1 − log (1 − p)) to an edge (u, v), de-
pending on whether gene u express or not in condition v, respectively. The
summation of edge weights over H is defined as the statistical significance of H .
Since 1
≤ p < 1
, asymptotically we have
−1−log (1−p)
−1−log p
∈ Ω( 1
log η
) ∩ O(1).
Invoking Theorem 5 gives the following.
Theorem 6. For the Simple SAMBA Statistical model, there exists some ǫ > 0
such that no polynomial time algorithm, possibly randomized, can find a bicluster
whose statistical significance is within a factor of nǫ of optimal unless RP = NP.
The Refined SAMBA Statistical Model: In the refined model, each edge
(u, v) is assumed to take an independent Bernoulli trial with parameter pu,v,
therefore p(H) = (
(u,v)∈E′ pu,v)(
(u,v)∈E′(1 − pu,v)) is the probability of ob-
serving a subgraph H . Since p(H) generally decreases as the size of H increases,
Tanay et al. aims to find a bicluster with the largest (normalized) likelihood ra-
tio L(H) =
(u,v)∈E′ pc)(
(u,v)∈E′(1− pc))
, where pc > max(u,v)∈E pu,v is a
constant probability and chosen with biologically sound assumptions. Note this
is equivalent to maximizing the log-likelihood ratio
logL(H) =
(u,v)∈E′
(u,v)∈E′
1− pc
1− pu,v
With this formulation, each edge is assigned weight either log pc
> 0 or
log 1−pc
1−pu,v
< 0 and finding the most statistically significant bicluster is equiva-
lent to solving S-MWEB with S = {log 1−pc
1−pu,v
, log pc
}. Since pc is a constant
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 9
and 1
≤ pu,v < pc, we have log (1−pc)−log (1−pu,v)log pc−log pu,v ∈ Ω(
log η
) ∩ O(1). Invoking
Theorem 5 gives the following.
Theorem 7. For the Refined SAMBA Statistical model, there exists some ǫ > 0
such that no polynomial time algorithm, possibly randomized, can find a bicluster
whose log-likelihood is within a factor of nǫ of optimal unless RP = NP.
3.2 Minimum Description Length with Holes (MDLH) is Hard
Bu et. al [4] considered the Minimum Description Length with Holes problem
(defined in the following); the 2-dimensional case is claimed NP-hard in this
paper and the proof is referred to [3]. However, the proof given in [3] suffers
from an error in its reduction3, thus whether MDLH is NP-complete remains
unsettled. In this section, by employing the results established in the previous
sections, we show that no polynomial time algorithm exists for MDLH, under
the slightly weaker (than P 6= NP) but widely believed assumption RP 6= NP.
We first briefly describe the Minimum Description Length summarization
with Holes problem; for a detailed discussion of the subject, we refer the readers
to [3,4].
Suppose one is given a k-dimensional binary matrix M , where each entry is
of value either 1, which is of interest, or of value 0, which is not of interest. Be-
sides, there are also k hierarchies (trees) associated with each dimension, namely
T1, T2, ..., Tk, each of height l1, l2, ..., lk respectively. Define level l = maxi(li).
For each Ti, there is a bijection between its leafs and the ’hyperplanes’ in the
ith dimension (e.g. in a 2-dimensional matrix, these hyperplanes corresponds to
rows and columns). A region is a tuple (x1, x2, ..., xk), where xi is a leaf node
or an internal node in hierarchy Ti. Region (x1, x2, ..., xk) is said to cover cell
(c1, c2, ..., ck) if ci is a descendant of xi, for all 1 ≤ i ≤ k. A k-dimensional l-level
MDLH summary is defined as two sets S and H , where 1) S is a set of regions
covering all the 1-entries in M ; and 2) H is the set of 0-entries covered (unde-
sirably) by S and to be excluded from the summary. The length of a summary
is defined as |S|+ |H |, and the MDLH problem asks the question if there exists
a MDLH summary of length at most K, for a given K > 0.
In an effort to establish hardness of MDLH, we first define the following
problem, which serves as an intermediate problem bridging {−1, 1}-MWEB and
MDLH.
Definition 3. (Problem P)
Instance: A complete bipartite graph G = (V1, V2, E) where each edge takes on
a value in {−1, 1}, and a positive integer k.
Question: Does there exist an induced subgraph (a biclique U1 × U2) whose
total weight of edges is ω, such that |U1|+ |U2|+ ω ≥ k.
Lemma 6. No polynomial time algorithm exists for Problem P unless RP = NP.
3 In Lemma 3.2.1 of [3], the reduction from CLIQUE to CEW is incorrect.
10 Jinsong Tan
Proof. We prove this by constructing a reduction from {−1, 1}-MWEB to Prob-
lem P as follows: for the given input biclique G = (V1, V2, E), make N duplicates
of V1 and N duplicates of V2, where N = (|V1| + |V2|)2. Connect each copy of
V1 to each copy of V2 in a way that is identical to the input biclique, we then
claim that there is a size k solution to {−1, 1}-MWEB if and only if there is a
size N2k solution to Problem P .
If there is a size k solution to {−1, 1}-MWEB, then it is straightforward that
there is a solution to Problem P of size at leastN2k. For the reverse direction, we
show that if no solution to {−1, 1}-MWEB is of size at least k, then the maximum
solution to Problem P is strictly less than N2k. Note a solution UN1 × UN2 to
Problem P consists of at most N2 (not necessarily all distinct) solutions to
{−1, 1}-MWEB, and each of them can contribute at most (k − 1) in weight to
UN1 ×UN2 , so the total weight gained from edges is at most N2(k− 1). And note
the total weight gained from vertices is at most N(|V1|+ |V2|) = N
N , therefore
the weight is upper bounded by N
N +N2(k − 1) < N2k and this completes
the proof.
As a conclusion, we have a polynomial time reduction from {−1, 1}-MWEB
to Problem P . Since no polynomial time algorithm exists for {−1, 1}-MWEB
unless RP = NP, the same holds for Problem P . ⊓⊔
Theorem 8. No polynomial time algorithm exists for MDLH summarization,
even in the 2-dimension 2-level case, unless RP = NP.
Proof. We prove this by showing that Problem P is a complementary problem
of 2-dimensional 2-level MDLH.
Let the input 2DmatrixM be of size n1×n2, with a tree of height 2 associated
with each dimension. Without loss of generality, we only consider the ’sparse’
case where the number of 1-entries is less than the number of 0-entries by at
least 2 so that the optimal solution will never contain the whole matrix as one
of its regions. Let S be the set of regions in a solution. Let R and C be the set
of rows and columns not included in S. Let Z be the set of all zero entries in M .
Let z be the total number of zero entries in the R × C ’leftover’ matrix and let
w be the total number of 1-entries in it. MDLH tries to minimize the following:
(n1 − |R|) + (n2 − |C|) + (|Z| − z) + w = (n1 + n2 + |Z|)− (|R|+ |C|+ z − w)
Since (n1 + n2 + |Z|) is a fixed quantity for any given input matrix, the 2-
dimensional 2-level MDLH problem is equivalent to maximizing (|R|+|C|+z−w),
which is precisely the definition of Problem P .
Therefore, 2-dimensional 2-level MDLH is a complementary problem to Prob-
lem P and by Lemma 6 we conclude that no polynomial time algorithm exists
for 2-dimensional 2-level MDLH unless RP = NP. ⊓⊔
4 Concluding Remarks
Maximum weighted edge biclique and its variants have received much atten-
tion in recently years because of it wide range of applications in various fields
Inapproximability of Maximum Weighted Edge Biclique and Its Applications 11
including machine learning, database, and particularly bioinformatics and com-
putational biology, where many computational problems for the analysis of mi-
croarray data are closely related. To tackle these applied problems, various kinds
of heuristics are proposed and experimented and it is not known whether these
algorithms give provable approximations. In this work, we answer this question
by showing that it is highly unlikely (under the assumption RP 6= NP) that good
polynomial time approximation algorithm exists for maximum weighted edge
biclique for a wide range of choices of weight; and we further give specific appli-
cations of this result to two applied problems. We conclude our work by listing
a few open questions.
1. We have shown that {Θ(−ηδ), 1}-MWEB is nǫ-inapproximable for δ ∈
); also it is easy to see that (i) the problem is in P when δ ≤ −1, where
the entire input graph is the optimal solution; (ii) for any δ ≥ 1, the problem is
equivalent to MEB, which is conjectured to be nǫ-inapproximable [8]. Therefore
it is natural to ask what is the approximability of the {−nδ, 1}-MWEB problem
when δ ∈ (−1,− 1
] and δ ∈ [ 1
, 1]. In particular, can this be answered by a better
analysis of Lemma 3?
2. We are especially interested in {−1, 1}-MWEB, which is closely related
to the formulations of many natural problems [1,3,4,18]. We have shown that
no polynomial time algorithm exists for this problem unless RP = NP, and we
believe this problem is NP-complete, however a proof has eluded us so far.
References
1. N. Bansal, A. Blum, and S. Chawla. Correlation clustering, Machine Learning,
56:89-113, 2004.
2. A. Ben-Dor, B. Chor, R. Karp, and Z. Yakhini. Discovering local structure in
gene expression data: The Order-Preserving Submatrix Problem. In Proceedings of
RECOMB’02, 49-57, 2002.
3. S. Bu. The summarization of hierarchical data with exceptions. Master The-
sis, Department of Computer Science, University of British Columbia, 2004.
http://www.cs.ubc.ca/grads/resources/thesis/Nov04/Shaofeng Bu.pdf
4. S. Bu, L. V. S. Lakshmanan, R. T. Ng. MDL Summarization with Holes. In Pro-
ceedings of VLDB’05, 433-444, 2005.
5. Y. Cheng, and G. Church. Biclustering of expression data. In Proceedings of
ISMB’00, 93-103. AAAI Press, 2000.
6. M. Dawande, P. Keskinocak, J. M. Swaminathan, and S. Tayur. On Bipartite and
multipartite clique problems. Journal of Algorithms, 41(2):388-403, 2001.
7. U. Feige. Relations between average case complexity and approximation complex-
ity. In Proceedings of STOC’02, 534-543, 2002.
8. U. Feige and S. Kogan. Hardness of approximation of the Balanced Complete
Bipartite Subgraph problem. Technical Report MCS04-04, The Weizmann Institute
of Science, 2004.
9. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-completeness. Freeman, San Francisco, 1979.
10. P. Fontana, S. Guha and J. Tan. Recursive MDL Summarization and Approxima-
tion Algorithms. Preprint, 2007.
http://www.cs.ubc.ca/grads/resources/thesis/Nov04/Shaofeng_Bu.pdf
12 Jinsong Tan
11. J. H̊astad. Clique is hard to approximate within n1−ǫ. Acta Mathematica, 182:105-
142, 1999.
12. S. Khot. Ruling out PTAS for Graph Min-Bisection, Densest Subgraph and Bipar-
tite Clique. In Proceedings of FOCS’04, 136-145, 2004.
13. S. C. Madeira, and A. L. Oliveira. Biclustering algorithms for biological data anal-
ysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinfor-
matics, 1:24-45, 2004.
14. N. Mishra, D. Ron, and R. Swaminathan. On finding large conjunctive clusters. In
Proceedings of COLT’03, 448-462, 2003.
15. R. Peeters. The maximum edge biclique problem is NP-complete. Discrete Applied
Mathematics, 131:651-654, 2003.
16. J. M. Swaminathan and S. Tayur. Managing Broader Product Lines Through De-
layed Differentiation Using Vanilla Boxes. Management Science, 44:161-172, 1998.
17. J. Tan, K. Chua, L. Zhang, and S. Zhu. Algorithmic and Complexity Issues of
Three Clustering Methods in Microarray Data Analysis Algorithmica, 48(2): 203-
219, 2007.
18. A. Tanay, R. Sharan, and R. Shamir. Discovering statistically significant biclusters
in gene expression data. Bioinformatics, 18, Supplement 1:136-144, 2002.
19. L. Zhang, and S. Zhu. A New Clustering Method for Microarray Data Analysis.
In Proceedings of CSB’02, 268-275, 2002.
20. D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique
and Chromatic Number. In Proceedings of STOC’06, 681-690, 2006.
	Inapproximability of Maximum Weighted Edge Biclique and Its Applications
	Jinsong Tan
