The Maximum k-Balanced Weighted Biclique problem looks for a biclique in the given vertex-weighted bipartite graph such that the weight of the biclique is maximized, and the gap between the weights of the two independent vertex sets of the biclique is at most the given value k. Within the paper, we propose an exact algorithm for the problem with a new perspective: feedback vertex set. Specifically, our approach begins by conducting branch operations on the vertices with large degree and the ones in the feedback vertex set of the considered bipartite graph G, then calls a polynomial-time algorithm proposed for a related problem to each resulting graph that is acyclic. Our algorithm is shown to have time complexity \(O(\min \{1.325^n, 2^{2\delta (G)}\} n^4 W^4_{max})\) , where n and \(W_{max}\) are the number and maximum weight of the vertices in G, respectively, and \(\delta (G)\) is the minimum cardinality (i.e., number of vertices) of a feedback vertex set for G. Furthermore, our algorithm can be adapted to solve the Maximum Balanced Biclique problem (i.e., \(k=0\) and G is unweighted) with time complexity \(O(\min \{1.325^n, 2^{2\delta (G)}\} n^2\log ^6 n)\) , which is better than the best-known time complexity \(O(1.3803^n n^2)\) , especially if G satisfies \(\delta (G) \le n/5\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Exact Algorithms for the Maximum k-Balanced Weighted Biclique Problem

  • Jingyi Liu,
  • Jianxin Wang,
  • Qilong Feng,
  • Feng Shi

摘要

The Maximum k-Balanced Weighted Biclique problem looks for a biclique in the given vertex-weighted bipartite graph such that the weight of the biclique is maximized, and the gap between the weights of the two independent vertex sets of the biclique is at most the given value k. Within the paper, we propose an exact algorithm for the problem with a new perspective: feedback vertex set. Specifically, our approach begins by conducting branch operations on the vertices with large degree and the ones in the feedback vertex set of the considered bipartite graph G, then calls a polynomial-time algorithm proposed for a related problem to each resulting graph that is acyclic. Our algorithm is shown to have time complexity \(O(\min \{1.325^n, 2^{2\delta (G)}\} n^4 W^4_{max})\) , where n and \(W_{max}\) are the number and maximum weight of the vertices in G, respectively, and \(\delta (G)\) is the minimum cardinality (i.e., number of vertices) of a feedback vertex set for G. Furthermore, our algorithm can be adapted to solve the Maximum Balanced Biclique problem (i.e., \(k=0\) and G is unweighted) with time complexity \(O(\min \{1.325^n, 2^{2\delta (G)}\} n^2\log ^6 n)\) , which is better than the best-known time complexity \(O(1.3803^n n^2)\) , especially if G satisfies \(\delta (G) \le n/5\) .