  Enumerating maximal $k$-biplexes (MBPs) of a bipartite graph has been used
for applications such as fraud detection. Nevertheless, there usually exists an
exponential number of MBPs, which brings up two issues when enumerating MBPs,
namely the effectiveness issue (many MBPs are of low values) and the efficiency
issue (enumerating all MBPs is not affordable on large graphs). Existing
proposals of tackling this problem impose constraints on the number of vertices
of each MBP to be enumerated, yet they are still not sufficient (e.g., they
require to specify the constraints, which is often not user-friendly, and
cannot control the number of MBPs to be enumerated directly). Therefore, in
this paper, we study the problem of finding $K$ MBPs with the most edges called
MaxBPs, where $K$ is a positive integral user parameter. The new proposal well
avoids the drawbacks of existing proposals. We formally prove the NP-hardness
of the problem. We then design two branch-and-bound algorithms, among which,
the better one called FastBB improves the worst-case time complexity to
$O^*(\gamma_k^ n)$, where $O^*$ suppresses the polynomials, $\gamma_k$ is a
real number that relies on $k$ and is strictly smaller than 2, and $n$ is the
number of vertices in the graph. For example, for $k=1$, $\gamma_k$ is equal to
$1.754$. We further introduce three techniques for boosting the performance of
the branch-and-bound algorithms, among which, the best one called PBIE can
further improve the time complexity to $O^*(\gamma_k^{d^3})$ for large sparse
graphs, where $d$ is the maximum degree of the graph. We conduct extensive
experiments on both real and synthetic datasets, and the results show that our
algorithm is up to four orders of magnitude faster than all baselines and
finding MaxBPs works better than finding all MBPs for a fraud detection
application.
