Efficient Maximum Vertex (k, l)-Biplex Computation on Bipartite Graphs

Cohesive subgraph search is a fundamental problem in bipartite graph analysis. Given integers k and l, a (k,l)-biplex is a cohesive structure which requires each vertex to disconnect at most k or l vertices in the other side. Computing (k,l)-biplexes has been a popular research topic in recent years and has various applications. However, most existing studies considered the problem of finding (k, l)-biplex with the largest number of edges. In this paper, we instead consider another variant and focus on the maximum vertex (k, l)-biplex problem which aims to search for a (k, l)-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 l while max{k, l} 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 gamma(n)n(O(1)), where gamma < 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.