## Abstract

In the Maximum Balanced Biclique Problem (MBB), we are given an n-vertex graph G= (V, E), and the goal is to find a balanced complete bipartite subgraph with q vertices on each side while maximizing q. The MBB problem is among the first known NP-hard problems, and has recently been shown to be NP-hard to approximate within a factor n^{1} ^{-} ^{o} ^{(} ^{1} ^{)}, assuming the Small Set Expansion hypothesis [Manurangsi, ICALP 2017]. An O(n/ log n) approximation follows from a simple brute-force enumeration argument. In this paper, we provide the first approximation guarantees beyond brute-force: (1) an O(n/ log ^{2}n) efficient approximation algorithm, and (2) a parameterized approximation that returns, for any r∈ N, an r-approximation algorithm in time exp(O(nrlogr)). To obtain these results, we translate the subgraph removal arguments of [Feige, SIDMA 2004] from the context of finding a clique into one of finding a balanced biclique. The key to our proof is the use of matching edges to guide the search for a balanced biclique.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers |

Editors | Isolde Adler, Haiko Müller |

Pages | 238-247 |

Number of pages | 10 |

DOIs | |

Publication status | Published - 2020 |

MoE publication type | A4 Article in a conference publication |

Event | International Workshop on Graph-Theoretic Concepts in Computer Science - Leeds, United Kingdom Duration: 24 Jun 2020 → 26 Jun 2020 Conference number: 46 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Springer |

Volume | 12301 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | International Workshop on Graph-Theoretic Concepts in Computer Science |
---|---|

Abbreviated title | WG |

Country/Territory | United Kingdom |

City | Leeds |

Period | 24/06/2020 → 26/06/2020 |