{"ID":6138269,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T13:47:13.783731841Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07419","arxiv_id":"2607.07419","title":"Revisiting Maximum $k$-Biplex Search Through $k$-Bounded-Degree Deletion","abstract":"Biplex, as a relaxation of the biclique model, has emerged as an important cohesive subgraph model for bipartite graph analysis. The maximum $k$-biplex search problem aims to identify the $k$-biplex with maximum number of edges and has been widely applied in various real-world applications, including community detection, online recommendation, and fraud detection. However, the problem is NP-hard, and existing exact algorithms remain inefficient on large-scale bipartite graphs with large values of $k$ (e.g., $k\\geq 3$). In this paper, we revisit the maximum $k$-biplex search problem from a complementary perspective. We reveal a novel structural duality: finding a maximum $k$-biplex in a bipartite graph is equivalent to finding a minimal $k$-bounded-degree deletion in its complement graph. Based on this observation, we propose a novel deletion-based algorithm for the maximum $k$-biplex search problem. We theoretically prove that the proposed algorithm achieves a worst-case time complexity of $O^*(γ_k^n)$, where $γ_k\u003c2$. Specifically, $γ_1=1.725$, $γ_2=1.856$, and $γ_3=1.928$. To further enhance practical efficiency, we develop several effective upper-bounding techniques and a heuristic strategy for obtaining high-quality initial solutions, which substantially reduce the search space. Extensive experiments on eight real-world bipartite graphs demonstrate the efficiency of our approach, which achieves up to four orders of magnitude speedups over state-of-the-art algorithms.","short_abstract":"Biplex, as a relaxation of the biclique model, has emerged as an important cohesive subgraph model for bipartite graph analysis. The maximum $k$-biplex search problem aims to identify the $k$-biplex with maximum number of edges and has been widely applied in various real-world applications, including community detectio...","url_abs":"https://arxiv.org/abs/2607.07419","url_pdf":"https://arxiv.org/pdf/2607.07419v1","authors":"[\"Donghang Cui\",\"Ronghua Li\",\"Qiangqiang Dai\",\"Guoren Wang\"]","published":"2026-07-08T13:47:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}