Publications
Sort:
Open Access Issue
Efficient Maximum Vertex (k,)-Biplex Computation on Bipartite Graphs
Tsinghua Science and Technology 2025, 30(2): 569-584
Published: 09 December 2024
Abstract PDF (2.2 MB) Collect
Downloads:264

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.

Total 1