On Finding Balanced Bicliques via Matchings

Parinya Chalermsook, Wanchote Po Jiamjitrak, Ly Orgo*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

193 Lataukset (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.

OtsikkoGraph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers
ToimittajatIsolde Adler, Haiko Müller
ISBN (painettu)9783030604394
DOI - pysyväislinkit
TilaJulkaistu - 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Workshop on Graph-Theoretic Concepts in Computer Science - Leeds, Iso-Britannia
Kesto: 24 kesäk. 202026 kesäk. 2020
Konferenssinumero: 46


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta12301 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


WorkshopInternational Workshop on Graph-Theoretic Concepts in Computer Science


Sukella tutkimusaiheisiin 'On Finding Balanced Bicliques via Matchings'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä