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 contributionScientificpeer-review

32 Downloads (Pure)

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 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
Pages238-247
Number of pages10
DOIs
Publication statusPublished - 2020
MoE publication typeA4 Article in a 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)
PublisherSpringer
Volume12301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopInternational Workshop on Graph-Theoretic Concepts in Computer Science
Abbreviated titleWG
CountryUnited Kingdom
CityLeeds
Period24/06/202026/06/2020

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

Cite this