# Partition of a Binary Matrix intok (k

Authors: Peiqiang Liu; Daming Zhu; Jinjie Xiao; Qingsong Xie; Yanyan Mao
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

A biclustering problem consists of objects and an attribute vector for each object. Biclustering aims at finding a bicluster—a subset of objects that exhibit similar behavior across a subset of attributes, or vice versa. Biclustering in matrices with binary entries (“0”/“1”) can be simplified into the problem of finding submatrices with entries of “1.” In this paper, we consider a variant of the biclustering problem: thek-submatrix partition of binary matrices problem. The input of the problem contains an n
×
m matrix with entries (“0”/“1”) and a constant positive integer k. The k-submatrix partition of binary matrices problem is to find exactly k submatrices with entries of “1” such that these k submatrices are pairwise row and column exclusive and each row (column) in the matrix occurs in exactly one of the k submatrices. We discuss the complexity of the k-submatrix partition of binary matrices problem and show that the problem is NP-hard for any k
≥
3 by reduction from a biclustering problem in bipartite graphs.


---

## Body

## 1. Introduction

The problems considered in this paper are biclustering problems. Biclustering is an important optimization problem with applications in many fields including bioinformatics (especially in gene expression data analysis), identifying web communities, network information security analysis, and many more [1–3]. Biclustering is also known as block clustering, coclustering, or two-way clustering. The earliest biclustering algorithm that can be found in the literature is the so-called direct clustering by Hartigan in the 1970s [4, 5]. Since then, many approaches to biclustering have been proposed, such as the direct clustering algorithm [4], the node-deletion algorithm [6], the FLOC algorithm [7], the biclustering via spectral bipartite graph partitioning algorithm [8], the biclustering via GIBBS sampling algorithm [9], and the algorithm for finding an order-preserving submatrix [10]. For more on biclustering, see [3, 11, 12].The basic model for biclustering is as follows. Let a dataset ofm objects and n attributes be given as a matrix A
=
[
a
i
j
]
m
*
n, where the value of a
i
j is the value of the jth attribute of the ith object; the simplest aim of biclustering is to find a subset of rows (objects) that exhibit similar behavior across a subset of columns (attributes), or vice versa. In this case, the combination of the subset of objects and the subset of attributes is called a bicluster. A bicluster forms a contiguous rectangle after an appropriate reordering of rows and columns; that is, a bicluster is a submatrix of A.In some applications, the main goal of biclustering is to simultaneously find many submatrices (biclusters) in a matrix. Madeira and Oliveira discussed this issue and summarized eight biclustering patterns [11]. Five of these patterns are presented in Figure 1: (1) exclusive row and column biclusters (Figure 1(a)), with each row (column) occurring in exactly one bicluster; (2) exclusive row biclusters (Figure 1(b)), with each row occurring in exactly one bicluster and each column occurring in at least one bicluster; (3) exclusive column biclusters (Figure 1(c)), with each column occurring in exactly one bicluster and each row occurring in at least one bicluster; (4) checkerboard structure (Figure 1(d)), with each entry of the matrix occurring in exactly one bicluster; and (5) arbitrarily positioned overlapping biclusters (Figure 1(e)), with no limiting condition of rows (columns) overlapping or entries overlapping.Biclustering patterns: (a) exclusive row and column biclusters, (b) exclusive row biclusters, (c) exclusive column biclusters, (d) checkerboard structure, and (e) arbitrarily positioned overlapping biclusters.
(a)
(b)
(c)
(d)
(e)In many applications, a biclustering problem consists of a matrix that has entries of “1” or “0,” which is also called a binary matrix. The goal of biclustering in binary matrices is to find submatrices with entries of “1.” For example, when applying biclustering to text mining, a dataset ofm documents and n words is arranged in a binary matrix A
=
[
a
i
j
]
m
*
n, where rows correspond to documents and columns correspond to words. If an entry (i, j
) of the matrix is “1,” then word j is present in document i. If the entry is “0,” then the word is not present. The question is whether we can find k submatrices with entries of “1” such that these submatrices are pairwise row and column exclusive, and each row (column) occurs in exactly one submatrix. Clearly, if the answer is “yes,” then these documents can be partitioned into k groups, and documents in the same group have a good chance of belonging to the same domain.The text mining problem described above can be abstracted as thek-submatrix partition of binary matrices problem (k-SPBM). Given an n
×
m binary matrix and a constant positive integer k, k-SPBM is to find k submatrices with entries “1” such that these k submatrices are pairwise row and column exclusive and each row (column) of the matrix occurs in exactly one of these submatrices. The bicluster pattern of k-SPBM belongs to pattern (a) in Figure 1. To the best of our knowledge, the hardness of k-SPBM remains an open problem, for each k
≥
3.We will show thatk-SPBM is NP-complete by reduction from the partition of a bipartite graph into k bicliques problem (k-PBB) that is a variant of biclustering problems in bipartite graphs; that is, an instance of k-PBB is a bipartite graph. A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets such that no two graph vertices within the same set are adjacent. For a biclustering problem in bipartite graphs, the goal is to find bicliques according to some scoring criterion. A biclique, which is also called a complete bipartite graph, is a special type of bipartite graph for which every pair of vertices in the two sets are adjacent.In recent years, much study has focused on algorithms and complexity of biclustering problems in bipartite graphs. Peeters, Dawande et al., and Amit proved that the maximum edge biclique problem [13], the maximum edge weight biclique problem [14], the bicluster graph editing problem [15], the exact cardinality biclique problem [16], and the minimum edge deletion biclique problem [16], among others, are NP-complete.When Heydari et al. studied the biclustering of an attack graph problem in information security, they first proposed the partition of a bipartite graph into bicliques problem (PBB). Heydari et al. showed that PBB is NP-complete [17]. Furthermore, Bein et al. discussed the k-PBB problem, where k is a constant positive integer. Here, k-PBB is a parameterized version of PBB; it aims at partitioning the vertex set of a bipartite graph into k subsets such that each vertex subset can induce a biclique. k-PBB defines a family of problems for any k
≥
3. Bein et al. first proposed the k-PBB problem and indicated that the question of whether k-PBB is NP-complete for k
≥
3 remains open [18].Contribution of this paper is that it focuses on the complexity of several biclustering problems. The main result shows that 3-PBB,k-PBB (k
>
3), and k-SPBM (k
≥
3) are all NP-complete.Organization of the paper is as follows: in Section2, we introduce the k-PBB and k-SPBM problems. In Section 3, we first show that 3-PBB is NP-complete by reduction from a variant of the monotone one-in-three 3SAT problem (MO3), which is a well-known NP-complete problem [19, 20], and, then, we show that k-PBB (k
>
3) is NP-complete by reduction from 3-PBB. In Section 4, we prove that k-SPBM (k
≥
3) is NP-complete by reduction from k-PBB. Finally, in Section 6, we present our conclusions.


## 2. Preliminaries

In this paper, we study two problems: thek-SPBM problem and the k-PBB problem. Next, we present the formal descriptions of k-SPBM and k-PBB.(1) Thek-submatrix partition of binary matrices problem (k-SPBM).The input to thek-SPBM problem is typically a binary matrix. Let A
=
[
a
i
j
]
m
*
n be an n
×
m binary matrix. Denote the set of row vectors and the set of column vectors by R
=
{
1
,
…
,
m
} and C
=
{
1
,
…
,
n
}, respectively. Suppose R
1
⊑
R and C
1
⊑
C; then the public entries of row vectors {
α
i
∣
a
i
j
∈
α
i
,
i
∈
R
1
,
j
∈
C
} and column vectors {
β
j
∣
a
i
j
∈
β
j
,
i
∈
R
,
j
∈
C
1
} form a matrix [
a
i
j
:
i
∈
R
1
,
j
∈
C
1
] that is called a submatrix of A induced by R
1 and C
1, which is denoted by A
[
R
1
,
C
1
]. Clearly, A
=
A
[
R
,
C
]. Let A
1
=
A
[
R
1
,
C
1
], A
2
=
A
[
R
2
,
C
2
] be submatrices of A. If R
1
∩
R
2
=
∅, then A
1 and A
2 are row exclusive; if C
1
∩
C
2
=
∅, then A
1 and A
2 are column exclusive. k-SPBM is to find exactly k exclusive row and column submatrices with entries of “1” in a binary matrix. The k-SPBM problem can be stated formally as follows.Instance: anm
×
n binary matrix A, and a constant positive integer k.
Question: are therek submatrices with entries “1” A
[
R
1
,
C
1
]
,
…
,
A
[
R
k
,
C
k
] of A such that the k submatrices are pairwise row and column exclusive, and R
1
∪
⋯
∪
R
k
=
{
1,2
,
…
,
m
},  C
1
∪
⋯
∪
C
k
=
{
1,2
,
…
,
n
}?A
[
R
1
,
C
1
]
,
…
,
A
[
R
k
,
C
k
] are called a k-submatrix partition of A.(2) The partition of a bipartite graph intok-bicliques problem (k-PBB).An instance ofk-PBB is a bipartite graph. All bipartite graphs in the paper are simple bipartite graphs, that is, do not contain parallel edges or self-loops. Let G
=
(
X
,
Y
,
E
) be a bipartite graph. For convenience in writing, vertices in X are called left-vertices, and vertices in Y are called right-vertices of G. In other words, X and Y are the left-vertex set and right-vertex set of G, respectively. We denote by E
(
G
) and V
(
G
) its set of edges and its set of vertices, respectively. For a vertex v
∈
V
(
G
), we denote the set of neighbors of vertex v by Γ
(
v
). A biclique in G corresponds to a subset of V
(
G
), say, C
=
A
∪
B, such that A
⊆
X, B
⊆
Y, and for each u
∈
A, v
∈
B the edge (
u
,
v
)
∈
E.We say that there exists ak-biclique partition for a bipartite graph G if V
(
G
) can be partitioned into exactly k disjoint sets V
1
,
V
2
,
…
,
V
k such that, for 1
≤
i
≤
k, the subgraph induced by V
i is a biclique. The k-PBB problem is the problem of determining whether there is a k-biclique partition for a bipartite graph G, where k is a constant positive integer. The k-PBB problem can be stated formally as follows.Instance: a finite bipartite graphG
=
(
X
,
Y
,
E
) and a constant positive integer k
≤
min
⁡
{
|
X
|
,
|
Y
|
}.
Question: does there exist ak-biclique partition for G?


## 3. The Complexity ofk-PBB

In this section, we first show the NP-completeness ofk-PBB when k
=
3 (i.e., 3-PBB). We then show that k-PBB is NP-complete for any constant integer k
(
k
>
3
) by reduction from 3-PBB. Finally, we conclude that k-PBB is NP-complete for any constant integer k
(
k
≥
3
).


### 3.1. The NP-Completeness of 3-PBB

In order to prove the hardness of 3-PBB, we first introduce the monotone one-in-three 3SAT problem (MO3), which was proved to be NP-complete by Schaefer in 1978 [19]. Then, we show that a variant of MO3 is NP-complete. Finally, we prove that 3-PBB is NP-complete by reduction from MO3.Below we define the terms we will use in describing MO3. LetU
=
{
u
1
,
u
2
,
…
,
u
n
} be a set of Boolean variables. If u
i
∈
U, then u
i and u
-
i are literals over U. u
i is called a positive variable, and u
-
i is called a negative variable. A truth assignment for U is a function t
:
→
T
,
F. For u
i
∈
U, if t
(
u
i
)
=
F, we say that u
i is “TRUE” under t; if f
(
u
i
)
=
F, we say that u
i is “FALSE.”The MO3 problem, which is a variant of 3SAT, is specified as follows.Instance: setU
=
{
u
1
,
u
2
,
…
,
u
n
} of Boolean variables, collection C
=
{
c
1
,
c
2
,
…
,
c
m
} of clauses over U, where each clause c
∈
C has |
c
|
=
3, and c does not contain a negative variable; that is, c
i
=
{
u
x
,
u
y
,
u
z
}
,
u
x
,
u
y
,
u
z
∈
U,   1
≤
i
≤
m.
Question: is there a truth assignment forU such that each clause in C has exactly one true literal?In the MO3 problem, a clause overU contains only positive variables. For an MO3 instance, a clause over U is satisfied by a truth assignment if and only if it has exactly one “TRUE” literal (and thus exactly two “FALSE” literals) under the assignment. A collection C of clauses over U is satisfiable if and only if there exists a truth assignment for U that simultaneously satisfies all the clauses in C.For example, we are given Boolean variable setU
=
{
u
1
,
u
2
,
u
3
,
u
4
}, and a clause collection C
=
{
c
1
,
c
2
,
c
3
,
c
4
}, where c
1
=
{
u
1
,
u
2
,
u
3
}, c
2
=
{
u
2
,
u
3
,
u
4
} and c
3
=
{
u
1
,
u
2
,
u
4
}. Let [
a
(
u
1
)
,
a
(
u
2
)
,
a
(
u
3
)
,
a
(
u
4
)
]
=
[
F
,
T
,
F
,
F
]; then, the values of the variables in c
1, c
2, and c
3 are (
F
,
T
,
F
),    (
T
,
F
,
F
), and (
F
,
T
,
F
), which means that c
1, c
2, and c
3 are satisfied. Therefore, a
(
·
) is a feasible solution of this MO3 instance.For an arbitrary MO3 instance, we can assume that the three literals in each clause are not from the same variable, in which case the clause is not satisfied. Moreover, a clause in which two literals are from the same variable can be transformed into six clauses with pairwise different variables. The approach is as follows.Suppose thatc
k
=
{
u
i
,
u
i
,
u
j
} is a clause of an MO3 instance. We create four new variables u
i
1, u
i
2, u
i
3, and u
i
4. Then, we construct six clauses over u
i, u
j, and the four new variables: c
k
[
1
]
=
{
u
i
1
,
u
i
2
,
u
i
3
}, c
k
[
2
]
=
{
u
i
1
,
u
i
2
,
u
i
}, c
k
[
3
]
=
{
u
i
2
,
u
i
3
,
u
i
}, c
k
[
4
]
=
{
u
i
1
,
u
i
2
,
u
i
4
}, c
k
[
5
]
=
{
u
i
2
,
u
i
3
,
u
i
4
}, and c
k
[
6
]
=
{
u
i
,
u
i
4
,
u
j
}. Clearly, the clause {
u
i
,
u
i
,
u
j
} is satisfied if and only if a
(
u
i
)
=
F and a
(
u
j
)
=
T. Moreover, a truth assignment for the variables u
i
1, u
i
2, u
i
3, and u
i
4 exists such that each clause in c
k[1~6] is satisfied if and only if a
(
u
i
)
=
F and a
(
u
j
)
=
T.Thus, an arbitrary MO3 instance can be transformed into an MO3 instance with pairwise different variables in each clause in polynomial time. Therefore, we have Theorem1.Theorem 1.
MO3 with pairwise different variables in each clause is NP-complete.Throughout this paper, we assume without loss of generality that, for an instance of MO3, the three literals of each clause are pairwise different. Next, we discuss the complexity of 3-PBB; that is, we prove Theorem2.Theorem 2.
3-PBB is NP-complete.The proof of Theorem2 consists of two steps. First, let a variable set U
=
{
u
1
,
u
2
,
…
,
u
n
} and a clause collection C
=
{
c
1
,
c
2
,
…
,
c
m
} be an instance of MO3; then we build a bipartite graph B
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
) that is an instance of 3-PBB. Second, we show that C is satisfied if and only if there exists a 3-biclique partition for B.


#### 3.1.1. The Construction of a Bipartite GraphB from an MO3 Instance

Given an instance of MO3, we build a bipartite graphB that is an instance of 3-PBB in three steps. In the first step, we construct three components T
i
1, T
i
2, and T
i
3 from the clause c
i
(
1
≤
i
≤
m
). In the second step, we merge T
i
1, T
i
2, and T
i
3 into a bipartite graph B
i. In the final step, we merge m
B
i’s into a bipartite graph B.Step 1.
For each clausec
i
∈
C, we construct three components that are associated with the three literals in c
i. Each of these components is a bipartite graph.
Suppose thatc
i
=
{
u
x
,
u
y
,
u
z
}
∈
C. Thus, we construct the components T
i
1, T
i
2, and T
i
3. The three components contain vertices u
x, u
y, and u
z, which correspond to the variables u
x, u
y, and u
z of c
i, respectively. In the following, we will indiscriminately use the notation u
x, u
y, or u
z to represent a vertex or a variable.
The key idea used in this step of construction is that each of the three components contains a bipartite subgraph isomorphic toB
c illustrated in Figure 2. Moreover, for an arbitrary 3-biclique partition of T
i
j (j
∈
{
1,2
,
3
}), the structure of T
i
j ensures that (1)
{
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques,
(2)
u
x, u
y, or u
z only belongs to those bicliques that contain {
l
0
,
r
0
} or {
l
1
,
r
1
}.Figure 2
B
c.This is our basic way of encoding the idea thatu
i
∈
U can be set to either T or F; if u
i belongs to a biclique that contains {
l
0
,
r
0
}, we set u
i
=
F, and if u
i belongs to a biclique that contains {
l
1
,
r
1
}, we set u
i
=
T.T
i
1
=
(
L
i
1
,
R
i
1
,
E
i
1
) contains 13 vertices and 21 edges, as shown in Figure 3(a). Figures 3(b)–3(d) show three 3-biclique partitions of T
i
1. In Figures 3(b) –3(d), the vertices with the same color induce a biclique. In fact, there exist exactly three 3-biclique partitions for T
i
1, as shown in Figures 3(b) –3(d).T
i
1 and the three 3-biclique partitions of T
i
1.
(a)
(b)
(c)
(d)Lemma 3.
For an arbitrary 3-biclique partition ofT
i
1, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (For the sake of readability, we defer the proof to the Appendix. The complete proof is in Appendix A.)Based on Lemma3, each vertex in T
i
1 is assigned a value for denoting a 3-biclique partition of T
i
1 by the assignment function f
:
(
T
i
1
)
→
{
0,1
,
2
}. According to a 3-biclique partition of T
i
1, the function f
(
·
) is defined as
(1)
f
(
v
)
=
{
0
v
and
(
l
0
,
r
0
)
belong
to
the
same
biclique
1
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
2
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
.Lemma 4.
There exist exactly three 3-biclique partitions forT
i
1. Accordingly, the values of the vertices u
x, d
i
2, and d
i
3 are (f
(
u
x
), f
(
d
i
2
), f
(
d
i
3
)
)
∈
{
(
1
,
2
,
1
)
,
(
0
,
2
,
2
)
,
(
0
,
0
,
1
)
}. (The proof is in Appendix B.)T
i
2
=
(
L
i
2
,
R
i
2
,
E
i
2
) is presented in Figure 4(a). T
i
2 contains 12 vertices and 17 edges. Figures 4(b) and 4(c) show two 3-biclique partitions of T
i
2. In Figures 4(b) and 4(c), the vertices with the same color induce a biclique. In fact, there exist exactly two 3-biclique partitions for T
i
2, as shown in Figures 4(b) and 4(c).T
i
2 and the two 3-biclique partitions of T
i
2.
(a)
(b)
(c)Lemma 5.
For an arbitrary 3-biclique partition ofT
i
2, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (The proof is in Appendix C.)Based on Lemma5, the same approach that was used for T
i
1 is used to assign values to the vertices of T
i
2. Again, we suppose that f
:
V
(
T
i
2
)
→
{
0,1
,
2
} is the assignment function for T
i
2. The assignment method for f
(
·
) is the same as that in Formula (1).Lemma 6.
There exist exactly two 3-biclique partitions forT
i
2. Accordingly, the values of the vertices u
y and d
i
2 are (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}. (The proof is in Appendix D.)T
i
3
=
(
L
i
3
,
R
i
3
,
E
i
3
) is isomorphic to T
i
2. To obtain T
i
3 in Figure 5, we only need to rename the vertices d
i
2, u
y, m
i
1, l
2, l
1, l
0, n
i
1, n
i
2, n
i
3, r
2, r
1, and r
0 of T
i
2 as d
i
3, u
z, o
i
1, l
2, l
0, l
1, p
i
1, p
i
2, p
i
3, r
2, r
0, and r
1, respectively. We present Lemmas 7 and 8 on T
i
3 without proof. The proofs are similar to those of Lemmas 5 and 6.Figure 5
T
i
3.Lemma 7.
For an arbitrary 3-biclique partition ofT
i
3, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques.Again, we assign the vertices ofT
i
3 using Formula (1).Lemma 8.
There exist exactly two 3-biclique partitions forT
i
3. Accordingly, the values of the vertices u
z and d
i
3 are (
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1
,
2
)
,
(
0
,
1
)
}.Step 2.
We mergeT
i
1, T
i
2, and T
i
3 into a bipartite graph B
i (1
≤
i
≤
m) that is associated with the clause c
i
∈
C.For the bipartite graphsT
11, T
12, T
13, …, T
m
1, T
m
2, and T
m
3 (1
≤
i
≤
m) constructed as before, we first merge T
i
1, T
i
2, and T
i
3 into B
i before building an instance B of 3-PBB. Suppose that B
i
=
(
X
[
B
i
]
,
Y
[
B
i
]
,
E
[
B
i
]
) and B
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
).The left and right vertex sets ofB
i are obtained by merging the left and right vertex sets of T
i
1, T
i
2, and T
i
3:
(2)
X
[
B
i
]
=
L
i
1
∪
L
i
2
∪
L
i
3
,
Y
[
B
i
]
=
R
i
1
∪
R
i
2
∪
R
i
3
.In words, each vertex ofV
(
B
i
) belongs to V
(
T
i
1
), V
(
T
i
2
), or V
(
T
i
3
), and vice versa, and vertices with the same vertex label in T
i
1, T
i
2, and T
i
3 are merged into one vertex in B
i as follows: the vertices with the same label, including l
0, r
0, l
1, r
1, l
2, and r
2 in T
i
1, T
i
2, and T
i
3, are merged into one group of vertices labeled l
0,  r
0,  l
1,  r
1,  l
2, and r
2 in B
i; two vertices d
i
2 in T
i
1 and d
i
2 in T
i
2 are merged into one vertex labeled d
i
2 in B
i; and two vertices d
i
3 in T
i
1 and d
i
3 in T
i
3 are merged into one vertex labeled d
i
3 in B
i. In T
i
2 and T
i
3, no other vertices exist with the same label except for l
0,  r
0,  l
1,  r
1,  l
2, and r
2.E
(
B
i
) has two portions. Let E
[
B
i
]
=
E
1
[
B
i
]
∪
E
2
[
B
i
]. The first portion E
1
[
B
i
] can be obtained by merging E
(
T
i
1
), E
(
T
i
2
), and E
(
T
i
3
):
(3)
E
1
[
B
i
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
i
1
or
(
l
,
r
)
∈
E
i
2
or
(
l
,
r
)
∈
E
i
3
}
.Clearly, the edges with the same vertex label inT
i
1, T
i
2, and T
i
3 are merged into one edge of E
1
[
B
i
], respectively, and T
i
1, T
i
2, and T
i
3 are bipartite subgraphs of B
i. To ensure that there exists a 3-biclique partition for B
i
1, we require the addition of more edges as the other portion of E
(
B
i
) as follows: the edges of T
i
1 and T
i
2 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
1,2
]; the edges of T
i
2 and T
i
3 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
2,3
]; and the edges of T
i
3 and T
i
1 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
3,1
]. For two graphs, if a vertex label occurs exactly one of the two graphs, then the vertex corresponding to this label is called a nonpublic vertex. These three additional edge sets are formally stated as follows:
(4)
E
2
[
B
i
,
1,2
]
=
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
2
-
(
R
i
1
∩
R
i
2
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
1
-
(
R
i
1
∩
R
i
2
)
}
,
E
2
[
B
i
,
2,3
]
=
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
3
-
(
R
i
2
∩
R
i
3
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
2
-
(
R
i
2
∩
R
i
3
)
}
,
E
2
[
B
i
,
3,1
]
=
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
1
-
(
R
i
3
∩
R
i
1
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
3
-
(
R
i
3
∩
R
i
1
)
}
.Hence, the second portion ofE
(
B
i
) can be obtained:
(5)
E
2
[
B
i
]
=
E
2
[
B
i
,
1,2
]
∪
E
2
[
B
i
,
2,3
]
∪
E
2
[
B
i
,
3,1
]
.ForB
i and its bipartite subgraphs T
i
1, T
i
2, and T
i
3, Proposition 9 holds.Proposition 9.
A bipartite subgraph ofB
i induced by V
(
T
i
j
) is isomorphic to T
i
j, where j
∈
{
1,2
,
3
}. (The proof is in Appendix E.)Figure6 illustrates the process of building B
i from T
i
1, T
i
2, and T
i
3. The meaning of Figure 6 is as follows.(1)
Figure6(a) shows the public vertices. The white vertex set is a public vertex set of T
i
1, T
i
2, and T
i
3. The gray vertex d
i
2 is a public vertex of T
i
1 and T
i
2. The blue vertex d
i
3 is a public vertex of T
i
1 and T
i
3.
(2)
Figure6(b) depicts how to obtain V
(
B
i
) and E
1
[
B
i
]. The white vertices of T
i
1, T
i
2, and T
i
3, the gray vertex of T
i
1 and T
i
2, and the blue vertex of T
i
1 and T
i
3 are merged together, respectively. Here, u
x, u
y, and u
z cannot be merged because they are pairwise different. As shown in Figure 6(b), the edge set is E
1
[
B
i
].
(3)
Figure6(c) displays the following additional edge sets: E
2
[
B
i
,
1,2
] (yellow edge set), E
2
[
B
i
,
2,3
] (black edge set), and E
2
[
B
i
,
3,1
] (red edge set). For the sake of clarity, E
1
[
B
i
] is not illustrated in Figure 6(c). If E
1
[
B
i
] is added to Figure 6(c), then B
i will be obtained.Figure 6
The construction ofB
i by merging T
i
1, T
i
2, and T
i
3.Step 3.
We mergeB
1
,
B
2
,
…
,
B
m into B that is associated with an instance of MO3.The steps used to mergeB
i
(
1
≤
i
≤
m
) are similar to those in merging T
i
1, T
i
1, and T
i
3 as above. V
(
B
) is obtained by merging V
(
B
i
)’s (
1
≤
i
≤
m
):
(6)
X
[
B
]
=
⋃
i
=
1
m
‍
X
[
B
i
]
,
Y
[
B
]
=
⋃
i
=
1
m
‍
Y
[
B
i
]
.In words, each vertex ofV
(
B
) belongs to V
(
B
i
)
(
1
≤
i
≤
m
) and vice versa, and vertices with the same vertex label in B
i’s are merged into one vertex in B as follows: the m group vertices labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} in B
1
,
B
2
,
…
,
B
m are merged into one group in B and are still labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
}, and if a variable u
i
∈
U appears t times in the clause collection C, then in B, the t vertices labeled u
i in t
B
i’s are merged into one vertex u
i. Therefore, each variable corresponds to exactly one vertex in B.E
(
B
) has two portions. Let E
[
B
]
=
E
1
[
B
]
∪
E
2
[
B
]. The first portion E
1
[
B
] can be obtained by merging E
(
B
1
), E
(
B
2
)
,
…
,
E
(
B
m
); that is,
(7)
E
1
[
B
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
[
B
i
]
,
1
≤
i
≤
m
}
.Similarly, the edges with the same vertex label inB
i’s (1
≤
i
≤
m) are merged into one edge of E
1
[
B
], and B
i’s are bipartite subgraph of B. To ensure that there exists a 3-biclique partition for B, we require the addition of more edges to be the other portion of E
(
B
): the edges among the nonpublic vertices of B
i and B
j are added as the edge set E
2
[
B
,
i
,
j
], where i
≠
j. These additional edge sets are formally stated as follows:
(8)
E
2
[
B
,
i
,
j
]
=
{
(
l
,
r
)
∣
l
∈
X
[
B
i
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
j
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
∪
{
(
l
,
r
)
∣
l
∈
X
[
B
j
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
i
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
.Consequently, the second portion ofE
(
B
) can be obtained:
(9)
E
2
[
B
]
=
⋃
i
=
1
m
-
1
⋃
j
=
j
+
1
m
‍
E
2
[
B
,
i
,
j
]
.This completes the construction of the bipartite graphB. B obtained by merging m
B
i’s has at most 23
*
m vertices and 85
×
m
+
C
m
2
×
140 edges. Therefore, B can be constructed in polynomial time.ForB, B
i, and T
i
j
(
1
≤
i
≤
m
,
1
≤
j
≤
3
), Proposition 10 holds.Proposition 10.
A bipartite subgraph ofB induced by V
(
B
i
) is isomorphic to B
i, and a bipartite subgraph of B induced by V
(
T
i
j
) is isomorphic to T
i
j, where 1
≤
i
≤
m
,
1
≤
j
≤
3. (The proof is in Appendix F.)Next, we show that there does not exist a 2-biclique partition forB; that is, if there exists a k-biclique partition for B, then k
≥
3.Lemma 11.
If there exists ak-biclique partition for B, then k
≥
3.Proof.
An arbitrary vertexv
∈
L
i
j is adjacent to at most two of r
0, r
1, and r
2 in T
i
j. In the process of building B, there is no additional edge whose end vertex is in {
l
0
,
l
1
,
l
2
,
r
0
,
r
1
,
r
2
}. Therefore, an arbitrary vertex v
∈
X
[
B
] is adjacent to, at most, two of r
0, r
1, and r
2, such that r
0, r
1, and r
2 belong to at least two bicliques. If r
0, r
1, and r
2 are partitioned into two bicliques, then suppose that {
r
x
,
r
y
} and {
r
z
} are partitioned into different bicliques, where x
,
y
,
z
∈
{
1,2
,
3
},  x
≠
y,  x
≠
z,  y
≠
z. Based on the process of building B, (
l
x
,
r
y
)
∉
E
[
B
], and (
l
x
,
r
z
)
∉
E
[
B
]. Thus, l
x, r
x, r
y, and r
z of B belong to at least three bicliques, and the lemma follows.In the following, we prove that if there exists a 3-biclique partition forB, then Lemmas 12 and 13 hold.Lemma 12.
If there exists at least one 3-biclique partition forB, then {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} will always be partitioned into three different bicliques for an arbitrary 3-biclique partition of B.Proof.
There are only three edges(
l
0
,
r
0
),  (
l
1
,
r
1
), and (
l
2
,
r
2
) between {
l
0
,
l
1
,
l
2
} and {
r
0
,
r
1
,
r
2
} in B. Therefore, if r
0
,
r
1, and r
2 are partitioned into three bicliques, then {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} must be partitioned into three bicliques. Moreover, because an arbitrary vertex v
∈
X
[
B
] is adjacent to at most two vertices of {
r
0
,
r
1
,
r
2
}, r
0, r
1, and r
2 belong to at least two bicliques in a 3-biclique partition of B. We next show that r
0,  r
1, and r
2 do not belong to two bicliques using proof by contradiction.
Suppose thatr
0, r
1, and r
2 belong to two bicliques. We can assume without loss of generality that X
[
B
]
∪
Y
[
B
]
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B, {
r
x
,
r
y
}
⊆
V
b
1, {
r
z
}
⊆
V
b
2, where x
,
y
,
z
∈
{
0
,
1
,
2
},  x
≠
y,  y
≠
z,  x
≠
z. Because (
l
x
,
r
y
)
∉
E
B,  (
l
y
,
r
x
)
∉
E
B,  (
l
x
,
r
z
)
∉
E
B,  (
l
y
,
r
z
)
∉
E
B, we have {
l
x
,
l
y
}
⊆
V
b
3. Thus, there exists T
i
j
=
(
L
i
j
,
R
i
j
,
E
i
j
), 1
≤
i
≤
m, j
∈
{
1,2
,
3
}, such that {
l
x
,
l
y
,
v
r
}
⊆
V
b
3, v
r
∈
R
i
j
∖
{
r
0
,
r
1
,
r
2
}. Because {
v
r
,
r
0
,
r
1
,
r
2
}
⊆
R
i
j, the vertices in R
i
j are partitioned into three bicliques in a 3-biclique partition of B. By Proposition 10, the edge subset of B induced by V
(
T
i
j
) is exactly E
i
j. We next show that the vertices in L
i
j also belong to three bicliques. Consider the following three cases: T
i
j
=
T
i
1, T
i
j
=
T
i
2, and T
i
j
=
T
i
3. (1)
IfT
i
j
=
T
i
1, then v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
,
q
i
4
}. As shown in Figure 7(a), if v
r is q
i
4, then there are no edges between {
u
x
,
d
i
2
,
d
i
3
} and q
i
4. Moreover, u
x, d
i
2, and d
i
3 cannot simultaneously belong to either V
b
1 or V
b
2. Therefore, the vertices in L
i
j belong to three bicliques. As shown in Figures 7(b)–7(d), if v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, we distinguish three cases. For an arbitrary v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, v
r is not adjacent to two of u
x, d
i
2, and d
i
3 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(2)
IfT
i
j
=
T
i
2, then v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}. As shown in Figures 8(a)–8(c), we distinguish three cases. For an arbitrary v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}, v
r is not adjacent to two of u
y, d
i
2, and m
i
1 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(3)
IfT
i
j
=
T
i
3, then because T
i
2 and T
i
3 are isomorphic, the vertices of L
i
j also belong to three bicliques.
By (1), (2), and (3), either the left or right vertices ofT
i
j are always partitioned into three bicliques in a 3-biclique partition of B. Thus, V
b
1
∩
V
(
T
i
j
),  V
b
2
∩
V
(
T
i
j
), or V
b
3
∩
V
(
T
i
j
) induces a biclique in a 3-biclique partition of B, respectively. The three bicliques are a 3-biclique partition of T
i
j. From Lemmas 3, 5, and 7, r
0,  r
1, and r
2 must belong to three different bicliques, which contradicts the supposition that r
0, r
1, and r
2 belong to two bicliques. The lemma follows.IfT
i
j is T
i
1, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)
(d)IfT
i
j is T
i
2, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)Lemma 13.
LetX
[
B
]
∪
Y
[
B
]
=
V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 be a 3-biclique partition of B. Then, L
i
j
∪
R
i
j
=
V
(
T
i
j
)
=
[
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j.Proof.
From Lemma12, {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into three different bicliques in a 3-biclique partition of B. Thus, for T
i
j in B, the vertices of either its L
i
j or R
i
j all belong to three bicliques. By Proposition 10, the bipartite subgraph of B induced by V
(
T
i
j
) is T
i
j. Therefore, the edges between L
i
j and R
i
j must belong to E
i
j in a 3-biclique partition of B. From the definition of a biclique, the lemma follows.


#### 3.1.2. Completing the NP-Completeness Proof of 3-PBB

It is easy to see that 3-PBB∈ NP because, for a given bipartite graph B, a nondeterministic algorithm need only guess a partition with size 3 of V
(
B
) that partitions V
(
B
) into three groups and check in polynomial time whether the bipartite subgraph induced by each vertex group is a biclique.Previously, we constructed a bipartite graphB
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
) from a variable set U
=
{
u
1
,
u
2
,
…
,
u
n
} and a clause collection C
=
{
c
1
,
c
2
,
…
,
c
m
}. All that remains to be shown is that there exists a truth assignment for U such that C is satisfied if and only if there exists a 3-biclique partition for B.(
→
) Assume that A
:
U
→
{
T
,
F
} is a truth assignment that satisfies C. We first assign each vertex of B in three steps and then show that there exists a 3-biclique partition for B.(1)
Letc
i
=
(
u
x
,
u
x
,
u
y
)
∈
C; then the value of c
i is (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}. The 3-biclique partitions of T
i
1, T
i
2, and T
i
3 are given from the values of A
(
u
x
), A
(
u
y
), and A
(
u
z
), as presented in Table 1. Based on Lemmas 3, 5, and 7, we set each vertex of T
i
1,  T
i
2, and T
i
3 to “0,” “1,” or “2” by Formula (1) and Table 1.
(2)
We assign a value to each vertex ofV
(
B
i
) as follows: if a vertex v
∈
B
i has the same label with a vertex w
∈
T
i
j (1
≤
j
≤
3), then set v equal to the value of w. As shown in Table 1, a key observation is that vertices with the same label in T
i
1, T
i
2, and T
i
3 are assigned an identical value by a 3-biclique partitions of T
i
1, T
i
2, or T
i
3 and the true assignment of U. This ensures that each vertex of V
(
B
i
) cannot be assigned different values.
(3)
Similarly as step (2), we assign a value to each vertex ofV
(
B
) as follows: if a vertex v
∈
V
(
B
) has the same label with a vertex w
∈
B
i (1
≤
j
≤
3), then set v equal to the value of w. Clearly, by the truth assignment, even if a variable occurs in more than one clause of C, the variable has exactly one value; therefore, even if a variable corresponds to more than one vertex in different B
i’s, these vertices corresponding to this variable are assigned an identical value, and it is not hard to see that each vertex of {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} has an identical value in different B
i’s by Formula (1). In addition, except for u
x, u
y, u
z, l
0, r
0, l
1, r
1, l
2, and r
2, there do not exist other vertices with the same label in different B
i’s. It follows that vertices with the same label in different B
i’s have an identical value. This ensures that each vertex of V
(
B
) cannot be assigned different values.Table 1
The relationship between the clausec
i
=
{
u
x
,
u
y
,
u
z
} and the vertex values of B
i.
(A
(
u
x
), A
(
u
y
), A
(
u
z
))
(T, F, F
)
(F, T, F
)
(F, F, T
)
3-biclique partitions ofT
i
1
{
l
0
,
r
0
,
q
i
1
,
q
i
2
,
q
i
4
} /{
l
1
,
r
1
,
u
x
,
d
i
3
} /{
l
2
,
r
2
,
d
i
2
,
q
i
3
}
{
l
0
,
r
0
,
u
x
,
d
i
2
} /{
l
1
,
r
1
,
d
i
3
,
q
i
1
} /{
l
2
,
r
2
,
q
i
2
,
q
i
3
,
q
i
4
}
{
l
0
,
r
0
,
u
x
,
q
i
2
} /{
l
1
,
r
1
,
q
i
1
,
q
i
3
,
q
i
4
} /{
l
2
,
r
2
,
d
i
2
,
d
i
3
}
3-biclique partitions ofT
i
2
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
{
l
0
,
r
0
,
d
i
2
,
n
i
1
} /{
l
1
,
r
1
,
u
y
,
m
i
1
} /{
l
2
,
r
2
,
n
i
2
,
n
i
3
}
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
3-biclique partitions ofT
i
3
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
p
i
1
,
p
i
2
} /{
l
1
,
r
1
,
u
z
,
p
i
3
} /{
l
2
,
r
2
,
d
i
3
,
o
i
1
}Next, to prove that there exists a 3-biclique partition forB, it suffices to show that vertices with an identical value form a biclique of B. In other words, we only need to show that if v and w belong to the left and right vertex sets, respectively, and their values are identical, then (
v
,
w
)
∈
E
[
B
]. If v and w belong to the same T
i
j, and their values are identical, then v and w certainly belong to a biclique, and (
v
,
w
)
∈
E
i
j
∈
E
[
B
] must hold. If v and w belong to different T
i
j’s, then the edge (
v
,
w
) must be added in the process of merging T
i
j’s into B
i or merging B
i’s into B; that is, (
v
,
w
)
∈
E
[
B
]. Therefore, the vertices of B with an identical value certainly form a biclique of B.(
←
) Suppose that V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B. Based on Lemma 12, a 3-biclique partition of B always partitions {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} into three different bicliques. By Formula (1), each vertex of B is set to “0,” “1,” or “2.” We next show that the vertices that correspond to a clause c
i
=
{
u
x
,
u
y
,
u
z
} are assigned (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
}.Based on Lemma13, [
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j. Therefore, we can directly consider obtaining the assignment of u
x,  u
y, and u
z from a 3-biclique partition of T
i
j.WhenT
i
j is T
i
1, based on Lemma 4, we have (f
(
u
x
)
,
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
,
1
)
,
(
0,2
,
2
)
,
(
0,0
,
1
)
}. Because d
i
2 of T
i
1 and d
i
2 of T
i
2 are of the same vertex, and d
i
3 of T
i
1 and d
i
3 of T
i
3 are of the same vertex in B, then the assignment of d
i
2 in T
i
1 is the same as that of d
i
2 in T
i
2, and the assignment of d
i
3 in T
i
1 is the same as that of d
i
3 in T
i
3. Therefore, the assignments of d
i
2 in T
i
2 and d
i
3 in T
i
3 must satisfy (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
}. When T
i
j is T
i
2 or T
i
3, based on Lemmas 6 and 8, we have (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}
,
(
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
)
,
(
0,1
)
}. Therefore, to ensure that (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
} holds, we must have (
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
} hold. It follows that if there is a 3-biclique partition for B, then (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
} holds.Because each variable corresponds to exactly one vertex inB, it is easy to obtain a truth assignment for all the variables: A
:
U
→
{
T
,
F
} from the vertex values of B. We merely set A
(
u
t
)
=
T if the assignment of u
t is f
(
u
t
)
=
1 in B and set A
(
u
t
)
=
F if the assignment of u
t is f
(
u
t
)
=
0 in B. After this assignment is made, an arbitrary clause c
i
=
{
u
x
,
u
y
,
u
z
} of an MO3 instance is set to (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}, which satisfies the clause collection C of the MO3 instance.


### 3.2. The NP-Completeness ofk-PBB (k
>
3)

To prove the NP-completeness ofk-PBB for any k
>
3, we provide a reduction from 3-PBB as follows.Theorem 14.
k-PBB (k
>
3) is NP-complete, where k is a constant positive integer.Proof.
It is easy to see thatk-PBB ∈ NP because a nondeterministic algorithm need only guess a partition with size k of V
(
G
), which partitions V
(
G
) into k groups for a given bipartite graph G, and check in polynomial time whether the bipartite subgraph that is induced by each vertex group is a biclique.
We provide a reduction from 3-PBB. Given an input instanceG
1
=
(
X
1
,
Y
1
,
E
1
) of 3-PBB, we form an instance G
2
=
(
X
2
,
Y
2
,
E
2
) of k-PBB (k
>
3) as follows: X
2
=
X
1
∪
{
l
[
i
]
∣
1
≤
i
≤
k
-
3
}; Y
2
=
Y
1
∪
{
r
[
i
]
∣
1
≤
i
≤
k
-
3
}; E
2
=
E
1
∪
{
(
l
[
i
]
,
r
[
i
]
)
|
1
≤
i
≤
k
-
3
}. That is, we add 2
(
k
-
3
) vertices and (k
-
3) independent edges to G
1 for building G
2. Then G
2
=
(
X
2
,
Y
2
,
E
2
) becomes an instance of k-PBB (k
>
3). The subgraph formed by these additional vertices and edges consists of k
-
3 disjoint bicliques, and each biclique contains only one edge.
We have that there exists a 3-biclique partition forG
1 if and only if there exists a k-biclique partition for G
2 by the observation of G
1 and G
2. The theorem follows.By Theorems2 and 14, we get that Corollary 15 holds.Corollary 15.
k-PBB is NP-complete for k
≥
3, where k is a constant positive integer.


## 3.1. The NP-Completeness of 3-PBB

In order to prove the hardness of 3-PBB, we first introduce the monotone one-in-three 3SAT problem (MO3), which was proved to be NP-complete by Schaefer in 1978 [19]. Then, we show that a variant of MO3 is NP-complete. Finally, we prove that 3-PBB is NP-complete by reduction from MO3.Below we define the terms we will use in describing MO3. LetU
=
{
u
1
,
u
2
,
…
,
u
n
} be a set of Boolean variables. If u
i
∈
U, then u
i and u
-
i are literals over U. u
i is called a positive variable, and u
-
i is called a negative variable. A truth assignment for U is a function t
:
→
T
,
F. For u
i
∈
U, if t
(
u
i
)
=
F, we say that u
i is “TRUE” under t; if f
(
u
i
)
=
F, we say that u
i is “FALSE.”The MO3 problem, which is a variant of 3SAT, is specified as follows.Instance: setU
=
{
u
1
,
u
2
,
…
,
u
n
} of Boolean variables, collection C
=
{
c
1
,
c
2
,
…
,
c
m
} of clauses over U, where each clause c
∈
C has |
c
|
=
3, and c does not contain a negative variable; that is, c
i
=
{
u
x
,
u
y
,
u
z
}
,
u
x
,
u
y
,
u
z
∈
U,   1
≤
i
≤
m.
Question: is there a truth assignment forU such that each clause in C has exactly one true literal?In the MO3 problem, a clause overU contains only positive variables. For an MO3 instance, a clause over U is satisfied by a truth assignment if and only if it has exactly one “TRUE” literal (and thus exactly two “FALSE” literals) under the assignment. A collection C of clauses over U is satisfiable if and only if there exists a truth assignment for U that simultaneously satisfies all the clauses in C.For example, we are given Boolean variable setU
=
{
u
1
,
u
2
,
u
3
,
u
4
}, and a clause collection C
=
{
c
1
,
c
2
,
c
3
,
c
4
}, where c
1
=
{
u
1
,
u
2
,
u
3
}, c
2
=
{
u
2
,
u
3
,
u
4
} and c
3
=
{
u
1
,
u
2
,
u
4
}. Let [
a
(
u
1
)
,
a
(
u
2
)
,
a
(
u
3
)
,
a
(
u
4
)
]
=
[
F
,
T
,
F
,
F
]; then, the values of the variables in c
1, c
2, and c
3 are (
F
,
T
,
F
),    (
T
,
F
,
F
), and (
F
,
T
,
F
), which means that c
1, c
2, and c
3 are satisfied. Therefore, a
(
·
) is a feasible solution of this MO3 instance.For an arbitrary MO3 instance, we can assume that the three literals in each clause are not from the same variable, in which case the clause is not satisfied. Moreover, a clause in which two literals are from the same variable can be transformed into six clauses with pairwise different variables. The approach is as follows.Suppose thatc
k
=
{
u
i
,
u
i
,
u
j
} is a clause of an MO3 instance. We create four new variables u
i
1, u
i
2, u
i
3, and u
i
4. Then, we construct six clauses over u
i, u
j, and the four new variables: c
k
[
1
]
=
{
u
i
1
,
u
i
2
,
u
i
3
}, c
k
[
2
]
=
{
u
i
1
,
u
i
2
,
u
i
}, c
k
[
3
]
=
{
u
i
2
,
u
i
3
,
u
i
}, c
k
[
4
]
=
{
u
i
1
,
u
i
2
,
u
i
4
}, c
k
[
5
]
=
{
u
i
2
,
u
i
3
,
u
i
4
}, and c
k
[
6
]
=
{
u
i
,
u
i
4
,
u
j
}. Clearly, the clause {
u
i
,
u
i
,
u
j
} is satisfied if and only if a
(
u
i
)
=
F and a
(
u
j
)
=
T. Moreover, a truth assignment for the variables u
i
1, u
i
2, u
i
3, and u
i
4 exists such that each clause in c
k[1~6] is satisfied if and only if a
(
u
i
)
=
F and a
(
u
j
)
=
T.Thus, an arbitrary MO3 instance can be transformed into an MO3 instance with pairwise different variables in each clause in polynomial time. Therefore, we have Theorem1.Theorem 1.
MO3 with pairwise different variables in each clause is NP-complete.Throughout this paper, we assume without loss of generality that, for an instance of MO3, the three literals of each clause are pairwise different. Next, we discuss the complexity of 3-PBB; that is, we prove Theorem2.Theorem 2.
3-PBB is NP-complete.The proof of Theorem2 consists of two steps. First, let a variable set U
=
{
u
1
,
u
2
,
…
,
u
n
} and a clause collection C
=
{
c
1
,
c
2
,
…
,
c
m
} be an instance of MO3; then we build a bipartite graph B
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
) that is an instance of 3-PBB. Second, we show that C is satisfied if and only if there exists a 3-biclique partition for B.


### 3.1.1. The Construction of a Bipartite GraphB from an MO3 Instance

Given an instance of MO3, we build a bipartite graphB that is an instance of 3-PBB in three steps. In the first step, we construct three components T
i
1, T
i
2, and T
i
3 from the clause c
i
(
1
≤
i
≤
m
). In the second step, we merge T
i
1, T
i
2, and T
i
3 into a bipartite graph B
i. In the final step, we merge m
B
i’s into a bipartite graph B.Step 1.
For each clausec
i
∈
C, we construct three components that are associated with the three literals in c
i. Each of these components is a bipartite graph.
Suppose thatc
i
=
{
u
x
,
u
y
,
u
z
}
∈
C. Thus, we construct the components T
i
1, T
i
2, and T
i
3. The three components contain vertices u
x, u
y, and u
z, which correspond to the variables u
x, u
y, and u
z of c
i, respectively. In the following, we will indiscriminately use the notation u
x, u
y, or u
z to represent a vertex or a variable.
The key idea used in this step of construction is that each of the three components contains a bipartite subgraph isomorphic toB
c illustrated in Figure 2. Moreover, for an arbitrary 3-biclique partition of T
i
j (j
∈
{
1,2
,
3
}), the structure of T
i
j ensures that (1)
{
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques,
(2)
u
x, u
y, or u
z only belongs to those bicliques that contain {
l
0
,
r
0
} or {
l
1
,
r
1
}.Figure 2
B
c.This is our basic way of encoding the idea thatu
i
∈
U can be set to either T or F; if u
i belongs to a biclique that contains {
l
0
,
r
0
}, we set u
i
=
F, and if u
i belongs to a biclique that contains {
l
1
,
r
1
}, we set u
i
=
T.T
i
1
=
(
L
i
1
,
R
i
1
,
E
i
1
) contains 13 vertices and 21 edges, as shown in Figure 3(a). Figures 3(b)–3(d) show three 3-biclique partitions of T
i
1. In Figures 3(b) –3(d), the vertices with the same color induce a biclique. In fact, there exist exactly three 3-biclique partitions for T
i
1, as shown in Figures 3(b) –3(d).T
i
1 and the three 3-biclique partitions of T
i
1.
(a)
(b)
(c)
(d)Lemma 3.
For an arbitrary 3-biclique partition ofT
i
1, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (For the sake of readability, we defer the proof to the Appendix. The complete proof is in Appendix A.)Based on Lemma3, each vertex in T
i
1 is assigned a value for denoting a 3-biclique partition of T
i
1 by the assignment function f
:
(
T
i
1
)
→
{
0,1
,
2
}. According to a 3-biclique partition of T
i
1, the function f
(
·
) is defined as
(1)
f
(
v
)
=
{
0
v
and
(
l
0
,
r
0
)
belong
to
the
same
biclique
1
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
2
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
.Lemma 4.
There exist exactly three 3-biclique partitions forT
i
1. Accordingly, the values of the vertices u
x, d
i
2, and d
i
3 are (f
(
u
x
), f
(
d
i
2
), f
(
d
i
3
)
)
∈
{
(
1
,
2
,
1
)
,
(
0
,
2
,
2
)
,
(
0
,
0
,
1
)
}. (The proof is in Appendix B.)T
i
2
=
(
L
i
2
,
R
i
2
,
E
i
2
) is presented in Figure 4(a). T
i
2 contains 12 vertices and 17 edges. Figures 4(b) and 4(c) show two 3-biclique partitions of T
i
2. In Figures 4(b) and 4(c), the vertices with the same color induce a biclique. In fact, there exist exactly two 3-biclique partitions for T
i
2, as shown in Figures 4(b) and 4(c).T
i
2 and the two 3-biclique partitions of T
i
2.
(a)
(b)
(c)Lemma 5.
For an arbitrary 3-biclique partition ofT
i
2, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (The proof is in Appendix C.)Based on Lemma5, the same approach that was used for T
i
1 is used to assign values to the vertices of T
i
2. Again, we suppose that f
:
V
(
T
i
2
)
→
{
0,1
,
2
} is the assignment function for T
i
2. The assignment method for f
(
·
) is the same as that in Formula (1).Lemma 6.
There exist exactly two 3-biclique partitions forT
i
2. Accordingly, the values of the vertices u
y and d
i
2 are (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}. (The proof is in Appendix D.)T
i
3
=
(
L
i
3
,
R
i
3
,
E
i
3
) is isomorphic to T
i
2. To obtain T
i
3 in Figure 5, we only need to rename the vertices d
i
2, u
y, m
i
1, l
2, l
1, l
0, n
i
1, n
i
2, n
i
3, r
2, r
1, and r
0 of T
i
2 as d
i
3, u
z, o
i
1, l
2, l
0, l
1, p
i
1, p
i
2, p
i
3, r
2, r
0, and r
1, respectively. We present Lemmas 7 and 8 on T
i
3 without proof. The proofs are similar to those of Lemmas 5 and 6.Figure 5
T
i
3.Lemma 7.
For an arbitrary 3-biclique partition ofT
i
3, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques.Again, we assign the vertices ofT
i
3 using Formula (1).Lemma 8.
There exist exactly two 3-biclique partitions forT
i
3. Accordingly, the values of the vertices u
z and d
i
3 are (
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1
,
2
)
,
(
0
,
1
)
}.Step 2.
We mergeT
i
1, T
i
2, and T
i
3 into a bipartite graph B
i (1
≤
i
≤
m) that is associated with the clause c
i
∈
C.For the bipartite graphsT
11, T
12, T
13, …, T
m
1, T
m
2, and T
m
3 (1
≤
i
≤
m) constructed as before, we first merge T
i
1, T
i
2, and T
i
3 into B
i before building an instance B of 3-PBB. Suppose that B
i
=
(
X
[
B
i
]
,
Y
[
B
i
]
,
E
[
B
i
]
) and B
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
).The left and right vertex sets ofB
i are obtained by merging the left and right vertex sets of T
i
1, T
i
2, and T
i
3:
(2)
X
[
B
i
]
=
L
i
1
∪
L
i
2
∪
L
i
3
,
Y
[
B
i
]
=
R
i
1
∪
R
i
2
∪
R
i
3
.In words, each vertex ofV
(
B
i
) belongs to V
(
T
i
1
), V
(
T
i
2
), or V
(
T
i
3
), and vice versa, and vertices with the same vertex label in T
i
1, T
i
2, and T
i
3 are merged into one vertex in B
i as follows: the vertices with the same label, including l
0, r
0, l
1, r
1, l
2, and r
2 in T
i
1, T
i
2, and T
i
3, are merged into one group of vertices labeled l
0,  r
0,  l
1,  r
1,  l
2, and r
2 in B
i; two vertices d
i
2 in T
i
1 and d
i
2 in T
i
2 are merged into one vertex labeled d
i
2 in B
i; and two vertices d
i
3 in T
i
1 and d
i
3 in T
i
3 are merged into one vertex labeled d
i
3 in B
i. In T
i
2 and T
i
3, no other vertices exist with the same label except for l
0,  r
0,  l
1,  r
1,  l
2, and r
2.E
(
B
i
) has two portions. Let E
[
B
i
]
=
E
1
[
B
i
]
∪
E
2
[
B
i
]. The first portion E
1
[
B
i
] can be obtained by merging E
(
T
i
1
), E
(
T
i
2
), and E
(
T
i
3
):
(3)
E
1
[
B
i
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
i
1
or
(
l
,
r
)
∈
E
i
2
or
(
l
,
r
)
∈
E
i
3
}
.Clearly, the edges with the same vertex label inT
i
1, T
i
2, and T
i
3 are merged into one edge of E
1
[
B
i
], respectively, and T
i
1, T
i
2, and T
i
3 are bipartite subgraphs of B
i. To ensure that there exists a 3-biclique partition for B
i
1, we require the addition of more edges as the other portion of E
(
B
i
) as follows: the edges of T
i
1 and T
i
2 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
1,2
]; the edges of T
i
2 and T
i
3 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
2,3
]; and the edges of T
i
3 and T
i
1 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
3,1
]. For two graphs, if a vertex label occurs exactly one of the two graphs, then the vertex corresponding to this label is called a nonpublic vertex. These three additional edge sets are formally stated as follows:
(4)
E
2
[
B
i
,
1,2
]
=
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
2
-
(
R
i
1
∩
R
i
2
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
1
-
(
R
i
1
∩
R
i
2
)
}
,
E
2
[
B
i
,
2,3
]
=
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
3
-
(
R
i
2
∩
R
i
3
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
2
-
(
R
i
2
∩
R
i
3
)
}
,
E
2
[
B
i
,
3,1
]
=
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
1
-
(
R
i
3
∩
R
i
1
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
3
-
(
R
i
3
∩
R
i
1
)
}
.Hence, the second portion ofE
(
B
i
) can be obtained:
(5)
E
2
[
B
i
]
=
E
2
[
B
i
,
1,2
]
∪
E
2
[
B
i
,
2,3
]
∪
E
2
[
B
i
,
3,1
]
.ForB
i and its bipartite subgraphs T
i
1, T
i
2, and T
i
3, Proposition 9 holds.Proposition 9.
A bipartite subgraph ofB
i induced by V
(
T
i
j
) is isomorphic to T
i
j, where j
∈
{
1,2
,
3
}. (The proof is in Appendix E.)Figure6 illustrates the process of building B
i from T
i
1, T
i
2, and T
i
3. The meaning of Figure 6 is as follows.(1)
Figure6(a) shows the public vertices. The white vertex set is a public vertex set of T
i
1, T
i
2, and T
i
3. The gray vertex d
i
2 is a public vertex of T
i
1 and T
i
2. The blue vertex d
i
3 is a public vertex of T
i
1 and T
i
3.
(2)
Figure6(b) depicts how to obtain V
(
B
i
) and E
1
[
B
i
]. The white vertices of T
i
1, T
i
2, and T
i
3, the gray vertex of T
i
1 and T
i
2, and the blue vertex of T
i
1 and T
i
3 are merged together, respectively. Here, u
x, u
y, and u
z cannot be merged because they are pairwise different. As shown in Figure 6(b), the edge set is E
1
[
B
i
].
(3)
Figure6(c) displays the following additional edge sets: E
2
[
B
i
,
1,2
] (yellow edge set), E
2
[
B
i
,
2,3
] (black edge set), and E
2
[
B
i
,
3,1
] (red edge set). For the sake of clarity, E
1
[
B
i
] is not illustrated in Figure 6(c). If E
1
[
B
i
] is added to Figure 6(c), then B
i will be obtained.Figure 6
The construction ofB
i by merging T
i
1, T
i
2, and T
i
3.Step 3.
We mergeB
1
,
B
2
,
…
,
B
m into B that is associated with an instance of MO3.The steps used to mergeB
i
(
1
≤
i
≤
m
) are similar to those in merging T
i
1, T
i
1, and T
i
3 as above. V
(
B
) is obtained by merging V
(
B
i
)’s (
1
≤
i
≤
m
):
(6)
X
[
B
]
=
⋃
i
=
1
m
‍
X
[
B
i
]
,
Y
[
B
]
=
⋃
i
=
1
m
‍
Y
[
B
i
]
.In words, each vertex ofV
(
B
) belongs to V
(
B
i
)
(
1
≤
i
≤
m
) and vice versa, and vertices with the same vertex label in B
i’s are merged into one vertex in B as follows: the m group vertices labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} in B
1
,
B
2
,
…
,
B
m are merged into one group in B and are still labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
}, and if a variable u
i
∈
U appears t times in the clause collection C, then in B, the t vertices labeled u
i in t
B
i’s are merged into one vertex u
i. Therefore, each variable corresponds to exactly one vertex in B.E
(
B
) has two portions. Let E
[
B
]
=
E
1
[
B
]
∪
E
2
[
B
]. The first portion E
1
[
B
] can be obtained by merging E
(
B
1
), E
(
B
2
)
,
…
,
E
(
B
m
); that is,
(7)
E
1
[
B
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
[
B
i
]
,
1
≤
i
≤
m
}
.Similarly, the edges with the same vertex label inB
i’s (1
≤
i
≤
m) are merged into one edge of E
1
[
B
], and B
i’s are bipartite subgraph of B. To ensure that there exists a 3-biclique partition for B, we require the addition of more edges to be the other portion of E
(
B
): the edges among the nonpublic vertices of B
i and B
j are added as the edge set E
2
[
B
,
i
,
j
], where i
≠
j. These additional edge sets are formally stated as follows:
(8)
E
2
[
B
,
i
,
j
]
=
{
(
l
,
r
)
∣
l
∈
X
[
B
i
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
j
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
∪
{
(
l
,
r
)
∣
l
∈
X
[
B
j
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
i
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
.Consequently, the second portion ofE
(
B
) can be obtained:
(9)
E
2
[
B
]
=
⋃
i
=
1
m
-
1
⋃
j
=
j
+
1
m
‍
E
2
[
B
,
i
,
j
]
.This completes the construction of the bipartite graphB. B obtained by merging m
B
i’s has at most 23
*
m vertices and 85
×
m
+
C
m
2
×
140 edges. Therefore, B can be constructed in polynomial time.ForB, B
i, and T
i
j
(
1
≤
i
≤
m
,
1
≤
j
≤
3
), Proposition 10 holds.Proposition 10.
A bipartite subgraph ofB induced by V
(
B
i
) is isomorphic to B
i, and a bipartite subgraph of B induced by V
(
T
i
j
) is isomorphic to T
i
j, where 1
≤
i
≤
m
,
1
≤
j
≤
3. (The proof is in Appendix F.)Next, we show that there does not exist a 2-biclique partition forB; that is, if there exists a k-biclique partition for B, then k
≥
3.Lemma 11.
If there exists ak-biclique partition for B, then k
≥
3.Proof.
An arbitrary vertexv
∈
L
i
j is adjacent to at most two of r
0, r
1, and r
2 in T
i
j. In the process of building B, there is no additional edge whose end vertex is in {
l
0
,
l
1
,
l
2
,
r
0
,
r
1
,
r
2
}. Therefore, an arbitrary vertex v
∈
X
[
B
] is adjacent to, at most, two of r
0, r
1, and r
2, such that r
0, r
1, and r
2 belong to at least two bicliques. If r
0, r
1, and r
2 are partitioned into two bicliques, then suppose that {
r
x
,
r
y
} and {
r
z
} are partitioned into different bicliques, where x
,
y
,
z
∈
{
1,2
,
3
},  x
≠
y,  x
≠
z,  y
≠
z. Based on the process of building B, (
l
x
,
r
y
)
∉
E
[
B
], and (
l
x
,
r
z
)
∉
E
[
B
]. Thus, l
x, r
x, r
y, and r
z of B belong to at least three bicliques, and the lemma follows.In the following, we prove that if there exists a 3-biclique partition forB, then Lemmas 12 and 13 hold.Lemma 12.
If there exists at least one 3-biclique partition forB, then {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} will always be partitioned into three different bicliques for an arbitrary 3-biclique partition of B.Proof.
There are only three edges(
l
0
,
r
0
),  (
l
1
,
r
1
), and (
l
2
,
r
2
) between {
l
0
,
l
1
,
l
2
} and {
r
0
,
r
1
,
r
2
} in B. Therefore, if r
0
,
r
1, and r
2 are partitioned into three bicliques, then {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} must be partitioned into three bicliques. Moreover, because an arbitrary vertex v
∈
X
[
B
] is adjacent to at most two vertices of {
r
0
,
r
1
,
r
2
}, r
0, r
1, and r
2 belong to at least two bicliques in a 3-biclique partition of B. We next show that r
0,  r
1, and r
2 do not belong to two bicliques using proof by contradiction.
Suppose thatr
0, r
1, and r
2 belong to two bicliques. We can assume without loss of generality that X
[
B
]
∪
Y
[
B
]
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B, {
r
x
,
r
y
}
⊆
V
b
1, {
r
z
}
⊆
V
b
2, where x
,
y
,
z
∈
{
0
,
1
,
2
},  x
≠
y,  y
≠
z,  x
≠
z. Because (
l
x
,
r
y
)
∉
E
B,  (
l
y
,
r
x
)
∉
E
B,  (
l
x
,
r
z
)
∉
E
B,  (
l
y
,
r
z
)
∉
E
B, we have {
l
x
,
l
y
}
⊆
V
b
3. Thus, there exists T
i
j
=
(
L
i
j
,
R
i
j
,
E
i
j
), 1
≤
i
≤
m, j
∈
{
1,2
,
3
}, such that {
l
x
,
l
y
,
v
r
}
⊆
V
b
3, v
r
∈
R
i
j
∖
{
r
0
,
r
1
,
r
2
}. Because {
v
r
,
r
0
,
r
1
,
r
2
}
⊆
R
i
j, the vertices in R
i
j are partitioned into three bicliques in a 3-biclique partition of B. By Proposition 10, the edge subset of B induced by V
(
T
i
j
) is exactly E
i
j. We next show that the vertices in L
i
j also belong to three bicliques. Consider the following three cases: T
i
j
=
T
i
1, T
i
j
=
T
i
2, and T
i
j
=
T
i
3. (1)
IfT
i
j
=
T
i
1, then v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
,
q
i
4
}. As shown in Figure 7(a), if v
r is q
i
4, then there are no edges between {
u
x
,
d
i
2
,
d
i
3
} and q
i
4. Moreover, u
x, d
i
2, and d
i
3 cannot simultaneously belong to either V
b
1 or V
b
2. Therefore, the vertices in L
i
j belong to three bicliques. As shown in Figures 7(b)–7(d), if v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, we distinguish three cases. For an arbitrary v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, v
r is not adjacent to two of u
x, d
i
2, and d
i
3 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(2)
IfT
i
j
=
T
i
2, then v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}. As shown in Figures 8(a)–8(c), we distinguish three cases. For an arbitrary v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}, v
r is not adjacent to two of u
y, d
i
2, and m
i
1 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(3)
IfT
i
j
=
T
i
3, then because T
i
2 and T
i
3 are isomorphic, the vertices of L
i
j also belong to three bicliques.
By (1), (2), and (3), either the left or right vertices ofT
i
j are always partitioned into three bicliques in a 3-biclique partition of B. Thus, V
b
1
∩
V
(
T
i
j
),  V
b
2
∩
V
(
T
i
j
), or V
b
3
∩
V
(
T
i
j
) induces a biclique in a 3-biclique partition of B, respectively. The three bicliques are a 3-biclique partition of T
i
j. From Lemmas 3, 5, and 7, r
0,  r
1, and r
2 must belong to three different bicliques, which contradicts the supposition that r
0, r
1, and r
2 belong to two bicliques. The lemma follows.IfT
i
j is T
i
1, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)
(d)IfT
i
j is T
i
2, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)Lemma 13.
LetX
[
B
]
∪
Y
[
B
]
=
V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 be a 3-biclique partition of B. Then, L
i
j
∪
R
i
j
=
V
(
T
i
j
)
=
[
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j.Proof.
From Lemma12, {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into three different bicliques in a 3-biclique partition of B. Thus, for T
i
j in B, the vertices of either its L
i
j or R
i
j all belong to three bicliques. By Proposition 10, the bipartite subgraph of B induced by V
(
T
i
j
) is T
i
j. Therefore, the edges between L
i
j and R
i
j must belong to E
i
j in a 3-biclique partition of B. From the definition of a biclique, the lemma follows.


### 3.1.2. Completing the NP-Completeness Proof of 3-PBB

It is easy to see that 3-PBB∈ NP because, for a given bipartite graph B, a nondeterministic algorithm need only guess a partition with size 3 of V
(
B
) that partitions V
(
B
) into three groups and check in polynomial time whether the bipartite subgraph induced by each vertex group is a biclique.Previously, we constructed a bipartite graphB
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
) from a variable set U
=
{
u
1
,
u
2
,
…
,
u
n
} and a clause collection C
=
{
c
1
,
c
2
,
…
,
c
m
}. All that remains to be shown is that there exists a truth assignment for U such that C is satisfied if and only if there exists a 3-biclique partition for B.(
→
) Assume that A
:
U
→
{
T
,
F
} is a truth assignment that satisfies C. We first assign each vertex of B in three steps and then show that there exists a 3-biclique partition for B.(1)
Letc
i
=
(
u
x
,
u
x
,
u
y
)
∈
C; then the value of c
i is (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}. The 3-biclique partitions of T
i
1, T
i
2, and T
i
3 are given from the values of A
(
u
x
), A
(
u
y
), and A
(
u
z
), as presented in Table 1. Based on Lemmas 3, 5, and 7, we set each vertex of T
i
1,  T
i
2, and T
i
3 to “0,” “1,” or “2” by Formula (1) and Table 1.
(2)
We assign a value to each vertex ofV
(
B
i
) as follows: if a vertex v
∈
B
i has the same label with a vertex w
∈
T
i
j (1
≤
j
≤
3), then set v equal to the value of w. As shown in Table 1, a key observation is that vertices with the same label in T
i
1, T
i
2, and T
i
3 are assigned an identical value by a 3-biclique partitions of T
i
1, T
i
2, or T
i
3 and the true assignment of U. This ensures that each vertex of V
(
B
i
) cannot be assigned different values.
(3)
Similarly as step (2), we assign a value to each vertex ofV
(
B
) as follows: if a vertex v
∈
V
(
B
) has the same label with a vertex w
∈
B
i (1
≤
j
≤
3), then set v equal to the value of w. Clearly, by the truth assignment, even if a variable occurs in more than one clause of C, the variable has exactly one value; therefore, even if a variable corresponds to more than one vertex in different B
i’s, these vertices corresponding to this variable are assigned an identical value, and it is not hard to see that each vertex of {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} has an identical value in different B
i’s by Formula (1). In addition, except for u
x, u
y, u
z, l
0, r
0, l
1, r
1, l
2, and r
2, there do not exist other vertices with the same label in different B
i’s. It follows that vertices with the same label in different B
i’s have an identical value. This ensures that each vertex of V
(
B
) cannot be assigned different values.Table 1
The relationship between the clausec
i
=
{
u
x
,
u
y
,
u
z
} and the vertex values of B
i.
(A
(
u
x
), A
(
u
y
), A
(
u
z
))
(T, F, F
)
(F, T, F
)
(F, F, T
)
3-biclique partitions ofT
i
1
{
l
0
,
r
0
,
q
i
1
,
q
i
2
,
q
i
4
} /{
l
1
,
r
1
,
u
x
,
d
i
3
} /{
l
2
,
r
2
,
d
i
2
,
q
i
3
}
{
l
0
,
r
0
,
u
x
,
d
i
2
} /{
l
1
,
r
1
,
d
i
3
,
q
i
1
} /{
l
2
,
r
2
,
q
i
2
,
q
i
3
,
q
i
4
}
{
l
0
,
r
0
,
u
x
,
q
i
2
} /{
l
1
,
r
1
,
q
i
1
,
q
i
3
,
q
i
4
} /{
l
2
,
r
2
,
d
i
2
,
d
i
3
}
3-biclique partitions ofT
i
2
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
{
l
0
,
r
0
,
d
i
2
,
n
i
1
} /{
l
1
,
r
1
,
u
y
,
m
i
1
} /{
l
2
,
r
2
,
n
i
2
,
n
i
3
}
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
3-biclique partitions ofT
i
3
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
p
i
1
,
p
i
2
} /{
l
1
,
r
1
,
u
z
,
p
i
3
} /{
l
2
,
r
2
,
d
i
3
,
o
i
1
}Next, to prove that there exists a 3-biclique partition forB, it suffices to show that vertices with an identical value form a biclique of B. In other words, we only need to show that if v and w belong to the left and right vertex sets, respectively, and their values are identical, then (
v
,
w
)
∈
E
[
B
]. If v and w belong to the same T
i
j, and their values are identical, then v and w certainly belong to a biclique, and (
v
,
w
)
∈
E
i
j
∈
E
[
B
] must hold. If v and w belong to different T
i
j’s, then the edge (
v
,
w
) must be added in the process of merging T
i
j’s into B
i or merging B
i’s into B; that is, (
v
,
w
)
∈
E
[
B
]. Therefore, the vertices of B with an identical value certainly form a biclique of B.(
←
) Suppose that V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B. Based on Lemma 12, a 3-biclique partition of B always partitions {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} into three different bicliques. By Formula (1), each vertex of B is set to “0,” “1,” or “2.” We next show that the vertices that correspond to a clause c
i
=
{
u
x
,
u
y
,
u
z
} are assigned (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
}.Based on Lemma13, [
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j. Therefore, we can directly consider obtaining the assignment of u
x,  u
y, and u
z from a 3-biclique partition of T
i
j.WhenT
i
j is T
i
1, based on Lemma 4, we have (f
(
u
x
)
,
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
,
1
)
,
(
0,2
,
2
)
,
(
0,0
,
1
)
}. Because d
i
2 of T
i
1 and d
i
2 of T
i
2 are of the same vertex, and d
i
3 of T
i
1 and d
i
3 of T
i
3 are of the same vertex in B, then the assignment of d
i
2 in T
i
1 is the same as that of d
i
2 in T
i
2, and the assignment of d
i
3 in T
i
1 is the same as that of d
i
3 in T
i
3. Therefore, the assignments of d
i
2 in T
i
2 and d
i
3 in T
i
3 must satisfy (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
}. When T
i
j is T
i
2 or T
i
3, based on Lemmas 6 and 8, we have (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}
,
(
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
)
,
(
0,1
)
}. Therefore, to ensure that (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
} holds, we must have (
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
} hold. It follows that if there is a 3-biclique partition for B, then (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
} holds.Because each variable corresponds to exactly one vertex inB, it is easy to obtain a truth assignment for all the variables: A
:
U
→
{
T
,
F
} from the vertex values of B. We merely set A
(
u
t
)
=
T if the assignment of u
t is f
(
u
t
)
=
1 in B and set A
(
u
t
)
=
F if the assignment of u
t is f
(
u
t
)
=
0 in B. After this assignment is made, an arbitrary clause c
i
=
{
u
x
,
u
y
,
u
z
} of an MO3 instance is set to (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}, which satisfies the clause collection C of the MO3 instance.


## 3.1.1. The Construction of a Bipartite GraphB from an MO3 Instance

Given an instance of MO3, we build a bipartite graphB that is an instance of 3-PBB in three steps. In the first step, we construct three components T
i
1, T
i
2, and T
i
3 from the clause c
i
(
1
≤
i
≤
m
). In the second step, we merge T
i
1, T
i
2, and T
i
3 into a bipartite graph B
i. In the final step, we merge m
B
i’s into a bipartite graph B.Step 1.
For each clausec
i
∈
C, we construct three components that are associated with the three literals in c
i. Each of these components is a bipartite graph.
Suppose thatc
i
=
{
u
x
,
u
y
,
u
z
}
∈
C. Thus, we construct the components T
i
1, T
i
2, and T
i
3. The three components contain vertices u
x, u
y, and u
z, which correspond to the variables u
x, u
y, and u
z of c
i, respectively. In the following, we will indiscriminately use the notation u
x, u
y, or u
z to represent a vertex or a variable.
The key idea used in this step of construction is that each of the three components contains a bipartite subgraph isomorphic toB
c illustrated in Figure 2. Moreover, for an arbitrary 3-biclique partition of T
i
j (j
∈
{
1,2
,
3
}), the structure of T
i
j ensures that (1)
{
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques,
(2)
u
x, u
y, or u
z only belongs to those bicliques that contain {
l
0
,
r
0
} or {
l
1
,
r
1
}.Figure 2
B
c.This is our basic way of encoding the idea thatu
i
∈
U can be set to either T or F; if u
i belongs to a biclique that contains {
l
0
,
r
0
}, we set u
i
=
F, and if u
i belongs to a biclique that contains {
l
1
,
r
1
}, we set u
i
=
T.T
i
1
=
(
L
i
1
,
R
i
1
,
E
i
1
) contains 13 vertices and 21 edges, as shown in Figure 3(a). Figures 3(b)–3(d) show three 3-biclique partitions of T
i
1. In Figures 3(b) –3(d), the vertices with the same color induce a biclique. In fact, there exist exactly three 3-biclique partitions for T
i
1, as shown in Figures 3(b) –3(d).T
i
1 and the three 3-biclique partitions of T
i
1.
(a)
(b)
(c)
(d)Lemma 3.
For an arbitrary 3-biclique partition ofT
i
1, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (For the sake of readability, we defer the proof to the Appendix. The complete proof is in Appendix A.)Based on Lemma3, each vertex in T
i
1 is assigned a value for denoting a 3-biclique partition of T
i
1 by the assignment function f
:
(
T
i
1
)
→
{
0,1
,
2
}. According to a 3-biclique partition of T
i
1, the function f
(
·
) is defined as
(1)
f
(
v
)
=
{
0
v
and
(
l
0
,
r
0
)
belong
to
the
same
biclique
1
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
2
v
and
(
l
1
,
r
1
)
belong
to
the
same
biclique
.Lemma 4.
There exist exactly three 3-biclique partitions forT
i
1. Accordingly, the values of the vertices u
x, d
i
2, and d
i
3 are (f
(
u
x
), f
(
d
i
2
), f
(
d
i
3
)
)
∈
{
(
1
,
2
,
1
)
,
(
0
,
2
,
2
)
,
(
0
,
0
,
1
)
}. (The proof is in Appendix B.)T
i
2
=
(
L
i
2
,
R
i
2
,
E
i
2
) is presented in Figure 4(a). T
i
2 contains 12 vertices and 17 edges. Figures 4(b) and 4(c) show two 3-biclique partitions of T
i
2. In Figures 4(b) and 4(c), the vertices with the same color induce a biclique. In fact, there exist exactly two 3-biclique partitions for T
i
2, as shown in Figures 4(b) and 4(c).T
i
2 and the two 3-biclique partitions of T
i
2.
(a)
(b)
(c)Lemma 5.
For an arbitrary 3-biclique partition ofT
i
2, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques. (The proof is in Appendix C.)Based on Lemma5, the same approach that was used for T
i
1 is used to assign values to the vertices of T
i
2. Again, we suppose that f
:
V
(
T
i
2
)
→
{
0,1
,
2
} is the assignment function for T
i
2. The assignment method for f
(
·
) is the same as that in Formula (1).Lemma 6.
There exist exactly two 3-biclique partitions forT
i
2. Accordingly, the values of the vertices u
y and d
i
2 are (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}. (The proof is in Appendix D.)T
i
3
=
(
L
i
3
,
R
i
3
,
E
i
3
) is isomorphic to T
i
2. To obtain T
i
3 in Figure 5, we only need to rename the vertices d
i
2, u
y, m
i
1, l
2, l
1, l
0, n
i
1, n
i
2, n
i
3, r
2, r
1, and r
0 of T
i
2 as d
i
3, u
z, o
i
1, l
2, l
0, l
1, p
i
1, p
i
2, p
i
3, r
2, r
0, and r
1, respectively. We present Lemmas 7 and 8 on T
i
3 without proof. The proofs are similar to those of Lemmas 5 and 6.Figure 5
T
i
3.Lemma 7.
For an arbitrary 3-biclique partition ofT
i
3, {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into different bicliques.Again, we assign the vertices ofT
i
3 using Formula (1).Lemma 8.
There exist exactly two 3-biclique partitions forT
i
3. Accordingly, the values of the vertices u
z and d
i
3 are (
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1
,
2
)
,
(
0
,
1
)
}.Step 2.
We mergeT
i
1, T
i
2, and T
i
3 into a bipartite graph B
i (1
≤
i
≤
m) that is associated with the clause c
i
∈
C.For the bipartite graphsT
11, T
12, T
13, …, T
m
1, T
m
2, and T
m
3 (1
≤
i
≤
m) constructed as before, we first merge T
i
1, T
i
2, and T
i
3 into B
i before building an instance B of 3-PBB. Suppose that B
i
=
(
X
[
B
i
]
,
Y
[
B
i
]
,
E
[
B
i
]
) and B
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
).The left and right vertex sets ofB
i are obtained by merging the left and right vertex sets of T
i
1, T
i
2, and T
i
3:
(2)
X
[
B
i
]
=
L
i
1
∪
L
i
2
∪
L
i
3
,
Y
[
B
i
]
=
R
i
1
∪
R
i
2
∪
R
i
3
.In words, each vertex ofV
(
B
i
) belongs to V
(
T
i
1
), V
(
T
i
2
), or V
(
T
i
3
), and vice versa, and vertices with the same vertex label in T
i
1, T
i
2, and T
i
3 are merged into one vertex in B
i as follows: the vertices with the same label, including l
0, r
0, l
1, r
1, l
2, and r
2 in T
i
1, T
i
2, and T
i
3, are merged into one group of vertices labeled l
0,  r
0,  l
1,  r
1,  l
2, and r
2 in B
i; two vertices d
i
2 in T
i
1 and d
i
2 in T
i
2 are merged into one vertex labeled d
i
2 in B
i; and two vertices d
i
3 in T
i
1 and d
i
3 in T
i
3 are merged into one vertex labeled d
i
3 in B
i. In T
i
2 and T
i
3, no other vertices exist with the same label except for l
0,  r
0,  l
1,  r
1,  l
2, and r
2.E
(
B
i
) has two portions. Let E
[
B
i
]
=
E
1
[
B
i
]
∪
E
2
[
B
i
]. The first portion E
1
[
B
i
] can be obtained by merging E
(
T
i
1
), E
(
T
i
2
), and E
(
T
i
3
):
(3)
E
1
[
B
i
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
i
1
or
(
l
,
r
)
∈
E
i
2
or
(
l
,
r
)
∈
E
i
3
}
.Clearly, the edges with the same vertex label inT
i
1, T
i
2, and T
i
3 are merged into one edge of E
1
[
B
i
], respectively, and T
i
1, T
i
2, and T
i
3 are bipartite subgraphs of B
i. To ensure that there exists a 3-biclique partition for B
i
1, we require the addition of more edges as the other portion of E
(
B
i
) as follows: the edges of T
i
1 and T
i
2 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
1,2
]; the edges of T
i
2 and T
i
3 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
2,3
]; and the edges of T
i
3 and T
i
1 among the nonpublic vertices are added, as denoted by E
2
[
B
i
,
3,1
]. For two graphs, if a vertex label occurs exactly one of the two graphs, then the vertex corresponding to this label is called a nonpublic vertex. These three additional edge sets are formally stated as follows:
(4)
E
2
[
B
i
,
1,2
]
=
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
2
-
(
R
i
1
∩
R
i
2
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
1
∩
L
i
2
)
,
r
∈
R
i
1
-
(
R
i
1
∩
R
i
2
)
}
,
E
2
[
B
i
,
2,3
]
=
{
(
l
,
r
)
∣
l
∈
L
i
2
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
3
-
(
R
i
2
∩
R
i
3
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
2
∩
L
i
3
)
,
r
∈
R
i
2
-
(
R
i
2
∩
R
i
3
)
}
,
E
2
[
B
i
,
3,1
]
=
{
(
l
,
r
)
∣
l
∈
L
i
3
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
1
-
(
R
i
3
∩
R
i
1
)
}
∪
{
(
l
,
r
)
∣
l
∈
L
i
1
-
(
L
i
3
∩
L
i
1
)
,
r
∈
R
i
3
-
(
R
i
3
∩
R
i
1
)
}
.Hence, the second portion ofE
(
B
i
) can be obtained:
(5)
E
2
[
B
i
]
=
E
2
[
B
i
,
1,2
]
∪
E
2
[
B
i
,
2,3
]
∪
E
2
[
B
i
,
3,1
]
.ForB
i and its bipartite subgraphs T
i
1, T
i
2, and T
i
3, Proposition 9 holds.Proposition 9.
A bipartite subgraph ofB
i induced by V
(
T
i
j
) is isomorphic to T
i
j, where j
∈
{
1,2
,
3
}. (The proof is in Appendix E.)Figure6 illustrates the process of building B
i from T
i
1, T
i
2, and T
i
3. The meaning of Figure 6 is as follows.(1)
Figure6(a) shows the public vertices. The white vertex set is a public vertex set of T
i
1, T
i
2, and T
i
3. The gray vertex d
i
2 is a public vertex of T
i
1 and T
i
2. The blue vertex d
i
3 is a public vertex of T
i
1 and T
i
3.
(2)
Figure6(b) depicts how to obtain V
(
B
i
) and E
1
[
B
i
]. The white vertices of T
i
1, T
i
2, and T
i
3, the gray vertex of T
i
1 and T
i
2, and the blue vertex of T
i
1 and T
i
3 are merged together, respectively. Here, u
x, u
y, and u
z cannot be merged because they are pairwise different. As shown in Figure 6(b), the edge set is E
1
[
B
i
].
(3)
Figure6(c) displays the following additional edge sets: E
2
[
B
i
,
1,2
] (yellow edge set), E
2
[
B
i
,
2,3
] (black edge set), and E
2
[
B
i
,
3,1
] (red edge set). For the sake of clarity, E
1
[
B
i
] is not illustrated in Figure 6(c). If E
1
[
B
i
] is added to Figure 6(c), then B
i will be obtained.Figure 6
The construction ofB
i by merging T
i
1, T
i
2, and T
i
3.Step 3.
We mergeB
1
,
B
2
,
…
,
B
m into B that is associated with an instance of MO3.The steps used to mergeB
i
(
1
≤
i
≤
m
) are similar to those in merging T
i
1, T
i
1, and T
i
3 as above. V
(
B
) is obtained by merging V
(
B
i
)’s (
1
≤
i
≤
m
):
(6)
X
[
B
]
=
⋃
i
=
1
m
‍
X
[
B
i
]
,
Y
[
B
]
=
⋃
i
=
1
m
‍
Y
[
B
i
]
.In words, each vertex ofV
(
B
) belongs to V
(
B
i
)
(
1
≤
i
≤
m
) and vice versa, and vertices with the same vertex label in B
i’s are merged into one vertex in B as follows: the m group vertices labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} in B
1
,
B
2
,
…
,
B
m are merged into one group in B and are still labeled {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
}, and if a variable u
i
∈
U appears t times in the clause collection C, then in B, the t vertices labeled u
i in t
B
i’s are merged into one vertex u
i. Therefore, each variable corresponds to exactly one vertex in B.E
(
B
) has two portions. Let E
[
B
]
=
E
1
[
B
]
∪
E
2
[
B
]. The first portion E
1
[
B
] can be obtained by merging E
(
B
1
), E
(
B
2
)
,
…
,
E
(
B
m
); that is,
(7)
E
1
[
B
]
=
{
(
l
,
r
)
∣
(
l
,
r
)
∈
E
[
B
i
]
,
1
≤
i
≤
m
}
.Similarly, the edges with the same vertex label inB
i’s (1
≤
i
≤
m) are merged into one edge of E
1
[
B
], and B
i’s are bipartite subgraph of B. To ensure that there exists a 3-biclique partition for B, we require the addition of more edges to be the other portion of E
(
B
): the edges among the nonpublic vertices of B
i and B
j are added as the edge set E
2
[
B
,
i
,
j
], where i
≠
j. These additional edge sets are formally stated as follows:
(8)
E
2
[
B
,
i
,
j
]
=
{
(
l
,
r
)
∣
l
∈
X
[
B
i
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
j
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
∪
{
(
l
,
r
)
∣
l
∈
X
[
B
j
]
-
(
X
[
B
i
]
∩
X
[
B
j
]
)
,
r
∈
Y
[
B
i
]
-
(
Y
[
B
i
]
∩
Y
[
B
j
]
)
}
.Consequently, the second portion ofE
(
B
) can be obtained:
(9)
E
2
[
B
]
=
⋃
i
=
1
m
-
1
⋃
j
=
j
+
1
m
‍
E
2
[
B
,
i
,
j
]
.This completes the construction of the bipartite graphB. B obtained by merging m
B
i’s has at most 23
*
m vertices and 85
×
m
+
C
m
2
×
140 edges. Therefore, B can be constructed in polynomial time.ForB, B
i, and T
i
j
(
1
≤
i
≤
m
,
1
≤
j
≤
3
), Proposition 10 holds.Proposition 10.
A bipartite subgraph ofB induced by V
(
B
i
) is isomorphic to B
i, and a bipartite subgraph of B induced by V
(
T
i
j
) is isomorphic to T
i
j, where 1
≤
i
≤
m
,
1
≤
j
≤
3. (The proof is in Appendix F.)Next, we show that there does not exist a 2-biclique partition forB; that is, if there exists a k-biclique partition for B, then k
≥
3.Lemma 11.
If there exists ak-biclique partition for B, then k
≥
3.Proof.
An arbitrary vertexv
∈
L
i
j is adjacent to at most two of r
0, r
1, and r
2 in T
i
j. In the process of building B, there is no additional edge whose end vertex is in {
l
0
,
l
1
,
l
2
,
r
0
,
r
1
,
r
2
}. Therefore, an arbitrary vertex v
∈
X
[
B
] is adjacent to, at most, two of r
0, r
1, and r
2, such that r
0, r
1, and r
2 belong to at least two bicliques. If r
0, r
1, and r
2 are partitioned into two bicliques, then suppose that {
r
x
,
r
y
} and {
r
z
} are partitioned into different bicliques, where x
,
y
,
z
∈
{
1,2
,
3
},  x
≠
y,  x
≠
z,  y
≠
z. Based on the process of building B, (
l
x
,
r
y
)
∉
E
[
B
], and (
l
x
,
r
z
)
∉
E
[
B
]. Thus, l
x, r
x, r
y, and r
z of B belong to at least three bicliques, and the lemma follows.In the following, we prove that if there exists a 3-biclique partition forB, then Lemmas 12 and 13 hold.Lemma 12.
If there exists at least one 3-biclique partition forB, then {
l
0
,
r
0
}, {
l
1
,
r
1
}, and {
l
2
,
r
2
} will always be partitioned into three different bicliques for an arbitrary 3-biclique partition of B.Proof.
There are only three edges(
l
0
,
r
0
),  (
l
1
,
r
1
), and (
l
2
,
r
2
) between {
l
0
,
l
1
,
l
2
} and {
r
0
,
r
1
,
r
2
} in B. Therefore, if r
0
,
r
1, and r
2 are partitioned into three bicliques, then {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} must be partitioned into three bicliques. Moreover, because an arbitrary vertex v
∈
X
[
B
] is adjacent to at most two vertices of {
r
0
,
r
1
,
r
2
}, r
0, r
1, and r
2 belong to at least two bicliques in a 3-biclique partition of B. We next show that r
0,  r
1, and r
2 do not belong to two bicliques using proof by contradiction.
Suppose thatr
0, r
1, and r
2 belong to two bicliques. We can assume without loss of generality that X
[
B
]
∪
Y
[
B
]
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B, {
r
x
,
r
y
}
⊆
V
b
1, {
r
z
}
⊆
V
b
2, where x
,
y
,
z
∈
{
0
,
1
,
2
},  x
≠
y,  y
≠
z,  x
≠
z. Because (
l
x
,
r
y
)
∉
E
B,  (
l
y
,
r
x
)
∉
E
B,  (
l
x
,
r
z
)
∉
E
B,  (
l
y
,
r
z
)
∉
E
B, we have {
l
x
,
l
y
}
⊆
V
b
3. Thus, there exists T
i
j
=
(
L
i
j
,
R
i
j
,
E
i
j
), 1
≤
i
≤
m, j
∈
{
1,2
,
3
}, such that {
l
x
,
l
y
,
v
r
}
⊆
V
b
3, v
r
∈
R
i
j
∖
{
r
0
,
r
1
,
r
2
}. Because {
v
r
,
r
0
,
r
1
,
r
2
}
⊆
R
i
j, the vertices in R
i
j are partitioned into three bicliques in a 3-biclique partition of B. By Proposition 10, the edge subset of B induced by V
(
T
i
j
) is exactly E
i
j. We next show that the vertices in L
i
j also belong to three bicliques. Consider the following three cases: T
i
j
=
T
i
1, T
i
j
=
T
i
2, and T
i
j
=
T
i
3. (1)
IfT
i
j
=
T
i
1, then v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
,
q
i
4
}. As shown in Figure 7(a), if v
r is q
i
4, then there are no edges between {
u
x
,
d
i
2
,
d
i
3
} and q
i
4. Moreover, u
x, d
i
2, and d
i
3 cannot simultaneously belong to either V
b
1 or V
b
2. Therefore, the vertices in L
i
j belong to three bicliques. As shown in Figures 7(b)–7(d), if v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, we distinguish three cases. For an arbitrary v
r
∈
{
q
i
1
,
q
i
2
,
q
i
3
}, v
r is not adjacent to two of u
x, d
i
2, and d
i
3 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(2)
IfT
i
j
=
T
i
2, then v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}. As shown in Figures 8(a)–8(c), we distinguish three cases. For an arbitrary v
r
∈
{
n
i
1
,
n
i
2
,
n
i
3
}, v
r is not adjacent to two of u
y, d
i
2, and m
i
1 (the brown vertices), and these two vertices cannot simultaneously belong to V
b
1 or V
b
2. Therefore, the vertices of L
i
j belong to three bicliques.
(3)
IfT
i
j
=
T
i
3, then because T
i
2 and T
i
3 are isomorphic, the vertices of L
i
j also belong to three bicliques.
By (1), (2), and (3), either the left or right vertices ofT
i
j are always partitioned into three bicliques in a 3-biclique partition of B. Thus, V
b
1
∩
V
(
T
i
j
),  V
b
2
∩
V
(
T
i
j
), or V
b
3
∩
V
(
T
i
j
) induces a biclique in a 3-biclique partition of B, respectively. The three bicliques are a 3-biclique partition of T
i
j. From Lemmas 3, 5, and 7, r
0,  r
1, and r
2 must belong to three different bicliques, which contradicts the supposition that r
0, r
1, and r
2 belong to two bicliques. The lemma follows.IfT
i
j is T
i
1, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)
(d)IfT
i
j is T
i
2, then the vertices of L
i
j will belong to three bicliques.
(a)
(b)
(c)Lemma 13.
LetX
[
B
]
∪
Y
[
B
]
=
V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 be a 3-biclique partition of B. Then, L
i
j
∪
R
i
j
=
V
(
T
i
j
)
=
[
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j.Proof.
From Lemma12, {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} are always partitioned into three different bicliques in a 3-biclique partition of B. Thus, for T
i
j in B, the vertices of either its L
i
j or R
i
j all belong to three bicliques. By Proposition 10, the bipartite subgraph of B induced by V
(
T
i
j
) is T
i
j. Therefore, the edges between L
i
j and R
i
j must belong to E
i
j in a 3-biclique partition of B. From the definition of a biclique, the lemma follows.


## 3.1.2. Completing the NP-Completeness Proof of 3-PBB

It is easy to see that 3-PBB∈ NP because, for a given bipartite graph B, a nondeterministic algorithm need only guess a partition with size 3 of V
(
B
) that partitions V
(
B
) into three groups and check in polynomial time whether the bipartite subgraph induced by each vertex group is a biclique.Previously, we constructed a bipartite graphB
=
(
X
[
B
]
,
Y
[
B
]
,
E
[
B
]
) from a variable set U
=
{
u
1
,
u
2
,
…
,
u
n
} and a clause collection C
=
{
c
1
,
c
2
,
…
,
c
m
}. All that remains to be shown is that there exists a truth assignment for U such that C is satisfied if and only if there exists a 3-biclique partition for B.(
→
) Assume that A
:
U
→
{
T
,
F
} is a truth assignment that satisfies C. We first assign each vertex of B in three steps and then show that there exists a 3-biclique partition for B.(1)
Letc
i
=
(
u
x
,
u
x
,
u
y
)
∈
C; then the value of c
i is (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}. The 3-biclique partitions of T
i
1, T
i
2, and T
i
3 are given from the values of A
(
u
x
), A
(
u
y
), and A
(
u
z
), as presented in Table 1. Based on Lemmas 3, 5, and 7, we set each vertex of T
i
1,  T
i
2, and T
i
3 to “0,” “1,” or “2” by Formula (1) and Table 1.
(2)
We assign a value to each vertex ofV
(
B
i
) as follows: if a vertex v
∈
B
i has the same label with a vertex w
∈
T
i
j (1
≤
j
≤
3), then set v equal to the value of w. As shown in Table 1, a key observation is that vertices with the same label in T
i
1, T
i
2, and T
i
3 are assigned an identical value by a 3-biclique partitions of T
i
1, T
i
2, or T
i
3 and the true assignment of U. This ensures that each vertex of V
(
B
i
) cannot be assigned different values.
(3)
Similarly as step (2), we assign a value to each vertex ofV
(
B
) as follows: if a vertex v
∈
V
(
B
) has the same label with a vertex w
∈
B
i (1
≤
j
≤
3), then set v equal to the value of w. Clearly, by the truth assignment, even if a variable occurs in more than one clause of C, the variable has exactly one value; therefore, even if a variable corresponds to more than one vertex in different B
i’s, these vertices corresponding to this variable are assigned an identical value, and it is not hard to see that each vertex of {
l
0
,
r
0
,
l
1
,
r
1
,
l
2
,
r
2
} has an identical value in different B
i’s by Formula (1). In addition, except for u
x, u
y, u
z, l
0, r
0, l
1, r
1, l
2, and r
2, there do not exist other vertices with the same label in different B
i’s. It follows that vertices with the same label in different B
i’s have an identical value. This ensures that each vertex of V
(
B
) cannot be assigned different values.Table 1
The relationship between the clausec
i
=
{
u
x
,
u
y
,
u
z
} and the vertex values of B
i.
(A
(
u
x
), A
(
u
y
), A
(
u
z
))
(T, F, F
)
(F, T, F
)
(F, F, T
)
3-biclique partitions ofT
i
1
{
l
0
,
r
0
,
q
i
1
,
q
i
2
,
q
i
4
} /{
l
1
,
r
1
,
u
x
,
d
i
3
} /{
l
2
,
r
2
,
d
i
2
,
q
i
3
}
{
l
0
,
r
0
,
u
x
,
d
i
2
} /{
l
1
,
r
1
,
d
i
3
,
q
i
1
} /{
l
2
,
r
2
,
q
i
2
,
q
i
3
,
q
i
4
}
{
l
0
,
r
0
,
u
x
,
q
i
2
} /{
l
1
,
r
1
,
q
i
1
,
q
i
3
,
q
i
4
} /{
l
2
,
r
2
,
d
i
2
,
d
i
3
}
3-biclique partitions ofT
i
2
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
{
l
0
,
r
0
,
d
i
2
,
n
i
1
} /{
l
1
,
r
1
,
u
y
,
m
i
1
} /{
l
2
,
r
2
,
n
i
2
,
n
i
3
}
{
l
0
,
r
0
,
u
y
,
n
i
3
} /{
l
1
,
r
1
,
n
i
1
,
n
i
2
} /{
l
2
,
r
2
,
d
i
2
,
m
i
1
}
3-biclique partitions ofT
i
3
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
u
z
,
o
i
1
} /{
l
1
,
r
1
,
d
i
3
,
p
i
1
} /{
l
2
,
r
2
,
p
i
2
,
p
i
3
}
{
l
0
,
r
0
,
p
i
1
,
p
i
2
} /{
l
1
,
r
1
,
u
z
,
p
i
3
} /{
l
2
,
r
2
,
d
i
3
,
o
i
1
}Next, to prove that there exists a 3-biclique partition forB, it suffices to show that vertices with an identical value form a biclique of B. In other words, we only need to show that if v and w belong to the left and right vertex sets, respectively, and their values are identical, then (
v
,
w
)
∈
E
[
B
]. If v and w belong to the same T
i
j, and their values are identical, then v and w certainly belong to a biclique, and (
v
,
w
)
∈
E
i
j
∈
E
[
B
] must hold. If v and w belong to different T
i
j’s, then the edge (
v
,
w
) must be added in the process of merging T
i
j’s into B
i or merging B
i’s into B; that is, (
v
,
w
)
∈
E
[
B
]. Therefore, the vertices of B with an identical value certainly form a biclique of B.(
←
) Suppose that V
(
B
)
=
V
b
1
∪
V
b
2
∪
V
b
3 is a 3-biclique partition of B. Based on Lemma 12, a 3-biclique partition of B always partitions {
l
0
,
r
0
},  {
l
1
,
r
1
}, and {
l
2
,
r
2
} into three different bicliques. By Formula (1), each vertex of B is set to “0,” “1,” or “2.” We next show that the vertices that correspond to a clause c
i
=
{
u
x
,
u
y
,
u
z
} are assigned (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
}.Based on Lemma13, [
V
b
1
∩
V
(
T
i
j
)
]
∪
[
V
b
2
∩
V
(
T
i
j
)
]
∪
[
V
b
3
∩
V
(
T
i
j
)
] is a 3-biclique partition of T
i
j. Therefore, we can directly consider obtaining the assignment of u
x,  u
y, and u
z from a 3-biclique partition of T
i
j.WhenT
i
j is T
i
1, based on Lemma 4, we have (f
(
u
x
)
,
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
,
1
)
,
(
0,2
,
2
)
,
(
0,0
,
1
)
}. Because d
i
2 of T
i
1 and d
i
2 of T
i
2 are of the same vertex, and d
i
3 of T
i
1 and d
i
3 of T
i
3 are of the same vertex in B, then the assignment of d
i
2 in T
i
1 is the same as that of d
i
2 in T
i
2, and the assignment of d
i
3 in T
i
1 is the same as that of d
i
3 in T
i
3. Therefore, the assignments of d
i
2 in T
i
2 and d
i
3 in T
i
3 must satisfy (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
}. When T
i
j is T
i
2 or T
i
3, based on Lemmas 6 and 8, we have (
f
(
u
y
)
,
f
(
d
i
2
)
)
∈
{
(
0,2
)
,
(
1,0
)
}
,
(
f
(
u
z
)
,
f
(
d
i
3
)
)
∈
{
(
1,2
)
,
(
0,1
)
}. Therefore, to ensure that (
f
(
d
i
2
)
,
f
(
d
i
3
)
)
∈
{
(
2,1
)
,
(
2,2
)
,
(
0,1
)
} holds, we must have (
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
} hold. It follows that if there is a 3-biclique partition for B, then (
f
(
u
x
)
,
f
(
u
y
)
,
f
(
u
z
)
)
∈
{
(
1,0
,
0
)
,
(
0,0
,
1
)
,
(
0,1
,
0
)
} holds.Because each variable corresponds to exactly one vertex inB, it is easy to obtain a truth assignment for all the variables: A
:
U
→
{
T
,
F
} from the vertex values of B. We merely set A
(
u
t
)
=
T if the assignment of u
t is f
(
u
t
)
=
1 in B and set A
(
u
t
)
=
F if the assignment of u
t is f
(
u
t
)
=
0 in B. After this assignment is made, an arbitrary clause c
i
=
{
u
x
,
u
y
,
u
z
} of an MO3 instance is set to (
A
(
u
x
)
,
A
(
u
y
)
,
A
(
u
z
)
)
∈
{
(
T
,
F
,
F
)
,
(
F
,
F
,
T
)
,
(
F
,
T
,
F
)
}, which satisfies the clause collection C of the MO3 instance.


## 3.2. The NP-Completeness ofk-PBB (k
>
3)

To prove the NP-completeness ofk-PBB for any k
>
3, we provide a reduction from 3-PBB as follows.Theorem 14.
k-PBB (k
>
3) is NP-complete, where k is a constant positive integer.Proof.
It is easy to see thatk-PBB ∈ NP because a nondeterministic algorithm need only guess a partition with size k of V
(
G
), which partitions V
(
G
) into k groups for a given bipartite graph G, and check in polynomial time whether the bipartite subgraph that is induced by each vertex group is a biclique.
We provide a reduction from 3-PBB. Given an input instanceG
1
=
(
X
1
,
Y
1
,
E
1
) of 3-PBB, we form an instance G
2
=
(
X
2
,
Y
2
,
E
2
) of k-PBB (k
>
3) as follows: X
2
=
X
1
∪
{
l
[
i
]
∣
1
≤
i
≤
k
-
3
}; Y
2
=
Y
1
∪
{
r
[
i
]
∣
1
≤
i
≤
k
-
3
}; E
2
=
E
1
∪
{
(
l
[
i
]
,
r
[
i
]
)
|
1
≤
i
≤
k
-
3
}. That is, we add 2
(
k
-
3
) vertices and (k
-
3) independent edges to G
1 for building G
2. Then G
2
=
(
X
2
,
Y
2
,
E
2
) becomes an instance of k-PBB (k
>
3). The subgraph formed by these additional vertices and edges consists of k
-
3 disjoint bicliques, and each biclique contains only one edge.
We have that there exists a 3-biclique partition forG
1 if and only if there exists a k-biclique partition for G
2 by the observation of G
1 and G
2. The theorem follows.By Theorems2 and 14, we get that Corollary 15 holds.Corollary 15.
k-PBB is NP-complete for k
≥
3, where k is a constant positive integer.


## 4. The Complexity ofk-SPBM

Next, we discuss the complexity ofk-SPBM. We show that k-SPBM is NP-complete for any k
≥
3.Theorem 16.
k-SPBM is NP-complete for an arbitrary k
≥
3, where k is a constant positive integer.Proof.
It is easy to see thatk-SPBM belongs to NP, given a binary matrix A, because a nondeterministic algorithm need only guess k submatrices with entries “1” of A and check in polynomial time whether these submatrices are a k-submatrix partition of A.
In what follows, we reducek-PBB to k-SPBM. Assume that B
=
(
X
,
Y
,
E
) is an instance of k-PBB, where X
=
{
x
[
1
]
,
x
[
2
]
,
…
,
x
[
m
]
}, Y
=
{
y
[
1
]
,
y
[
2
]
,
…
,
y
[
n
]
}. Thus, we construct an m
×
n binary matrix A
=
[
a
i
j
]
m
*
n, and we assign “0” or “1” to each entry of A by the following:
(10)
a
i
j
=
{
1
,
(
x
[
i
]
,
y
[
j
]
)
∈
E
,
0
,
(
x
[
i
]
,
y
[
j
]
)
∉
E
.
We next show that there exists a k-biclique partition for B if and only if A has a k-submatrix partition.
(
→
) Suppose that X
∪
Y
=
V
1
∪
V
2
∪
⋯
∪
V
k is a k-biclique partition of B. A submatrix A
i of A can be obtained from the vertex set V
i as follows. Let V
i
=
X
i
∪
Y
i, and let X
i
=
{
x
[
i
1
]
,
…
,
x
[
i
p
]
} and Y
i
=
{
y
[
j
1
]
,
…
,
y
[
j
q
]
} be the left and right vertex sets of B, respectively. Then let R
i
=
{
i
1
,
…
,
i
p
}, C
i
=
{
j
1
,
…
,
j
q
}. Thus, a submatrix A
i
=
A
[
R
i
,
C
i
] of A is selected. Note that, because V
1
,
V
2
,
…
,
V
k are a k-biclique partition of B, R
i
∩
R
j
=
∅, C
i
∩
C
j
=
∅, where i
≠
j, and R
1
∪
⋯
∪
R
k
=
{
1
,
…
,
m
}, C
1
∪
⋯
∪
C
k
=
{
1,2
,
…
,
n
}. Moreover, for j
s
∈
R
i, j
t
∈
C
i. Because (
x
[
i
s
]
,
y
[
j
t
]
)
∈
E, a
j
s
j
t
=
1; that is, each entry of A
i is “1.” Thus, A
1
,
A
2
,
…
,
A
k are a k-submatrix partition of A.
(
←
) Assume that A
1
=
A
[
R
1
,
C
1
]
,
…
,
A
k
=
A
[
R
k
,
C
k
] are submatrices of A, where R
i
∩
R
j
=
∅ (i
≠
j),  C
i
∩
C
j
=
∅
(
i
≠
j
),  R
1
∪
⋯
∪
R
k
=
{
1
,
…
,
m
},  C
1
∪
⋯
∪
C
k
=
{
1,2
,
…
,
n
}, and each entry of A
i is “1.” Then, for the vertex set V
i
=
{
x
[
i
s
]
,
y
[
j
t
]
|
i
s
∈
R
i
,
j
t
∈
C
i
} obtained from R
i and C
i, where 1
≤
i
≤
k, the bipartite subgraph of B induced by V
i is a biclique because each entry of A
i is “1.” Moreover, as A
1
,
…
,
A
k are pairwise row and column exclusive and each row (column) of A occurs in exactly one of these submatrices, X
∪
Y
=
V
1
∪
V
2
⋯
∪
V
k is a 3-biclique partition of B.


## 5. Applications

Large binary matrices arise in many applications, for example, market-basket data analysis, text mining, and community detection. In addition, we can transform a real matrix into a binary matrix in biclustering for convenient analysis [11, 21–24]; the same approach can be used for clustering [25–27]. Recently, because of its prevalence and importance, the biclustering problem in binary matrices has been widely applied to many domains [3, 24, 28], such as the following.(1)
Market-basket analysis: this goal aims at finding groups of customers who have similar purchasing preferences toward a subset of products. We are given a binary matrix with rows that correspond to customers and columns that correspond to products. If entry(
i
,
j
) of the matrix is “1,” then customer i purchased product j. If the entry is “0,” then the customer did not purchase that product. Clearly, a submatrix with entries “1” formed by a subset of rows and a subset of columns can reveal that the corresponding customers have similar purchasing preferences [3].
(2)
Gene expression data analysis: this analysis searches for groups of genes that have similar expression levels toward a subset of conditions. We are given a binary matrix with rows that correspond to genes and columns that correspond to conditions. If entry(
i
,
j
) of the matrix is “1,” then gene i was switched on under condition j. If the entry is “0,” then the gene was not switched on under the condition. A submatrix with entries “1” formed by a subset of rows and a subset of columns can reveal that it is highly likely that these genes in the submatrix either perform similar functions or are involved in the same biological process [11].
(3)
There are also many other applications, including community detection and text mining.The model ofk-SPBM can be used to analyze data that belong to different domains and can help extract previously unknown interesting patterns of biclusters.


## 6. Conclusions and Future Work

We have first proved that 3-PBB is NP-complete by reduction from MO3. Moreover, we have proved thatk-PBB (k
>
3) is NP-complete by reduction from 3-PBB, thus proving that k-PBB (k
≥
3) is NP-complete. Finally, we have shown that k-SPBM (k
≥
3) is NP-complete from the NP-completeness of k-PBB (k
≥
3).Becausek-SPBM (k
≥
3) is NP-complete, the problem has no polynomial time algorithm. Determining an efficient exact algorithm or an approximation algorithm is important, and it requires further research. We intend to study this problem in the future. Moreover, the complexity of some variants of finding bicliques in bipartite graphs is open, for example, the maximum ±1 edge weight biclique problem [15]. Additionally, we plan to study complexity and algorithms for these problems.



---

*Source: 934630-2014-07-03.xml*