Revisiting Maximum \(k\)-Biplex Search Through \(k\)-Bounded-Degree Deletion
July 08, 2026
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^*(\gamma_k^n)\), where \(\gamma_k<2\). Specifically, \(\gamma_1=1.725\), \(\gamma_2=1.856\), and \(\gamma_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.
1 Introduction↩︎
Bipartite graphs are fundamental data structures for modeling interactions between two distinct groups of entities, such as user-item interactions in e-commerce networks [1], [2], author-publication relationships in academic networks [3], and gene-protein associations in computational biology networks [4]–[6]. Identifying cohesive subgraphs is a core task in bipartite graph mining, since such subgraphs often reveal meaningful groups with strong cross-side associations. For example, in computational biology networks, cohesive subgraphs can capture groups of genes and proteins with strong expression associations, thereby helping identify functional modules or disease-related biological pathways [6].
As a classical cohesive subgraph model in bipartite graphs, the biclique has been widely studied and applied in many scenarios [7]–[9]. A biclique is a complete bipartite subgraph, where every vertex on one side is connected to all vertices on the other side. The maximum biclique search problem aims to find a biclique containing the maximum number of edges, which has attracted considerable attention in recent years [10]–[15]. However, real-world network data are inevitably affected by observation noise, measurement errors, and missing data [16], [17]. Due to the strict complete-connectivity requirement, the biclique is unable to represent cohesive communities that contain a small number of missing edges, which limits its practical application.
To address this limitation, the \(k\)-biplex model was introduced as a relaxation of the biclique and has attracted increasing attention in recent years [2], [12], [18]–[22]. Formally, in a \(k\)-biplex of a bipartite graph, each vertex has at most \(k\) non-neighbors. This relaxation allows limited missing edges while preserving its cohesion, and has been applied to many real-world tasks such as online recommendation [23], [24], community detection [12], [25], and fraud detection [2], [12]. In this paper, we study the problem of finding a \(k\)-biplex with the maximum number of edges, which is referred to as the maximum \(k\)-biplex search problem. This problem has been proven to be NP-hard for any positive integer \(k\) [22], implying that no polynomial-time algorithm exists unless \(\mathrm{P}=\mathrm{NP}\).
To solve the maximum \(k\)-biplex search problem, several exact algorithms have been developed in recent years [2], [21], [22]. These algorithms mainly follow the branch-and-bound framework by deciding which vertices should be included in the target \(k\)-biplex, and they reduce the number of branches with carefully-designed branching and pruning strategies. However, these algorithms are mainly effective for small \(k\) values, and their performance substantially degrades when \(k\) becomes large, as shown in Table 3. For example, on most real-world graphs, existing algorithms struggle to solve most test cases when \(k\ge 3\). In particular, on the dataset Aol, existing algorithms fail to handle any test cases even when \(k\ge 2\).
Notably, several studies have proposed algorithms for maximal \(k\)-biplex enumeration [12], [18]–[20]. A natural way to apply these algorithms to the maximum \(k\)-biplex search problem is to enumerate all maximal \(k\)-biplexes and then select the one with the maximum number of edges. However, the number of maximal \(k\)-biplexes in a bipartite graph can be exponential with respect to the graph size. Directly applying these enumeration algorithms may generate a large number of maximal but non-maximum \(k\)-biplexes, thereby causing a large amount of unnecessary computation and making them inefficient in practice. Consequently, developing a theoretically and practically efficient algorithm for the maximum \(k\)-biplex search remains a challenging task.
Contributions. To address the aforementioned challenges, we propose a novel deletion-based algorithm for the maximum \(k\)-biplex search problem with a non-trivial worst-case time complexity. We also propose several optimization techniques to further improve the practical performance of the algorithm. The main contributions of this paper are as follows.
A novel deletion-based algorithm. We reveal the structural connection between maximum \(k\)-biplex search in the original bipartite graph and \(k\)-bounded-degree deletion in the complement graph. Based on this connection, we propose a deletion-based algorithm for maximum \(k\)-biplex search. Specifically, we first propose a novel deletion-based branching strategy, which decides which vertices to be deleted from the subgraph. We then develop several branch reduction techniques to further enhance the performance of the deletion-based branching strategy. Finally, we prove that our deletion-based algorithm achieves a non-trivial worst-case time complexity of \(O^*(\gamma_k^n)\). When \(k=1,2\) and \(3\), we have \(\gamma_1=1.725\), \(\gamma_2=1.856\) and \(\gamma_3=1.928\), respectively. To the best of our knowledge, our algorithm achieves the best known time complexity among all existing algorithms for maximum \(k\)-biplex search.
Efficient optimization techniques. To further improve the practical performance of the proposed deletion-based algorithm, we design several optimization techniques tailored to the deletion-based search framework. Specifically, we propose two efficient edge upper bounds to prune search branches that cannot generate a larger \(k\)-biplex. The first upper bound is derived from the newly added vertex and limits how many of its non-neighbors can still be kept; the second upper bound is derived from the total missing-edge allowance of the current partial solution on one side. We show that these upper bounds can be computed in linear time for each search instance. Finally, we develop a heuristic algorithm to quickly construct a large initial \(k\)-biplex in polynomial time, combining a greedy deletion stage with a localized expansion stage based on the distance property of large \(k\)-biplexes.
Comprehensive experiments. We conduct extensive experiments on 8 real-world bipartite graphs to evaluate the efficiency and scalability of our proposed algorithm. We compare our algorithm with two state-of-the-art maximum \(k\)-biplex search algorithms under various settings of \(k\) and \(\theta\). The experimental results demonstrate that our proposed algorithm substantially outperforms existing solutions, achieving up to four orders of magnitude speedups. For example, our algorithm solves all test cases on the graph Aol, while the baseline algorithms fail to solve most test cases within 24 hours. More specifically, our algorithm finds a maximum \(4\)-biplex on Aol with both side sizes larger than \(17\) in only \(6.14\) seconds, while the other two baseline algorithms cannot finish within 24 hours, demonstrating that our algorithm is up to four orders of magnitude faster than the state-of-the-art approaches.
2 Preliminaries↩︎
Let \(G=(U,V,E)\) be a bipartite graph, where \(U\) and \(V\) are two disjoint sets of vertices, and \(E\subseteq U\times V\) is the set of edges between vertices in \(U\) and \(V\). Let \(n=\lvert U\rvert+\lvert V\rvert\) and \(m=\lvert E\rvert\) be the number of vertices and edges in \(G\), respectively. For every vertex \(u\in U\) (resp. \(v\in V\)), let \(N(u)=\{v\in V\;\vert\;(u,v)\in E\}\) (resp. \(N(v)=\{u\in U\;\vert\;(u,v)\in E\}\)) be the set of \(u\)’s (resp. \(v\)’s) neighbors in \(G\), and let \(\overline{N}(u)=V\setminus N(u)\) (resp. \(\overline{N}(v)=U\setminus N(v)\)) be the set of \(u\)’s (resp. \(v\)’s) non-neighbors in \(G\). For every vertex \(v\in U\cup V\), let \(d(v)=\lvert N(v)\rvert\) and \(\overline{d}(v)=\lvert \overline{N}(v)\rvert\) be the degree and non-degree of \(v\) in \(G\), respectively. Let \(\delta=\max_{v\in U\cup V} d(v)\) and \(\overline{\delta}=\max_{v\in U\cup V}\overline{d}(v)\) be the maximum degree and maximum non-degree of vertices in \(G\), respectively. Given a vertex subset \(S=(U_S,V_S)\) of \(G\), where \(U_S\subseteq U\) and \(V_S\subseteq V\), let \(G[S]=(U_S,V_S,E_S)\) be the subgraph of \(G\) induced by \(S\), where \(E_S=\{(u,v)\in E\;\vert\;u\in U_S\land v\in V_S\}\) is the set of edges between vertices in \(U_S\) and \(V_S\). For every vertex \(v\in S\), let \(N_S(v)=N(v)\cap S\) and \(\overline{N}_S(v)=\overline{N}(v)\cap S\) be the set of \(v\)’s neighbors and non-neighbors in \(G[S]\), respectively. Let \(d_S(v)=\lvert N_S(v)\rvert\) and \(\overline{d}_S(v)=\lvert \overline{N}_S(v)\rvert\) be the degree and non-degree of \(v\) in \(G[S]\), respectively. Let \(\delta_S=\max_{v\in S} d_S(v)\) and \(\overline{\delta}_S=\max_{v\in S}\overline{d}_S(v)\) be the maximum degree and maximum non-degree of vertices in \(G[S]\), respectively. Given a bipartite graph \(G=(U,V,E)\), let \(\overline{G}=(U,V,\overline{E})\) be the complement graph of \(G\), where \(\overline{E}=U\times V\setminus E\) is the set of all missing edges in \(G\). Given a vertex subset \(S=(U_S,V_S)\), let \(\overline{G}[S]=(U_S,V_S,\overline{E}_S)\) be the subgraph of \(\overline{G}\) induced by \(S\), i.e., the complement graph of \(G[S]\), where \(\overline{E}_S=U_S\times V_S\setminus E_S\) is the set of all missing edges in \(G[S]\). All the notations frequently used in this paper are presented in Table 1.
| Notations | Descriptions |
|---|---|
| \(G=(U,V,E)\) | a bipartite graph |
| \(\overline G=(U,V,\overline E)\) | the complement graph of \(G\) |
| \(S=(U_S,V_S)\) | a vertex subset of \(G\), with \(U_S\subseteq U\) and \(V_S\subseteq V\) |
| \(G[S]=(U_S,V_S,E_S)\) | a subgraph of \(G\) induced by \(S\) |
| \(\overline E_S\) | the set of non-edges in \(G[S]\) |
| \(N(v)\), \(\overline N(v)\) | the set of \(v\)’s neighbors and non-neighbors in \(G\) |
| \(d(v)\), \(\overline d(v)\) | the number of \(v\)’s neighbors and non-neighbors in \(G\) |
| \(N_S(v)\), \(\overline N_S(v)\) | the set of \(v\)’s neighbors and non-neighbors in \(S\) |
| \(d_S(v)\), \(\overline d_S(v)\) | the number of \(v\)’s neighbors and non-neighbors in \(S\) |
| \(\delta\), \(\overline\delta\) | the maximum degrees of vertices in \(G\) and \(\overline G\) |
| \(\delta_S\), \(\overline\delta_S\) | the maximum degrees of vertices in \(G[S]\) and \(\overline G[S]\) |
Formally, the \(k\)-biplex is defined as follows.
Definition 1 (\(k\)-biplex). For a bipartite graph \(G=(U,V,E)\), a \(k\)-biplex \(G[S]\) is a subgraph of \(G\) induced by \(S=(U_S,V_S)\), where every vertex has at most \(k\) non-neighbors, i.e., \(\forall v\in S,\;\overline{d}_S(v)\le k\).
A \(k\)-biplex of \(G\) is called maximal if it cannot be included into another \(k\)-biplex of \(G\), and is called maximum if it has the most edges among all maximal \(k\)-biplexes of \(G\). For real-world bipartite graphs, we aim to find the maximum \(k\)-biplex to identify their most representative community. However, the maximum \(k\)-biplex of a bipartite graph may be disconnected, which is unsuitable for representing a meaningful community. To overcome this problem, we can constraint the number of vertices in each side of the target maximum \(k\)-biplex to ensure its connectivity, as presented in the following lemma [2].
Lemma 1. A \(k\)-biplex \(S=(U_S,V_S)\) is connected if \(\lvert U_S\rvert\ge 2k+1\) and \(\lvert V_S\rvert\ge 2k+1\).
Furthermore, a \(k\)-biplex with highly unbalanced number of vertices between the two sides (e.g. a 1-biplex where one side contains only 3 vertices while the other comprises thousands) has limited practical significance despite its connectivity. Therefore, we impose a threshold \(\theta\) on the number of vertices for both sides. Formally, we define the problem investigated in this study as follows.
Problem statement 1 (Maximum \(k\)-biplex search). Given a bipartite graph \(G=(U,V,E)\) and two positive integers \(\theta\) and \(k\), where \(\theta\ge 2k+1\), the maximum \(k\)-biplex search problem aims to find a \(k\)-biplex \(S=(U_S,V_S,E_S)\) with the maximum number of edges in \(G\) such that \(\lvert U_S\rvert\ge \theta\) and \(\lvert V_S\rvert\ge \theta\).
NP-hardness. As established in [2], the maximum \(k\)-biplex search problem is NP-hard, which implies there is no polynomial algorithm for solving it unless \(\mathrm{P}=\mathrm{NP}\). Consequently, it is essential to develop a maximum \(k\)-biplex search algorithm that is both theoretically and practically efficient. a
2.1 Existing Solutions↩︎
Several exact approaches have been proposed to solve the maximum \(k\)-biplex search problem [2], [22]. Below, we briefly review their main technical ideas and limitations.
Yu et al. [2] studied the problem of finding \(K\) maximal \(k\)-biplexes with the most edges, where \(K=1\) corresponds to our problem. They proposed a branch-and-bound algorithm based on a symmetric Bron–Kerbosch branching strategy. Specifically, the algorithm chooses a pivot vertex \(u\) with at least \(k+1\) non-neighbors \(v_1,v_2,\ldots,v_{k+1}\) in the current subgraph, and then generates subbranches in the following way: the first branch excludes \(u\) from the subgraph, and the \(i+1\)-th branch excludes \(v_i\) while adding \(u,v_1,\ldots,v_{i-1}\) into the \(k\)-biplex. Since \(u\) has at most \(k\) non-neighbors in a \(k\)-biplex, at most \(k+2\) subbranches will be generated. With this branching strategy, their algorithm achieves a worst-case time complexity \(O^*(\alpha_k^n)\), where \(\alpha_k<2\); when \(k=1,2,\) and \(3\), \(\alpha_k=1.754,1.888,\) and \(1.947\), respectively. This branching strategy is effective when \(k\) is small, but becomes less efficient when \(k\) increases. This is because the number of subbranches generated by the symmetric-BK branching strategy depends heavily on \(k\). When \(k\) increases, the rapid increase in the number of branches results in an excessively large search space, thereby reducing search efficiency.
Pan et al. [22] studied the maximum \(k\)-biplex search problem over large bipartite graphs and proposed a core-based graph reduction framework. Specifically, for every possible side-size pair \((x,y)\) of the target \(k\)-biplex, they compute the corresponding \((x,y)\)-core, where vertices on the two sides have degree at least \(y-k\) and \(x-k\), respectively. The algorithm then examines every pair \((x,y)\) in decreasing order of the value \(x\cdot y\). For the current pair \((x,y)\), it runs branch-and-bound search on the corresponding \((x,y)\)-core to find a \(k\)-biplex \(S=(U_S,V_S,E_S)\) with \(|U_S|=x\) and \(|V_S|=y\). Once such a solution is found, all remaining pairs \((x',y')\) with \(x'\cdot y'\le |E_S|\) can be safely discarded, because no \(k\)-biplex with these side sizes can contain more than \(x'\cdot y'\) edges. If no such \(k\)-biplex is found in the current core, the algorithm continues to the next pair. However, the effectiveness of this core-based reduction decreases as \(k\) becomes large. For a fixed side-size pair \((x,y)\), the degree requirements of the corresponding core are \(y-k\) and \(x-k\), respectively. Thus, a larger \(k\) directly lowers these requirements and allows more vertices to remain in the reduced graph. As a result, the branch-and-bound search is still conducted on a large core. Moreover, since a larger \(k\) allows more missing edges in the target \(k\)-biplex, the pruning rules become less restrictive, further increasing the search cost.
3 A Novel Deletion-based Algorithm↩︎
In this section, we propose a novel deletion-based algorithm for the maximum \(k\)-biplex search problem, which solves the problem from the complement graph: instead of deciding which vertices should be kept in the original graph, we decide which vertices should be deleted so that the remaining complement subgraph has bounded degree. We prove that our algorithm achieves a non-trivial worst-case time complexity of \(O^*(\gamma_k^n)\), where \(\gamma_k<2\). For example, when \(k=1,2\) and \(3\), we have \(\gamma_1=1.725\), \(\gamma_2=1.856\) and \(\gamma_3=1.928\), respectively. To the best of our knowledge, our algorithm achieves the best known time complexity among all existing algorithms for maximum \(k\)-biplex search.
3.1 Deletion-based Branching Framework↩︎
We first introduce the concept of deletion in bipartite graphs. Given a bipartite graph \(G=(U,V,E)\), the \(k\)-bounded-degree deletion of \(G\) is defined as follows.
Definition 2 (\(k\)-bounded-degree deletion). Given a bipartite graph \(G=(U,V,E)\) and a positive integer \(k\), a \(k\)-bounded-degree deletion of \(G\) is a vertex subset \(D\subseteq U\cup V\) such that after deleting all vertices in \(D\) from \(G\), the maximum degree of the remaining subgraph \(G[(U\cup V)\setminus D]\) is at most \(k\).
For convenience of discussion, we refer to a \(k\)-bounded-degree deletion as a \(k\)-BDD in this paper. We say a \(k\)-BDD \(D\) is minimal in \(G\) if there is no other \(k\)-BDD \(D'\) in \(G\) satisfying that \(D'\subset D\). We then discuss the relationship between \(k\)-biplex and \(k\)-BDD in bipartite graphs. Given a \(k\)-biplex \(S\) of \(G\), let \(D=(U\cup V)\setminus S\). Since every vertex in \(S\) has at most \(k\) non-neighbors in \(G[S]\), the maximum degree of \(\overline{G}[S]\) is at most \(k\). Hence, \(D\) is a \(k\)-BDD of \(\overline{G}\). Conversely, if \(D\) is a \(k\)-BDD of \(\overline{G}\), then the remaining vertex set \((U\cup V)\setminus D\) induces a \(k\)-biplex in \(G\). However, this correspondence does not mean that the maximum \(k\)-biplex can be obtained by finding a \(k\)-BDD that leaves the fewest edges in the complement graph. For example, consider \(k=1\) and \(\theta=2\). Let \(U=\{u_1,u_2,u_3\}\) and \(V=\{v_1,v_2,v_3\}\), and let \(G\) contain all edges except \((u_3,v_3)\). Then \(G[U\cup V]\) is a \(1\)-biplex with eight edges, and thus it is the maximum \(1\)-biplex. In \(\overline{G}\), this solution leaves one complement edge. In contrast, if we keep only \(\{u_1,u_2\}\cup\{v_1,v_2\}\), the remaining complement graph has no edge, but the corresponding subgraph of \(G\) has only four edges, and hence is not the maximum \(k\)-biplex of \(G\). To overcome this limitation, we develop the new relationship between the maximum \(k\)-biplex of \(G\) and the \(k\)-BDD of \(\overline{G}\), which builds upon the following lemma.
Lemma 2. Given a bipartite graph \(G=(U,V,E)\) and a maximum \(k\)-biplex \(G[S]=(U_S,V_S,E_S)\) of \(G\), \((U\cup V)\setminus S\) forms a minimal \(k\)-BDD of \(\overline{G}\).
Proof. We prove this lemma by contradiction. Let \(D=(U\cup V)\setminus S\). If there exists a minimal \(k\)-BDD \(D'\) in \(\overline{G}\) satisfying \(D'\subset D\), we have \(S=(U\cup V)\setminus D\subset (U\cup V)\setminus D'\), which means \(G[(U\cup V)\setminus D']\) forms a \(k\)-biplex that contains \(G[S]\), contradicting the maximality. Therefore, \(G[S]\) is not a maximum \(k\)-biplex of \(G\), which contradicts the condition. ◻
Based on this lemma, we propose a new structural duality that a maximum \(k\)-biplex of \(G\) always corresponds to a specific minimal \(k\)-BDD of \(\overline{G}\), as shown in the following theorem.
Theorem 1 (Structural Duality). Let \(G=(U,V,E)\) be a bipartite graph and \(\overline{G}=(U,V,\overline{E})\) be its complement. If a minimal \(k\)-BDD \(D=(U_D,V_D)\) of \(\overline{G}\) satisfies \(\lvert U_D\rvert\le\lvert U\rvert-\theta\) and \(\lvert V_D\rvert\le\lvert V\rvert-\theta\), and maximizes \(\lvert U\setminus U_D\rvert\times\lvert V\setminus V_D\rvert-\lvert \overline{E}_{(U\cup V)\setminus D}\rvert\) among all minimal \(k\)-BDDs in \(\overline{G}\) satisfying these two constraints, then \(G[U\cup V\setminus D]\) is a maximum \(k\)-biplex of \(G\).
Proof. Let \(S=(U\setminus U_D,V\setminus V_D)\). Since \(D\) is a \(k\)-BDD of \(\overline{G}\), the maximum degree of \(\overline{G}[S]\) is at most \(k\). Equivalently, every vertex in \(G[S]\) has at most \(k\) non-neighbors. Thus, \(G[S]\) is a \(k\)-biplex. As \(\lvert U_D\rvert\le\lvert U\rvert-\theta\) and \(\lvert V_D\rvert\le\lvert V\rvert-\theta\), we have \(\lvert U_S\rvert=\lvert U\setminus U_D\rvert\ge\theta\) and \(\lvert V_S\rvert=\lvert V\setminus V_D\rvert\ge\theta\). Since \(|E_S|=|U_S|\times|V_S|-|\overline{E}_S|=\lvert U\setminus U_D\rvert\times\lvert V\setminus V_D\rvert-\lvert \overline{E}_{(U\cup V)\setminus D}\rvert\), and the complement vertex set of a maximum \(k\)-biplex of \(G\) is always a minimal \(k\)-BDD of \(\overline{G}\) according to Lemma 2, maximizing \(|E_S|\) among all \(k\)-biplexes in \(G\) is equivalent to maximizing \(\lvert U\setminus U_D\rvert\times\lvert V\setminus V_D\rvert-\lvert \overline{E}_{(U\cup V)\setminus D}\rvert\) among all minimal \(k\)-BDDs in \(\overline{G}\). ◻
Theorem 1 reformulates the maximum \(k\)-biplex search problem as finding a specific minimal \(k\)-BDD in the complement graph. Based on this formulation, we develop deletion-based branching and reduction strategies tailored to the maximum \(k\)-biplex search problem. Specifically, given a bipartite graph \(G=(U,V,E)\) and its complement graph \(\overline{G}=(U,V,\overline{E})\), let \((D,S,C)\) be an instance of our deletion-based algorithm, where \(D\subseteq U\cup V\) is the partial deletion set containing vertices that have been deleted from \(\overline{G}\), \(S\subseteq U\cup V\) is the partial \(k\)-biplex set containing vertices that cannot be deleted from \(\overline{G}\) (i.e., the vertices that must be kept in the maximum \(k\)-biplex), and \(C\subseteq U\cup V\) is the candidate set containing vertices to be moved to \(D\) or \(S\). The three sets are disjoint, and \(G[S]\) is maintained as a valid \(k\)-biplex throughout the search. The instance \((D,S,C)\) aims to find a minimal \(k\)-BDD \(D^*\subseteq C\) in \(\overline{G}[S\cup C]\) such that \(G[(U\cup V)\setminus (D\cup D^*)]\) is a maximum \(k\)-biplex of \(G[S\cup C]\) containing \(S\). In particular, the initial instance \(((\emptyset,\emptyset),(\emptyset,\emptyset),(U,V))\) aims to find such a \(k\)-BDD in \(\overline{G}\), which corresponds to a maximum \(k\)-biplex of \(G\).
Given an instance \((D,S,C)\), our algorithm selects a vertex \(u\in S\cup C\) and generate subbranches in the following way: if the selected vertex is in \(C\), generate one subbranch that moves it to \(D\); the remaining branches handle the cases where it is kept in \(S\). For convenience, we refer to such a vertex \(u\) as a branching vertex of the current instance \((D,S,C)\). Our algorithm then recursively applies this branching method until \(D\) forms a minimal \(k\)-BDD of \(\overline{G}\), where \(G[S\cup C]\) gives a candidate solution for the maximum \(k\)-biplex of \(G\). More specifically, our deletion-based branching strategy relies on the following branching rule.
Theorem 2 (Deletion-based branching rule). Given a bipartite graph \(G\) and a vertex \(v\) of \(G\), any \(k\)-BDD of \(\overline{G}\) must contain either \(v\) or at least \(\overline{d}(v)-k\) of \(v\)’s neighbors in \(\overline{G}\).
Proof. Consider a \(k\)-BDD \(D\) of \(\overline{G}\). If \(v\in D\), the theorem holds directly. Otherwise, \(v\) remains in \(\overline{G}\setminus D\). According to the definition of \(k\)-BDD, at most \(k\) neighbors of \(v\) in \(\overline{G}\) can remain together with \(v\). Therefore, at least \(\overline{d}(v)-k\) neighbors of \(v\) in \(\overline{G}\) must be contained in \(D\). ◻
According to Theorem 2, selecting a branching vertex \(u\in C\) with a large degree in \(\overline{G}[S\cup C]\) creates a strong branching condition: once \(u\) is kept, at least \(\overline{d}_{S\cup C}(u)-k\) vertices in \(\overline{N}_C(u)\) must be deleted. Therefore, to delete as many vertices as possible from \(C\), we can choose \(u\in C\) with the maximum value of \(\overline{d}_{S\cup C}(u)\). With this observation, we propose our deletion-based branching strategy as follows.
Our deletion-based branching strategy. Given the instance \((D,S,C)\), let \(u=\mathrm{\arg\max}_{v\in S\cup C}\overline{d}_{S\cup C}(v)\) be the branching vertex. If \(\overline{d}_{S\cup C}(u)>k\), let \(r=\overline{d}_{S\cup C}(u)-k\) and \(\overline{N}_C(u)=\{v_1,v_2,\dots,v_{\overline{d}_C(u)}\}\) in decreasing order of \(\overline{d}_{S\cup C}(\cdot)\). The new subinstances are generated as follows.
If \(r\le 0\), \(D\) forms a minimal \(k\)-BDD of \(\overline{G}\), update the current best solution with \(G[S\cup C]\) and return.
If \(u\in C\), generate one subinstance \((D\cup\{u\},S,C\setminus\{u\})\), corresponding to the case where \(u\) is deleted. After this subinstance returns, add \(u\) to \(S\).
For each \(i=r,r+1,\ldots,\overline{d}_C(u)\), regard \(v_i\) as the \(r\)-th deleted vertex in the order of \(\overline{N}_C(u)\). For every vertex subset \(P\subseteq\{v_1,v_2,\dots,v_{i-1}\}\) with \(|P|=r-1\), generate the subinstance \((D\cup P\cup\{v_i\},S\cup(\{v_1,v_2,\dots,v_{i-1}\}\setminus P),C\setminus\{v_1,v_2,\dots,v_i\})\), corresponding to the case where \(v_i\) and \(r-1\) vertices from \(v_1,v_2,\dots,v_{i-1}\) are deleted.
Figure 1 illustrates the one-level branches generated by our deletion-based branching strategy. The first branch deletes the branching vertex \(u\), while the remaining branches keep \(u\) and delete two vertices from \(\overline{N}_C(u)\). These branches are grouped by the last deleted vertex in the ordered set \(\overline{N}_C(u)\).
3.2 Branch Reduction Techniques↩︎
We introduce several branch reductions to further enhance the efficiency of our deletion-based branching strategy. First, we reduce \(C\) through vertices with a large number of non-neighbors in \(S\).
Lemma 3 (Branch Reduction 1). Given an instance \((D,S,C)\) and a vertex \(u\in C\), if \(\overline{d}_S(u)>k\) or there exists \(v\in \overline{N}_S(u)\) satisfying \(\overline{d}_S(v)\ge k\), we can move \(u\) from \(C\) to \(D\) directly.
Proof. We prove it by contradiction. If \(\overline{d}_S(u)>k\) and \(u\) is not included in any \(k\)-BDD \(D'\) derived from \((D,S,C)\), then \(u\) will have more than \(k\) neighbors in \(\overline{G}[(S\cup C)\setminus D']\) and thus \(D'\) is not a \(k\)-BDD of \(\overline{G}\). Similarly, if there exists \(v\in \overline{N}_S(u)\) with \(\overline{d}_S(v)\ge k\), then \(v\) will have at least \(k+1\) neighbors in \(\overline{G}[(S\cup C)\setminus D']\) and thereby \(D'\) is not a \(k\)-BDD of \(\overline{G}\) as well. ◻
Then, we reduce \(C\) through vertices that cannot be contained in any \(k\)-biplex satisfying the size threshold \(\theta\).
Lemma 4 (Branch Reduction 2). Given an instance \((D,S,C)\) and a vertex \(u\in C\), if \(d_{S\cup C}(u)<\theta-k\), we can move \(u\) from \(C\) to \(D\) directly.
Proof. Assume that a \(k\)-biplex \(S'\) derived from \((D,S,C)\) contains \(u\). Since the opposite side of \(u\) in \(S'\) has at least \(\theta\) vertices, vertex \(u\) must have at least \(\theta-k\) neighbors in \(S'\). However, \(S'\subseteq S\cup C\), and hence \(d_{S'}(u)\le d_{S\cup C}(u)<\theta-k\), a contradiction. Therefore, \(u\) cannot be contained in any solution and can be moved to \(D\). ◻
Intuitively, if adding a candidate vertex from \(C\) to \(S\) does not make itself or any of its non-neighbors violate the \(k\)-biplex constraint, then keeping this vertex can only enlarge the solution. This leads to the following reduction.
Lemma 5 (Branch Reduction 3). Given an instance \((D,S,C)\) and a vertex \(u\in C\), if \(\forall v\in \{u\}\cup \overline{N}_{S\cup C}(u), \overline{d}_{S\cup C}(v)\le k\), we can move \(u\) from \(C\) to \(S\) directly.
Proof. Let \(S'\) be any \(k\)-biplex derived from \((D,S,C)\) that does not contain \(u\). We show that \(S'\cup\{u\}\) is still a \(k\)-biplex. Since \(\overline{d}_{S\cup C}(u)\le k\) and \(S'\cup\{u\}\subseteq S\cup C\), vertex \(u\) has at most \(k\) non-neighbors in \(S'\cup\{u\}\). Furthermore, for any vertex \(v\in \overline{N}_{S'}(u)\), we have \(\overline{d}_{S'\cup\{u\}}(v)\le \overline{d}_{S\cup C}(v)\le k\). The non-degrees of all other vertices in \(S'\) remain unchanged after adding \(u\) to \(S'\). Thus, after adding \(u\), \(S'\cup\{u\}\) is still a \(k\)-biplex. ◻
We notice that the branching size can be further reduced for the case \(\overline{\delta}_{S\cup C}=k+1\). In this case, every vertex in \(\overline{G}[S\cup C]\) has at most \(k+1\) neighbors. This branch reduction is based on the following lemma.
Lemma 6 (Branch reduction 4). Given an instance \((D,S,C)\) and a vertex \(u\in C\). If \(\overline{d}_{S\cup C}(u)\le k\), and \(u\) has exactly one neighbor \(v\) in \(\overline{G}[S\cup C]\) satisfying \(\overline{d}_{S\cup C}(v)>k\), and \(v\) has exactly \(k+1\) neighbors in \(\overline{G}[S\cup C]\), then after moving \(u\) to \(D\), we can add \(v\) and all vertices in \(\overline{N}_{C}(v)\setminus\{u\}\) to \(S\) directly.
Proof. We prove it by contradiction. Let \(D'\) be a minimal \(k\)-BDD derived from the current instance that contains \(u\) and at least one vertex from \(\{v\}\cup \overline{N}_C(v)\setminus\{u\}\). Let \(S'=S\cup C\setminus D'\) be the \(k\)-biplex derived from deleting \(D'\). If \(v\in D'\), we have \(\overline{d}_{S'}(u)< k\) and every neighbor \(x\) of \(u\) in \(\overline{G}[S']\) satisfies \(\overline{d}_{S'}(x)< k\). Therefore, \(D'\setminus\{u\}\) is still a \(k\)-BDD and thus \(D'\) is not minimal. If there exists a vertex \(w\in \overline{N}_C(v)\setminus\{u\}\) and \(w\in D'\), then we have \(\overline{d}_{S'}(v)<k\), and every neighbor \(x\) of \(u\) in \(\overline{G}[S']\) except \(v\) satisfies \(\overline{d}_{S'}(x)<k\). Therefore, \(D'\setminus\{u\}\) is also a \(k\)-BDD and thus \(D'\) is not minimal. ◻
Improved branching strategy for \(\overline{\delta}_{S\cup C}=k+1\). Based on Lemma 6, we improve our deletion-based branching strategy for the case when \(\overline{\delta}_{S\cup C}=k+1\) and \(\max_{v\in S}\overline{d}_{S\cup C}(v)\le k\). In this case, the branching vertex \(u\) is selected from \(C\). We redesign the branching strategy when \(u\) is deleted from \(C\) to trigger Lemma 6 as early as possible. Specifically, let \(u\) be the vertex in \(\{v\in C\;\vert\;\overline{d}_{S\cup C}(v)=k+1\}\) with the minimum \(\overline{d}_C(\cdot)\). Let \(v_1,v_2,\dots,v_{\overline{d}_C(u)}\) be the vertices of \(\overline{N}_C(u)\) in non-increasing order of \(\overline{d}_{S\cup C}(\cdot)\). The subinstances are generated in the following way: for each \(i\) from \(1\) to \(\overline{d}_C(u)\), we generate a subinstance: \[(D\cup\{u,v_1,v_2\dots,v_{i-1}\}, S\cup\{v_i\}, C\setminus\{u,v_1,v_2\dots,v_i\})\] until (1) \(\overline{d}_{S\cup C\setminus\{v_1,v_2\dots,v_{i-1}\}}(u)\le k\), and (2) at most one vertex \(v\in \{v_i,v_{i+1},\dots,v_{\overline{d}_{C}(u)}\}\) satisfies \(\overline{d}_{S\cup C}(v)=k+1\). If \(v_i\) is the only vertex in this set satisfying \(\overline{d}_{S\cup C}(v_i)=k+1\), we generate one more subinstance according to Lemma 6: \[\begin{gather} (D\cup\{u,v_1,v_2\dots,v_{i-1}\}, S\cup\{v_i\}\cup (\overline{N}_C(v_i)\setminus\{u\}),\\ C\setminus\{u,v_1,v_2\dots,v_i\}\setminus \overline{N}_C(v_i)). \end{gather}\] Otherwise, we terminate generating any new branches directly. These early termination can be established as the remaining subgraph \(\overline{G}[S\cup C\setminus\{u,v_1,v_2,\dots,v_{i}\}]\) will not yield any minimal \(k\)-BDD according to Lemma 6.
Figure 2 illustrates the one-level branches generated by our improved branching strategy. The left dashed box shows the branches where \(u\) is moved to \(D\), which are generated by this strategy. In these branches, the vertices of \(\overline{N}_C(u)\) are considered in the given order, and each generated branch moves one vertex \(v_i\) to \(S\) while moving the preceding vertices \(v_1,\ldots,v_{i-1}\) to \(D\). Once Lemma 6 can be applied, i.e. \(\overline{d}_{S\cup C}(u)\le k\) and \(v_i\) is the last vertex in \(\overline{N}_C(u)\) satisfying \(\overline{d}_{S\cup C}(v_i)=k+1\), the remaining branches are pruned, and \(v_i\) as well as all vertices in \(\overline{N}_C(v_i)\setminus \{u\}\) are directly added to \(S\). The right dashed box shows the branches where \(u\) is added to \(S\), which are generated by our deletion-based branching strategy. Since \(\overline{d}_{S\cup C}(u)-k=1\), each such branch deletes exactly one vertex from \(\overline{N}_C(u)\).
3.3 Implementation details↩︎
Equipped with our deletion-based branching strategy and branch reduction techniques, we present the pseudocode of our deletion-based algorithm in Algorithm 3. It first initializes the best solution \(S^*\) as an empty graph and invokes with all vertices in the candidate set (lines 1-2). For each instance \((D,S,C)\), the procedure exhaustively applies Lemma 3, Lemma 4, and Lemma 5 to reduce the candidate set (line 4). If all vertices in \(S\cup C\) have at most \(k\) non-neighbors in \(S\cup C\), then \(G[S\cup C]\) is already a valid \(k\)-biplex. In this case, the algorithm only needs to check the size constraint and update \(S^*\) if more edges are obtained (lines 5-7). Otherwise, the algorithm selects a branching vertex \(u\) and sorts the vertices in \(\overline{N}_C(u)\) as \(v_1,v_2,\dots,v_q\) in decreasing order of their non-degrees (lines 8-14). If some vertex in \(S\) has non-degree larger than \(k\), such a vertex with the maximum non-degree is selected; otherwise, \(u\) is selected from \(C\) with the maximum \(\overline{d}_{S\cup C}(\cdot)\) and the minimum \(\overline{d}_C(\cdot)\). If \(u\in C\) and \(\overline{d}_{S\cup C}(u)=k+1\), the algorithm invokes to handle the branches where \(u\) is moved to \(D\) (lines 15-16). Specifically, scans the ordered vertices and lets \(P_i=\{v_1,\dots,v_{i-1}\}\) and \(D_i=\{u\}\cup P_i\) (lines 25-26). Before the stopping condition is met, it generates the subinstance that moves \(D_i\) to \(D\) and fixes \(v_i\) into \(S\) (line 32). Once the remaining non-neighbors of \(u\) satisfy the condition of Lemma 6, directly adds the corresponding vertices to \(S\) and stops generating further branches (lines 27-31). After the branches with \(u\) deleted are generated, the main procedure moves \(u\) to \(S\) (line 18) and applies the ordinary deletion-based branching rule (lines 19-23). Let \(r=\overline{d}_{S\cup C}(u)-k\). For each possible position \(i\) of the \(r\)-th deleted vertex in \(\overline{N}_C(u)\), the algorithm chooses the other \(r-1\) deleted vertices from \(\{v_1,\dots,v_{i-1}\}\), deletes them together with \(v_i\), and fixes the remaining prefix vertices into \(S\) (lines 19-23).
We next analyze the worst-case time complexity of Algorithm 3.
Theorem 3. Given a bipartite graph \(G\) and two positive integers \(k\) and \(\theta\), the worst-case time complexity of Algorithm 3 is \(O^*(\gamma_k^n)\), where \(n=\lvert U\rvert+\lvert V\rvert\) and \(\gamma_k<2\). In particular, \(\gamma_1=1.725\), \(\gamma_2=1.856\), and \(\gamma_3=1.928\).
Proof. Let \(T(n)\) denote the maximum number of leaf instances generated by Algorithm 3, where \(n=|C|\) is the number of candidate vertices. In each recursive call, the procedure takes at most \(O(m)\) time by maintaining degree values, selecting the branching vertex, and bucket-sorting the non-neighbors of the branching vertex. Therefore, the total running time of Algorithm 3 is \(O(m\cdot T(n))\).
We next analyze \(T(n)\) according to the branching strategy. Consider an instance after applying the reduction rules. Let \(u\) be the selected branching vertex. Let \(\overline{d}=\overline{d}_{S\cup C}(u)\), \(q=\overline{d}_C(u)\) and \(r=\overline{d}-k\). There are three possible cases to discuss.
Case 1: \(\overline{d}=k+1\) and \(u\in C\). Let \(p\) be the number of vertices in \(\overline{N}_C(u)\) whose non-degrees in \(S\cup C\) are \(k+1\). Since the vertices in \(\overline{N}_C(u)\) are sorted in decreasing order of their non-degrees, these vertices are \(v_1,\ldots,v_p\). In the \(i\)-th branch generated by , it moves \(D_i=\{u,v_1,\ldots,v_{i-1}\}\) to \(D\) and fixes \(v_i\) into \(S\), thereby removing \(i+1\) vertices from \(C\). If \(p\le 1\), at most one subinstance is generated in , which moves \(u\) to \(D\) and \(v_1\) to \(S\). At most \(k+1\) subinstances are generated by , each of which moves \(u\) to \(S\) and moves one vertex from \(\overline{N}_C(u)\) to \(D\). Therefore, the recurrence is given by \[T(n)\le T(n-2) + \sum_{i=1}^{k+1} T(n-i-1).\] If \(p\ge2\), then generates subinstances for \(i=1,\ldots,p-1\), and applies Lemma 6 at \(v_p\). Since \(u\) is chosen with the minimum \(\overline{d}_C(\cdot)\) among vertices of non-degree \(k+1\), we have \(\overline{d}_C(v_p)\ge \overline{d}_C(u)=q\). Moreover, all vertices in \(\overline{N}_C(u)\) are on the same side as \(v_p\), and hence the only vertex in \(D_p\) adjacent to \(v_p\) in \(\overline{G}\) is \(u\). Thus, the branch generated by Lemma 6 removes at least \(p+q\) vertices from \(C\). After finishes, the main procedure moves \(u\) to \(S\). Since \(\overline{d}=k+1\), the ordinary deletion-based branching rule further generates \(q\) branches, where the \(i\)-th branch removes \(i+1\) vertices from \(C\). Therefore, the recurrence is given by \[\begin{align} T(n)\le& \sum_{i=1}^{q}T(n-i-1) + \sum_{i=2}^{p}T(n-i) + T(n-p-q). \label{eq:kplusone-c} \end{align}\tag{1}\] Among all \(1\le p\le q\le k+1\), the largest branching factor of Eq. (1 ) is obtained when \(q=p=k+1\). Hence, this case is bounded by \[\begin{align} T(n)\le& 2\sum_{i=2}^{k+1}T(n-i) + T(n-k-2) + T(n-2k-2) \nonumber \\ \le& \sum_{i=1}^{k}T(n-i) + T(n-k-2) + T(n-2k-2) \label{eq:kplusone-c-bound} \end{align}\tag{2}\]
Case 2: \(\overline{d}=k+1\) and \(u\in S\). Since \(u\) is already contained in \(S\), the algorithm does not generate the branch that moves \(u\) to \(D\). The ordinary deletion-based branching rule only needs to delete one vertex from \(\overline{N}_C(u)\). Thus, the recurrence is given by \[T(n)\le \sum_{i=1}^{k+1}T(n-i). \label{eq:kplusone-s}\tag{3}\]
Note that Eq. (2 ) is dominated by Eq. (3 ). Let \(\eta_k\) be the largest real root of \(x^n=\sum_{i=1}^{k+1}x^{n-i}\). Then this case runs in \(O^*(\eta_k^n)\) time, where \(\eta_1=1.618\), \(\eta_2=1.839\), and \(\eta_3=1.928\).
Case 3: \(\overline{d}\ge k+2\). If \(u\in C\), the branch that moves \(u\) to \(D\) contributes \(T(n-1)\); if \(u\in S\), this branch is absent and the recurrence is dominated by the former case. In the branches where \(u\) is kept, the algorithm chooses the position \(i\) of the \(r\)-th deleted vertex in \(\overline{N}_C(u)\) and chooses the other \(r-1\) deleted vertices from \(\{v_1,\ldots,v_{i-1}\}\). Therefore, \[T(n)\le T(n-1)+\sum_{i=r}^{q} \binom{i-1}{r-1} T(n-i-1). \label{eq:bdd-rec}\tag{4}\] For \(\overline{d}\ge k+2\), the largest branching factor is obtained when \(r=2\) and \(q=k+2\). Thus, Eq. (4 ) is bounded by \[T(n)\le T(n-1)+\sum_{i=2}^{k+2}(i-1)T(n-i-1). \label{eq:large-degree-bound}\tag{5}\] Let \(\zeta_k\) be the largest real root of \(x^{k+3}=x^{k+2}+\sum_{j=1}^{k+1} jx^{k+1-j}\). Then this case runs in \(O^*(\zeta_k^n)\) time, where \(\zeta_1=1.725\), \(\zeta_2=1.856\), and \(\zeta_3=1.923\).
Combining the above cases, the running time is \(O^*(\gamma_k^n)\), where \(\gamma_k=\max\{\eta_k,\zeta_k\}\). Therefore, \(\gamma_1=1.725\), \(\gamma_2=1.856\), and \(\gamma_3=1.928\). This completes the proof. ◻
4 Optimization Techniques↩︎
In this section, we propose several optimization techniques to further enhance the practical performance of our deletion-based algorithm, including efficient upper-bounding techniques to prune unnecessary instances in linear time and a new heuristic algorithm to identify an initial near-maximum \(k\)-biplex in polynomial time.
4.1 Novel Upper-Bounding Techniques↩︎
In this subsection, we propose an efficient upper-bounding technique to prune instances that cannot produce a \(k\)-biplex with more edges than \(S^*\). Given an instance \((D,S,C)\), let \(S=(U_S,V_S)\) and \(C=(U_C,V_C)\). We first compute the degree-based vertex upper bounds for both sides as \(c_U=\min_{v\in V_S}(d_{S\cup C}(v)+k)\) and \(c_V=\min_{v\in U_S}(d_{S\cup C}(v)+k)\). If \(c_U<\theta\) or \(c_V<\theta\), the instance can be safely pruned.
Next, we derive an edge upper bound from the vertex newly added to \(S\). Suppose that a vertex \(u\) has just been moved from \(U_C\) to \(U_S\). The case that \(u\) is moved from \(V_C\) to \(V_S\) is symmetric. Since \(u\) has been added to \(U_S\), at most \(k-\overline{d}_S(u)\) vertices in \(\overline{N}_C(u)\) can be kept in any \(k\)-biplex derived from \((D,S,C)\). For a vertex \(v\in V_S\cup V_C\), let \(f(v)=\min\{d_{S\cup C}(v),c_U\}\). Clearly, \(f(v)\) provides an upper bound for \(v\)’s degree in any derived \(k\)-biplex, i.e., adding \(v\) to \(S\) will introduce at most \(f(v)\) edges to the final \(k\)-biplex. Therefore, an edge upper bound can be obtained by keeping all vertices in \(V_C\setminus\overline{N}_C(u)\) and only \(k-\overline{d}_S(u)\) vertices with the largest \(f(\cdot)\) values in \(\overline{N}_C(u)\), as stated in the following lemma.
Lemma 7 (Vertex-based upper bound). Given an instance \((D,S,C)\) and a vertex \(u\) that is newly added to \(S\), let \(v_1,v_2,\dots,v_{\overline{d}_{C}(u)}\) be the vertices of \(\overline{N}_C(u)\) in non-increasing order with respect to \(f(v)\). For any \(k\)-biplex \(S'\) derived from \((D,S,C)\), we have that: \[\label{eq:ub1} \lvert E_{S'}\rvert\le \sum_{v\in V_S\cup N_C(u)} f(v) + \sum_{i=1}^{k-\overline{d}_S(u)} f(v_i).\tag{6}\]
Proof. For each vertex \(v\) on the opposite side of \(u\), its contribution to \(\lvert E_{S'}\rvert\) is at most \(f(v)\). As \(u\) is added to \(S\), at most \(k-\overline{d}_S(u)\) non-neighbors of \(u\) can still be added to \(S\). Since \(f(v)\) is independent of how vertices are chosen from \(V_S\cup V_C\), vertices in \(V_S\cup N_C(u)\) contribute at most \(\sum_{v\in V_S\cup N_C(u)} f(v)\) edges to \(S'\), and vertices in \(\overline{N}_C(u)\) contribute at most \(\sum_{i=1}^{k-\overline{d}_S(u)} f(v_i)\) edges to \(S'\). ◻
![Figure 4: An example instance for upper-bounding techniques when k=2. The left part shows the bipartite graph, where dashed red lines denote the non-edges between the newly added vertex u_2 (red color) and \overline{N}_C(u_2). In the right matrix, \bullet denotes an edge in G[S\cup C] and \circ denotes a non-edge.](/article/2607.07419/_pdflatex/hyupwksx.png "fig:")
We notice that this upper bound may not be tight enough, as it only restricts \(u\)’s non-neighbors in \(C\) without considering \(u\)’s neighbors in \(C\). To address this, we further propose an edge upper bound from \(U_S\). The case for \(V_S\) is symmetric. Specifically, for a vertex \(v\in V_C\), adding \(v\) to \(S\) introduces \(\overline{d}_S(v)\) non-neighbors to vertices in \(U_S\). Since every vertex in \(U_S\) can have at most \(k\) non-neighbors, the total number of such introduced non-neighbors is at most \(\sum_{w\in U_S}(k-\overline{d}_S(w))\). Therefore, if all vertices in \(V_C\) introduce more non-neighbors than the above allowance, some vertices in \(V_C\) must be discarded.
Lemma 8 (Set-based upper bound).
Given an instance \((D,S,C)\), let \(x_1,x_2,\dots,x_{|V_C|}\) be the vertices of \(V_C\) in non-increasing order with respect to \(\overline{d}_S(x)\). Let \(p\) be the smallest integer satisfying \[\sum_{i=1}^{p}\overline{d}_S(x_i) \ge \sum_{v\in V_C}\overline{d}_S(v) - \sum_{w\in U_S}(k-\overline{d}_S(w)).\] Let \(y_1,y_2,\dots,y_{|V_C|}\) be the vertices of \(V_C\) in non-increasing order with respect to \(f(v)\). We can derive the following upper bound. For any \(k\)-biplex \(S'\) derived from \((D,S,C)\), we have that: \[\label{eq:ub2} \lvert E_{S'}\rvert \le \sum_{v\in V_S} f(v) + \sum_{i=1}^{\lvert V_C\rvert-p} f(y_i).\tag{7}\]
Proof. For any \(k\)-biplex \(S'\) derived from \((D,S,C)\), the total number of non-neighbors introduced by vertices selected from \(V_C\) cannot exceed \(\sum_{w\in U_S}(k-\overline{d}_S(w))\). According to the definition of \(p\), at least \(p\) vertices in \(V_C\) cannot be selected. Therefore, at most \(|V_C|-p\) vertices from \(V_C\) can be contained in \(S'\). For each vertex \(v\in V_S\cup V_C\), its contribution to \(\lvert E_{S'}\rvert\) is at most \(f(v)\). Thus, vertices in \(V_S\) contribute at most \(\sum_{v\in V_S} f(v)\) edges to \(S'\), and vertices in \(V_C\) contribute at most \(\sum_{i=1}^{\lvert V_C\rvert-p} f(y_i)\) edges to \(S'\). ◻
Example 1. Consider the instance shown in Fig. 4, where \(k=2\), \(S=(U_S,V_S)\) with \(U_S=\{u_1,u_2\}\) and \(V_S=\{v_1,v_2\}\), and \(C=(U_C,V_C)\) with \(U_C=\{u_3,u_4,u_5\}\) and \(V_C=\{v_3,v_4,v_5,v_6,v_7\}\). Assume that \(u_2\) has just been moved from \(U_C\) to \(U_S\). We have \(c_U=5\) and \(c_V=5\), and the corresponding \(f(\cdot)\) values of vertices in \(V_S\cup V_C\) are shown in the last row of Fig. 4. For the vertex-based upper bound, \(\overline{d}_S(u_2)=0\) and \(\overline{N}_C(u_2)=\{v_5,v_6,v_7\}\). Thus, any \(2\)-biplex containing \(u_2\) can keep at most two vertices from \(\overline{N}_C(u_2)\). By Lemma 7, we have \[e_1=(f(v_1)+f(v_2)+f(v_3)+f(v_4))+(f(v_5)+f(v_6))=22.\] For the set-based upper bound, the vertices \(v_3,v_4,v_5,v_6,v_7\) introduce \(0,0,1,2,2\) non-neighbors to \(U_S\), respectively. The remaining number of non-neighbors allowed by \(U_S\) is \((2-\overline{d}_S(u_1))+(2-\overline{d}_S(u_2))=0+2=2\). Hence, at least two vertices in \(V_C\) cannot be selected. Keeping the three vertices in \(V_C\) with the largest \(f(\cdot)\) values gives \[e_2=f(v_1)+f(v_2)+f(v_3)+f(v_4)+f(v_5)=19.\] Therefore, Algorithm ¿fig:alg:ub? returns \(\min\{c_U\cdot c_V,e_1,e_2\}=19\). If the current best solution already contains at least \(19\) edges, this instance can be safely pruned.
Implementation details 1. Algorithm ¿fig:alg:ub? first computes the vertex upper bounds \(c_U\) and \(c_V\) (lines 1-2). If either of them is smaller than \(\theta\), the current instance can be pruned (line 3). Then, it computes the degree upper bound \(f(\cdot)\) for each vertex (lines 4-5). After that, Algorithm ¿fig:alg:ub? computes two edge upper bounds. It first computes the vertex-based upper bound according to Lemma 7. Specifically, it keeps all vertices in \(V_S\cup N_C(u)\) (line 7), and selects at most \(\min\{k-\overline{d}_S(u),\overline{d}_C(u)\}\) vertices with the largest \(f(\cdot)\) values from \(\overline{N}_C(u)\) (lines 8-9). Then it computes two set-based upper bounds, which are derived from calling twice, once for each side (line 10). In each call, it first computes the excess number of non-neighbors of vertices in \(U_S\) caused by adding all vertices from \(V_C\) (lines 14-15). Then it removes vertices from \(V_C\) with the largest \(\overline{d}_S(\cdot)\) values until the excess is covered (lines 16-19). Finally, it keeps the remaining number of vertices in \(V_C\) with the largest \(f(\cdot)\) and all vertices in \(V_S\) to obtain the set-based upper bound (lines 20-22).
Lemma 9. Given an instance \((D,S,C)\) and a vertex \(u\) that is newly added to \(S\), Algorithm ¿fig:alg:ub? runs in \(O(|S|+|C|)\) time.
Proof. In Algorithm ¿fig:alg:ub?, the values \(c_U\), \(c_V\), and \(f(\cdot)\) can be computed by traversing vertices in \(S\cup C\), which takes \(O(|S|+|C|)\) time. In computing \(e_1\), the vertices in \(\overline{N}_C(u)\) are sorted by bucket sort, and the remaining operations are linear traversals. Thus, it takes \(O(|S|+|C|)\) time. In , the values \(r\) and \(e\) are computed by linear traversals. The two orderings can be obtained by bucket sort, since both \(\overline{d}_S(\cdot)\) and \(f(\cdot)\) are integers bounded by \(|S|+|C|\). The value of \(p\) is also computed in at most \(\lvert V_C\rvert\) times. Thus, takes \(O(|S|+|C|)\) time. Based on the above analysis, the total time complexity of Algorithm ¿fig:alg:ub? is \(O(|S|+|C|)\). ◻
4.2 A New Heuristic Algorithm↩︎
We propose a heuristic algorithm to efficiently identify an initial large \(k\)-biplex, which provides a tight lower bound on the edge size of the maximum \(k\)-biplex and helps prune the non-maximum instances. The pseudocode of this algorithm is shown in Algorithm ¿fig:alg:heu?. Specifically, the algorithm consists of two stages. The first stage (lines 1-6) aims to extract a valid \(k\)-biplex by a greedy deletion strategy. Starting with the entire graph \(G\), the algorithm iteratively removes the vertex with the minimum degree. To prevent the resulting structure from becoming heavily skewed, this deletion is strictly restricted to the partition currently containing more vertices (lines 3-4). The process terminates when the remaining subgraph \(G[S^*]\) forms a valid \(k\)-biplex (line 2). If \(G[S^*]\) violates the size threshold \(\theta\), \(S^*\) is set to empty (line 6).
However, this greedy strategy may prematurely delete useful vertices and thereby miss a large \(k\)-biplex in practice. To address this problem, we propose the second stage (lines 7-15) to systematically explore localized subgraphs. Specifically, the algorithm first sorts vertices of \(U\) as \(u_1,u_2,\dots,u_{|U|}\) in ascending degree order (line 7). For each vertex \(u_i\in U\), the algorithm greedily constructs a valid \(k\)-biplex that contains \(u_i\) while excluding \(u_1,u_2,\dots,u_{i-1}\). We first present the following lemma to constrain the distance between two vertices of a \(k\)-biplex.
Lemma 10. [12] The distance between any two vertices of a \(k\)-biplex \(S=(U_S,V_S)\) is at most \(3\) if \(|U_S|\ge 2k+1\) and \(|V_S|\ge 2k+1\).
Let \(N^2(u_i)=\{w\in N(v)\mid v\in N(u_i)\}\) and \(N^3(u_i)=\{x \in N(w)\mid w\in N^2(u_i)\}\) denote the set of \(u_i\)’s 2-hop and 3-hop neighbors, respectively. Let \(N^{2+}(u_i)=N^2(u_i)\cap\{u_{i+1},u_{i+2},\dots,u_{|U|}\}\). According to Lemma 10, any \(k\)-biplex whose first vertex in the above ordering is \(u_i\) must be contained in \(\{u_i\}\cup N^{2+}(u_i)\cup N(u_i)\cup N^3(u_i)\). Therefore, the algorithm initializes \(S\) as \((\{u_i\},\emptyset)\) and \(C\) as the vertices within distance at most \(3\) from \(u_i\) after removing lower-order vertices (line 9). Then, the algorithm repeatedly reduces \(C\); if \(C\) becomes empty, the current expansion is terminated. Otherwise, the vertex in \(C\) with the largest degree in \(G[S\cup C]\) is selected, moved to \(S\) only when the resulting subgraph remains a \(k\)-biplex, and then discarded from \(C\) (lines 10-14). Finally, the algorithm updates \(S^*\) if the obtained \(G[S]\) has more edges than \(G[S^*]\) (line 15).
Theorem 4. Given a bipartite graph \(G\) and two integers \(\theta\) and \(k\), Algorithm ¿fig:alg:heu? runs in \(O(mn)\) time.
Proof. In Algorithm ¿fig:alg:heu?, the first stage (lines 2-5) can be implemented using a peeling method adapted from the core decomposition [26], which takes \(O(m)\) time. In the second stage, bucket-sorting vertices of \(U\) by degree takes \(O(n)\) time (line 7). For each vertex \(u_i\), initializing \(S\) and \(C\) (line 9) takes \(O(n\delta)=O(m)\) time. During the greedy expansion (lines 10-14), the algorithm maintains the degree value \(d_{S\cup C}(\cdot)\) for vertices in \(C\). When a vertex is removed from \(C\), updating the degree value takes \(O(\delta)\) time. By using a peeling method similar to the first stage, selecting a vertex with the largest \(d_{S\cup C}(\cdot)\) takes only \(O(1)\) time (line 12). Therefore, the greedy expansion loop takes totally \(O(n\delta)=O(m)\) time. As \(|U|\le n\), the total time of the second stage is \(O(nm)\). Consequently, the total running time of Algorithm ¿fig:alg:heu? is \(O(m+mn)=O(mn)\). ◻
| Dataset | \(\lvert U\rvert\) | \(\lvert V\rvert\) | \(\lvert E\rvert\) | \(\delta\) |
|---|---|---|---|---|
| Youtube | 94,238 | 30,087 | 293,360 | (1,035, 7,591) |
| LKML | 42,045 | 337,509 | 599,858 | (31,719, 6,627) |
| Mummun | 175,214 | 530,418 | 1,890,661 | (968, 19,805) |
| Citeu | 153,277 | 731,769 | 2,338,554 | (189,292, 1,264) |
| IMDB | 303,617 | 896,302 | 3,782,463 | (1,334, 1,590) |
| Amazon | 2,146,057 | 1,230,915 | 5,743,258 | (12,180, 3,096) |
| Aol | 4,811,647 | 1,632,788 | 10,741,953 | (100,629, 84,530) |
| 5,998,790 | 4,443,631 | 20,592,962 | (423, 95,165) |
5 Experiments↩︎
| Dataset | \(k\) | \(\theta\) | \(\lvert E^*\rvert\) | DMBP | \(k\) | \(\theta\) | \(\lvert E^*\rvert\) | DMBP | \(k\) | \(\theta\) | \(\lvert E^*\rvert\) | DMBP | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Youtube | 1 | 3 | 945 | 35 | 1,232 | 5,510 | 2 | 7 | 280 | 5,500 | - | - | 3 | 10 | 345 | 9,452 | - | - |
| 6 | 302 | 7.66 | 186 | 162 | 10 | 275 | 186 | 16,675 | 6,951 | 13 | 345 | 347 | - | - | ||||
| 4 | 9 | 375 | 1,611 | - | - | 5 | 12 | 429 | 19,306 | - | - | 6 | 17 | 493 | 63,085 | - | - | |
| 16 | 381 | 2,553 | - | - | 19 | 429 | 4,802 | - | - | 20 | 493 | 14,091 | - | - | ||||
| LKML | 1 | 3 | 462 | 717 | 6,515 | 3,739 | 2 | 7 | 94 | 604 | - | - | 3 | 9 | 112 | 6,472 | - | - |
| 6 | 85 | 11 | 409 | 144 | 9 | 85 | 2.77 | 16,231 | 15,665 | 11 | 107 | 1.07 | - | - | ||||
| 4 | 11 | 129 | 5,713 | - | - | 5 | 13 | 147 | 1,434 | - | - | 6 | 15 | 161 | 58 | - | - | |
| 12 | 129 | 47 | - | - | 14 | 146 | 1.70 | - | - | 16 | 0 | 0.15 | - | - | ||||
| Mummun | 1 | 3 | 8,805 | 6,638 | - | - | 2 | 12 | 510 | 1,889 | 9,124 | 20,947 | 3 | 14 | 568 | 1,146 | - | - |
| 6 | 1,783 | 2,907 | 18,273 | 11,284 | 15 | 510 | 2.49 | 244 | 46 | 18 | 551 | 0.18 | 662 | 81 | ||||
| 4 | 16 | 610 | 611 | - | - | 5 | 18 | 670 | 214 | - | - | 6 | 19 | 717 | 1,761 | - | - | |
| 19 | 580 | 0.33 | - | 9,257 | 20 | 670 | 0.30 | - | - | 20 | 684 | 0.39 | - | - | ||||
| Citeu | 1 | 3 | 12,429 | 92 | 24,568 | 175 | 2 | 11 | 2,600 | 1,774 | - | - | 3 | 14 | 2,600 | 4,670 | - | - |
| 6 | 4,970 | 1,898 | 23,042 | 28,228 | 14 | 2,600 | 2.71 | - | - | 17 | 2,600 | 2.13 | - | - | ||||
| 4 | 16 | 2,600 | 36 | - | - | 5 | 17 | 2,600 | 65 | - | - | 6 | 18 | 2,600 | 471 | - | - | |
| 20 | 2,600 | 0.82 | - | - | 20 | 2,600 | 2.34 | - | - | 20 | 2,600 | 5.17 | - | - | ||||
| IMDB | 1 | 3 | 564 | 28 | 1,164 | 528 | 2 | 5 | 554 | 1,943 | - | - | 3 | 8 | 554 | 278 | - | - |
| 6 | 529 | 5.15 | 16 | 4.39 | 8 | 516 | 17 | 1,635 | 618 | 11 | 554 | 144 | 52,220 | 18,534 | ||||
| 4 | 9 | 593 | 5,723 | - | - | 5 | 16 | 648 | 4,100 | - | - | 6 | 15 | 719 | 80,574 | - | - | |
| 12 | 593 | 3,967 | - | - | 19 | 648 | 2,594 | - | - | 19 | 719 | 7,645 | - | - | ||||
| Amazon | 1 | 3 | 433 | 272 | 5,150 | 2,277 | 2 | 5 | 461 | 248 | - | - | 3 | 7 | 500 | 1,508 | - | - |
| 6 | 433 | 13 | 565 | 437 | 8 | 461 | 11 | - | - | 10 | 500 | 12 | - | - | ||||
| 4 | 11 | 527 | 26 | - | - | 5 | 12 | 553 | 680 | - | - | 6 | 18 | 324 | 7,752 | - | - | |
| 14 | 325 | 2,937 | - | - | 17 | 299 | 337 | - | - | 19 | 324 | 64 | - | - | ||||
| Aol | 1 | 4 | 856 | 9,516 | - | - | 2 | 8 | 250 | 5,095 | - | - | 3 | 11 | 229 | 9,230 | - | - |
| 8 | 209 | 21 | - | 72,501 | 11 | 194 | 88 | - | - | 14 | 219 | 87 | - | - | ||||
| 4 | 15 | 256 | 1,779 | - | - | 5 | 17 | 281 | 2,195 | - | - | 6 | 18 | 329 | 39,285 | - | - | |
| 17 | 249 | 6.14 | - | - | 18 | 280 | 31 | - | - | 19 | 320 | 949 | - | - | ||||
| 1 | 6 | 204 | 2,346 | 80,534 | 18,103 | 2 | 9 | 193 | 6,112 | - | - | 3 | 13 | 209 | 825 | - | - | |
| 9 | 148 | 25 | 118 | 97 | 12 | 178 | 13 | 961 | 618 | 15 | 0 | 5.66 | 4,426 | - | ||||
| 4 | 15 | 233 | 617 | - | - | 5 | 17 | 237 | 126 | - | - | 6 | 18 | 258 | 3,730 | - | - | |
| 17 | 0 | 2.16 | 54,390 | 30,586 | 18 | 0 | 5.39 | - | - | 20 | 0 | 1.88 | - | - |
4pt
5.1 Experimental Setup↩︎
Datasets. We use 8 real-world bipartite graphs from diverse categories to evaluate the efficiency of our algorithm. These graphs have been widely used as benchmark datasets for bipartite cohesive subgraph search problems [2], [12], [15], [22]. The detailed information of these graphs is shown in Table 2, where \(\delta\) represents the maximum degree of vertices on each side. All these datasets are publicly available at http://konect.cc/networks.
Algorithms. We implement our proposed deletion-based algorithm in Algorithm 3, denoted by DMBP, which is equipped with all optimization techniques described in Sec. 4.1. We also implement two state-of-the-art maximum \(k\)-biplex search algorithms for comparative analysis, namely and . Specifically, is a branch-and-bound algorithm that adopts the symmetric-BK
branching strategy, which achieves a non-trivial worst-case time complexity [2]. is a core-based algorithm that combines the symmetric-BK branching strategy with a
core-based pruning method [22]. All algorithms are implemented in C++ and executed on a PC equipped with a 2.2GHz CPU and
128GB RAM running Linux.
Parameter settings. During the evaluations of all algorithms, we vary \(k\) from \(1\) to \(6\). Following the size constraint in Sec. 2, we choose \(\theta\) from the range \([2k+1,20]\) for each \(k\). We report the CPU time in seconds, excluding the time for reading graphs from external storage. Any runtime longer than \(24\) hours is regarded as a timeout and denoted by “-” in experimental results.
5.2 Experimental Results↩︎
Exp-1: Efficiency comparison among different algorithms. We evaluate the efficiency of DMBP and two baseline algorithms, and , on 8 real-world graphs. The results are shown in Table 3, where the column \(\lvert E^*\rvert\) represents the number of edges in the maximum \(k\)-biplex, and the notion “-” represents a timeout exceeding 24 hours. A value \(|E^*|=0\) means that no \(k\)-biplex satisfying the size threshold exists for this parameter setting. As observed, DMBP consistently outperforms the baseline algorithms across most input parameters. Specifically, DMBP solves all 96 test cases, while and solve only 23 and 22 test cases, respectively. The advantage becomes more evident when \(k\) is large: among the 64 test cases with \(k\ge3\), and solve only 4 and 2 test cases, respectively. For example, on LKML with \(k=2\) and \(\theta=9\), DMBP completes in \(2.77\)s, while and take \(16,231\)s and \(15,665\)s, respectively, achieving at least \(5000\times\) speedups. On Mummun with \(k=4\) and \(\theta=19\), DMBP completes in \(0.33\)s, while takes \(9,257\)s and times out, achieving at least \(28000\times\) speedups. Notably, DMBP solves all test cases on Aol with varying \(k\) from \(1\) to \(6\). In contrast, the two baseline algorithms fail to solve any test cases on this graph when \(k\ge 2\), and barely managed to finish when \(k=1\) and \(\theta=8\) in 21 hours. These results demonstrate the high efficiency of our proposed algorithm, especially with large \(k\) values.
Exp-2: Efficiency with varying \(\theta\) and \(k\). We evaluate the performance of and the two baseline algorithms and by varying \(\theta\) and \(k\) on two representative datasets, IMDB and Google. Similar results can be obtained on other datasets. The results are shown in Fig. 5, where the notion “INF” represents a timeout. As observed, DMBP consistently outperforms the baselines under different parameter settings, achieving speedups up to \(100\times\). For example, on the graph IMDB with \(k=4\) and \(\theta=16\) shown in Fig. 5 (c), our algorithm takes only \(80\) seconds, while takes over \(1000\) seconds and cannot finish in 24 hours. When \(\theta\) decreases or \(k\) increases, the search space becomes larger and all algorithms require more time. However, the runtime curve of DMBP grows much more slowly than those of the baselines, while and frequently reach the timeout on hard \(k\) or \(\theta\) settings. These results indicate that DMBP is less sensitive to input parameters, benefiting from the deletion-based branching strategy in Sec. 3.1 and the proposed upper-bounding techniques in Sec. 4.1.
Exp-3: Efficiency of upper bounding techniques. We evaluate the effectiveness of the proposed upper-bounding techniques by comparing DMBP with DMBP-U, which removes the upper bounds proposed in Sec. 4.1 from our deletion-based algorithm. The results are shown in Fig. 6. As observed, incorporating the upper-bounding techniques significantly improves the efficiency of DMBP. The improvement becomes more pronounced as \(k\) increases or \(\theta\) decreases, since these settings generate more partial solutions and make upper-bound pruning more important. In particular, DMBP-U can be up to two orders of magnitude slower than DMBP and may even time out on hard settings, while DMBP still finishes all the test cases efficiently. For example, on the graph Google with \(k=4\) and \(\theta=16\), DMBP takes about 80 seconds while DMBP-U takes more than 22 hours. These results demonstrate the strong pruning power of the proposed upper bounds.
Exp-4: Efficiency of the heuristic algorithm. We evaluate the effectiveness of the heuristic algorithm by comparing DMBP with DMBP-H, which starts from an empty initial solution instead of the solution returned by Algorithm ¿fig:alg:heu?. The results are shown in Fig. 7. As observed, DMBP consistently outperforms DMBP-H. This is because the heuristic algorithm provides a large \(k\)-biplex at the beginning, which tightens the pruning condition provided by the upper-bounding techniques in Sec. 4.1. The improvement of our heuristic algorithm is quite stable when varying the value of \(\theta\), but becomes more significant on difficult settings with a larger \(k\), where the total number of branches grows exponentially and a strong initial solution helps prune many redundant branches. These results show that the heuristic algorithm can substantially reduce the search cost by providing a strong initial solution.
Exp-5: Solution quality of the heuristic algorithm. We further verify the effectiveness of our heuristic algorithm by comparing the initial solution returned by the heuristic algorithm with the exact maximum \(k\)-biplex obtained by DMBP. The results are reported in Table 4, where \(\lvert E_H\rvert\) and \(\lvert E^*\rvert\) denote the numbers of edges in the heuristic solution and the maximum \(k\)-biplex, respectively. Table 4 shows that the heuristic algorithm obtains solutions close to the optimum on all tested cases. The edge ratio \(\lvert E_H\rvert/\lvert E^*\rvert\) ranges from \(85.2\%\) to \(98.1\%\), with an average value of \(92.9\%\). For example, on IMDB with \(k=4\) and \(\theta=20\), the heuristic algorithm returns a solution with 563 edges, while the optimal solution contains 574 edges. When comparing the running time, the heuristic algorithm is always significantly faster than DMBP. For example, the heuristic algorithm takes only \(0.51\) seconds on IMDB with \(k=4\) and \(\theta=20\), whereas the exact search takes \(190\) seconds. These results confirm that the heuristic algorithm can efficiently provide high-quality initial solutions for DMBP.
| Dataset | \(k\) | \(\theta\) | \(\lvert E_H\rvert\) | \(\lvert E^*\rvert\) | time | time |
|---|---|---|---|---|---|---|
| IMDB | 2 | 13 | 483 | 516 | 0.64 | 4.15 |
| 3 | 17 | 501 | 522 | 0.39 | 56 | |
| 4 | 20 | 563 | 574 | 0.51 | 190 | |
| 2 | 10 | 156 | 183 | 10 | 365 | |
| 3 | 13 | 198 | 209 | 6.53 | 825 | |
| 4 | 15 | 209 | 233 | 4.98 | 617 |
Exp-6: Scalability testing. We evaluate the scalability of algorithms on the Google dataset using random sampling of vertices and edges. Results on the other datasets show similar trends. We prepare sampled subgraphs by sampling 20%, 40%, 60%, and 80% vertices or edges from the original graph. The results are shown in Fig. 8. As observed, DMBP shows the slowest runtime growth as the graph size increases, while the baseline algorithms exhibit much steeper growth. On the 60% vertex-sampled graph with \(k=5\) and \(\theta=16\), DMBP completes in \(20\) seconds, whereas takes more than one hour and times out. These results indicate that the proposed deletion-based framework achieves the best scalability among the tested algorithms.
Exp-7: Memory usage testing. We evaluate the physical memory usage of DMBP, , and on 5 representative datasets. Similar results can be obtained on other graphs. The results are shown in Fig. 9. As observed, the memory usage of all algorithms grows almost linearly with the graph size. DMBP consumes memory comparable to , and both of them require less memory than . This is because the core-based algorithm relies on maintaining a large number of cores to reduce the graph size, which introduces additional memory overhead. These results indicate that DMBP is space efficient on real-world graphs.
6 Related Works↩︎
Closely related to our work is the maximal \(k\)-biplex enumeration problem, which aims to find all \(k\)-biplexes not contained in any larger ones. This problem has attracted increasing attention in recent years [12], [18]–[20], [27]. Sim et al. [27] first defined the \(k\)-biplex as a type of quasi-biclique and proposed a basic branch-and-bound algorithm MQBminer to enumerate all maximal \(k\)-biplexes satisfying a vertex size constraint. Although it uses degree-based and common-neighbor-based pruning methods, MQBminer still generates many redundant branches. To address this, Yu et al. [20] proposed iMB, a prefix-based algorithm equipped with early stopping strategies to reduce redundant non-maximal branches. However, its performance degrades on graphs with millions of edges when \(k > 2\). Yu et al. [20] also introduced iTraversal, a polynomial-delay algorithm based on a reverse search framework. While it guarantees polynomial time between outputs, it requires storing all maximal \(k\)-biplexes in memory, making it unsuitable for large-scale graphs. Alternatively, Dai et al. [12] proposed a pivot-based algorithm that uses pivoting techniques to avoid numerous non-maximal branches. However, it still suffers from a trivial worst-case time complexity of \(O^*(2^n)\). To overcome this, Dai et al. [19] later developed two algorithms combining pivoting techniques with a binary branching strategy. These two algorithms achieve non-trivial time complexities and currently offer the best practical performance when \(k\le 6\). These algorithms can be adapted to maximum \(k\)-biplex search by enumerating all maximal \(k\)-biplexes and returning the one with the most edges. However, since the number of maximal \(k\)-biplexes can be exponential in the graph size, this approach may enumerate many maximal but non-maximum \(k\)-biplexes, causing substantial unnecessary computation in practice.
The maximum \(k\)-plex search problem aims to find a \(k\)-plex with the most vertices in traditional graphs, where the \(k\)-plex model was originally introduced in [28]. This domain encompasses various formulations, among which the maximum \(k\)-plex search problem is the closest to our work and has been proven to be NP-hard [29]. Many approaches have been proposed to address this challenge. On the one hand, some approaches focus on carefully designed branching rules to surpass the trivial \(O^*(2^n)\) barrier, including strategies that prioritize vertices based on non-neighbor counts to strictly limit worst-case complexity [30], [31]. Notably, Wang et al. [32] developed a fixed-parameter tractable algorithm by exploiting the dual problem of the maximum \(k\)-plex search and derived a worst-case time complexity of \(O^*((k+1)^g)\), where \(g\) represents the gap between the degeneracy and the size of maximum \(k\)-plex. On the other hand, some approaches target scalability on large-scale graphs by using graph reductions based on degree and common-neighbor constraints [33]–[35], as well as new upper bounds derived from vertex coloring and vertex partitioning [35]–[38], to prune unnecessary branches. Notably, Ahmad et al. [39] synthesized these state-of-the-art techniques into a comprehensive framework to identify optimal configurations for general scenarios. However, these approaches are designed to maximize the number of vertices in traditional graphs, which is quite different from our problem of maximizing the number of edges in bipartite graphs, so these methods cannot be directly applied to the maximum \(k\)-biplex search problem.
7 Conclusion↩︎
In this paper, we investigate the maximum \(k\)-biplex search problem in bipartite graphs. We propose a novel deletion-based algorithm that reformulates the problem as finding a minimal \(k\)-bounded degree deletion in the complement graph. Based on this formulation, DMBP employs a new deletion-based branching strategy and branch reduction rules, achieving a worst-case time complexity below \(O^*(2^n)\). In addition, we develop several optimization techniques to further improve practical efficiency, including effective upper bounds and a heuristic algorithm. Extensive experiments on 8 real-world bipartite graphs demonstrate the efficiency and scalability of our deletion-based algorithm and the proposed optimization techniques.