Efficient Maximum Vertex $(\mathit{k},\mathit{\ell })$-Biplex Computation on Bipartite Graphs

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