195
Views
191
Downloads
0
Crossref
0
WoS
0
Scopus
0
CSCD
Cohesive subgraph search is a fundamental problem in bipartite graph analysis. 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 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.
© The author(s) 2024.
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).