On Finding Balanced Bicliques via Matchings
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2020
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
Series
Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers, pp. 238-247, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ; Volume 12301 LNCS
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.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Chalermsook, P, Jiamjitrak, W P & Orgo, L 2020, On Finding Balanced Bicliques via Matchings . in I Adler & H Müller (eds), Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12301 LNCS, Springer, pp. 238-247, International Workshop on Graph-Theoretic Concepts in Computer Science, Leeds, United Kingdom, 24/06/2020 . https://doi.org/10.1007/978-3-030-60440-0_19