Quantcast

Parameterized algorithms for Edge Biclique and related problems☆

Research paper by QilongFeng, ShaohuaLi, ZeyangZhou, JianxinWang

Indexed on: 14 Nov '17Published on: 01 Sep '17Published in: Theoretical Computer Science



Abstract

Maximum Edge Biclique and related problems have wide applications in management science, bioinformatics, etc. In this paper, we study parameterized algorithms for Parameterized Edge Biclique problem, Parameterized Edge Biclique Packing problem, Parameterized Biclique Edge Deletion problem, and Parameterized Bipartite Biclique Clustering problem. For the Parameterized Edge Biclique problem, the current best result is of running time ⁎O⁎(2k)<math class="math"><msup is="true"><mrow is="true"><mi is="true">O</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math>, and we give a parameterized algorithm of running time O(nk2.5k⌈k⌉)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">2.5</mn></mrow></msup><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mo stretchy="false" is="true">⌈</mo><msqrt is="true"><mi is="true">k</mi></msqrt><mo stretchy="false" is="true">⌉</mo></mrow></msup><mo stretchy="false" is="true">)</mo></math>, where k is the parameter and n is the number of vertices in the given graph. For the Parameterized Edge Biclique Packing problem, based on randomized divide-and-conquer technique, a parameterized algorithm of running time ⁎O⁎(k⌈k⌉logk4(2k−1)t))<math class="math"><msup is="true"><mrow is="true"><mi is="true">O</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mo stretchy="false" is="true">⌈</mo><msqrt is="true"><mi is="true">k</mi></msqrt><mo stretchy="false" is="true">⌉</mo><mi is="true">l</mi><mi is="true">o</mi><mi is="true">g</mi><mi is="true">k</mi></mrow></msup><msup is="true"><mrow is="true"><mn is="true">4</mn></mrow><mrow is="true"><mo stretchy="false" is="true">(</mo><mn is="true">2</mn><mi is="true">k</mi><mo is="true">−</mo><mn is="true">1</mn><mo stretchy="false" is="true">)</mo><mi is="true">t</mi><mo stretchy="false" is="true">)</mo></mrow></msup><mo stretchy="false" is="true">)</mo></math> is given, where k is the parameter and t is the number of bicliques in the solution. We study the Parameterized Biclique Edge Deletion problem on bipartite graphs and general graphs, and give parameterized algorithms of running time ⁎O⁎(2k)<math class="math"><msup is="true"><mrow is="true"><mi is="true">O</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">2</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math> and ⁎O⁎(3k)<math class="math"><msup is="true"><mrow is="true"><mi is="true">O</mi></mrow><mrow is="true"><mo is="true">⁎</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">3</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math>, respectively. For the Parameterized Bipartite Biclique Clustering problem, based on modular decomposition method, a kernel of size O(k2)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math> and a parameterized algorithm of running time O(2.42k(n+m))<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">2.42</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo is="true">+</mo><mi is="true">m</mi><mo stretchy="false" is="true">)</mo><mo stretchy="false" is="true">)</mo></math> are presented, where k is the parameter, n is the number of vertices, and m is the number of edges in the given graph.