On Finding Balanced Bicliques via Matchings

Parinya Chalermsook, Wanchote Po Jiamjitrak, Ly Orgo*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

187 Downloads (Pure)


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 n1 - 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 2n) 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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers
EditorsIsolde Adler, Haiko Müller
Number of pages10
ISBN (Print)9783030604394
Publication statusPublished - 2020
MoE publication typeA4 Conference publication
EventInternational Workshop on Graph-Theoretic Concepts in Computer Science - Leeds, United Kingdom
Duration: 24 Jun 202026 Jun 2020
Conference number: 46

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


WorkshopInternational Workshop on Graph-Theoretic Concepts in Computer Science
Abbreviated titleWG
Country/TerritoryUnited Kingdom


Dive into the research topics of 'On Finding Balanced Bicliques via Matchings'. Together they form a unique fingerprint.

Cite this