@article{Zhou2025, 
author = {Hongru Zhou and Shengxin Liu and Ruidi Cao},
title = {Efficient Maximum Vertex  (k,ℓ)-Biplex Computation on Bipartite Graphs},
year = {2025},
journal = {Tsinghua Science and Technology},
volume = {30},
number = {2},
pages = {569-584},
keywords = {bipartite graphs, cohesive subgraph search, branch-and-bound algorithm, maximum vertex $(k,\ell)$-biplex},
url = {https://www.sciopen.com/article/10.26599/TST.2024.9010009},
doi = {10.26599/TST.2024.9010009},
abstract = {Cohesive subgraph search is a fundamental problem in bipartite graph analysis. Given integers  k and  ℓ, a  (k,ℓ)-biplex is a cohesive structure which requires each vertex to disconnect at most  k or  ℓ vertices in the other side. Computing  (k,ℓ)-biplexes has been a popular research topic in recent years and has various applications. However, most existing studies considered the problem of finding  (k,ℓ)-biplex with the largest number of edges. In this paper, we instead consider another variant and focus on the maximum vertex  (k,ℓ)-biplex problem which aims to search for a  (k,ℓ)-biplex with the maximum cardinality. We first show that this problem is Non-deterministic Polynomial-time hard (NP-hard) for any positive integers  k and  ℓ while  max{k,ℓ} is at least 3. Guided by this negative result, we design an efficient branch-and-bound algorithm with a novel framework. In particular, we introduce a branching strategy based on whether there is a pivot in the current set, with which our proposed algorithm has the time complexity of  γnnO(1), where  γ<2. In addition, we also apply multiple speed-up techniques and various pruning strategies. Finally, we conduct extensive experiments on various real datasets which demonstrate the efficiency of our proposed algorithm in terms of running time.}
}