pith. sign in

arxiv: 2604.27141 · v1 · submitted 2026-04-29 · 💻 cs.DS

Improved Approximation Algorithm for Maximum Balanced Biclique

Pasin Manurangsi This is my paper

Pith reviewed 2026-05-07 09:53 UTC · model grok-4.3

classification 💻 cs.DS
keywords maximum balanced bicliqueapproximation algorithmsbipartite graphsmaximum cliquepolynomial-time algorithms
0
0 comments X

The pith

An improved algorithm approximates the maximum balanced biclique to within n over (log n) cubed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on the Maximum Balanced Biclique problem, which seeks the largest set of vertices inducing a complete bipartite subgraph with equal sides in a balanced bipartite graph. It develops a polynomial-time algorithm that guarantees an approximation ratio of n divided by tilde-Omega of (log n) cubed. This is an improvement over the previous best ratio of n divided by Omega of (log n) squared. The result also shows that the approximation is close to the best known for the maximum clique problem, differing only by an O(log log n) factor.

Core claim

We give a polynomial-time (n/Õ((log n)^3))-approximation algorithm for the Maximum Balanced Biclique problem, which improves upon an (n/Ω((log n)^2))-approximation by Chalermsook et al. (2020) and answers their open question. Furthermore, our approximation ratio matches that of the maximum clique problem by Feige (2004) up to an O(log log n) factor.

What carries the argument

The new polynomial-time algorithmic construction for approximating the size of the maximum balanced biclique in a bipartite graph

Load-bearing premise

The analysis establishing that the new algorithmic construction achieves the claimed approximation ratio holds without hidden gaps or post-hoc adjustments.

What would settle it

Finding a bipartite graph on which the algorithm returns a balanced biclique whose size is less than the optimal size divided by n over (log n) cubed would disprove the approximation guarantee.

Figures

Figures reproduced from arXiv: 2604.27141 by Pasin Manurangsi.

Figure 1
Figure 1. Figure 1: SDP Relaxation for MBB (First Attempt) If G contains Kk,k, there is a feasible solution (setting vectors in the biclique to e and all others to 0) of value k. We remark that the only difference compared to the Maximum Clique formulation here is the constraint (1), which aims to ensure that the number of vertices picked in U is the same as that in V (so that the biclique is balanced). Unfortunately, this SD… view at source ↗
Figure 2
Figure 2. Figure 2: SDP Relaxation for MBB We note that the only additional constraints are (5) and (6), which are “fractional degree” constraints aiming to ensure that if i is picked, then k of its neighbor must be picked. Again, if G contains Kk,k, there is a feasible solution (setting vectors in the biclique to e and all others to 0). Our main technical contribution (Theorem 3) is to show that a feasible solution to this S… view at source ↗
Figure 3
Figure 3. Figure 3: SDP Rounding Algorithm for MBB Proof of Theorem 3. We will next analyze the guarantee of the rounding algorithm. To do so, let D = 1000 and assume that t ≤ log n D·log log n . For any subsets S ⊆ U and T ⊆ V , let M(S, T) := P (i,j)∈S×T ⟨ui , uj ⟩. We have M(A, B) = M(U, V ) − M(U \ A, V ) − M(U, V \ B) + M(U \ A, V \ B) (4) ≥ M(U, V ) − M(U \ A, V ) − M(U, V \ B) = X i∈U   X j∈V ⟨ui , uj ⟩   − X i∈U\A… view at source ↗
read the original abstract

We study the Maximum Balanced Biclique (MBB) problem: Given a bipartite graph $G$ with $n$ vertices on each side, find a balanced biclique in $G$ with maximum size. We give a polynomial-time $\left(\frac{n}{\widetilde{\Omega}\left((\log n)^3\right)}\right)$-approximation algorithm for the problem, which improves upon an $\left(\frac{n}{\Omega\left((\log n)^2\right)}\right)$-approximation by Chalermsook et al. (2020) and answers their open question. Furthermore, our approximation ratio matches that of the maximum clique problem by Feige (2004) up to an $O(\log \log n)$ factor.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims a polynomial-time approximation algorithm for the Maximum Balanced Biclique problem on balanced bipartite graphs with n vertices per side, achieving an approximation ratio of n / Õ((log n)^3). This improves the prior n / Ω((log n)^2) ratio of Chalermsook et al. (2020) and resolves their open question; the ratio is also stated to match Feige's (2004) max-clique bound up to an O(log log n) factor.

Significance. If the analysis establishing the ratio is correct, the result is a clear incremental advance in approximation algorithms for biclique problems. It tightens the gap to the best-known bounds for the related maximum-clique problem and supplies a concrete algorithmic construction that answers a stated open question, which may guide further work on dense-subgraph approximation.

minor comments (2)
  1. [Abstract] Abstract: the notation Õ and Ω̃ should be defined explicitly on first use or a reference to the standard definition supplied, to avoid ambiguity for readers outside the immediate sub-area.
  2. [Introduction] The manuscript should include a short comparison paragraph (e.g., in the introduction) that isolates the new technical ingredient responsible for shaving one log n factor relative to Chalermsook et al. (2020).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, for recognizing that the result improves upon Chalermsook et al. (2020) and resolves their open question, and for recommending minor revision. We are pleased that the work is viewed as a clear incremental advance that tightens the gap to Feige's maximum-clique bound.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a new polynomial-time approximation algorithm for Maximum Balanced Biclique, deriving the n / Õ((log n)^3) ratio directly from the analysis of its algorithmic construction. This improves on a prior result by unrelated authors (Chalermsook et al. 2020) without any self-citation load-bearing the central claim, fitted parameters renamed as predictions, or self-definitional equations. The derivation is a standard algorithmic proof and analysis that remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or ad-hoc axioms are introduced; the work relies on standard mathematical assumptions in approximation algorithms for NP-hard problems.

axioms (1)
  • domain assumption The Maximum Balanced Biclique problem is NP-hard and admits no polynomial-time exact algorithm unless P=NP.
    Standard complexity assumption invoked to motivate approximation algorithms.

pith-pipeline@v0.9.0 · 5412 in / 1245 out tokens · 57449 ms · 2026-05-07T09:53:15.593467+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Approximating the independence number via the theta-function

    Noga Alon and Nabil Kahal \' e . Approximating the independence number via the theta-function. Math. Program. , 80:253--264, 1998

    work page 1998

  2. [2]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM , 45(3):501--555, 1998

    work page 1998

  3. [3]

    Probabilistic checking of proofs: A new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP . J. ACM , 45(1):70--122, 1998

    work page 1998

  4. [4]

    Bipartite independence number in graphs with bounded maximum degree

    Maria Axenovich, Jean - S \' e bastien Sereni, Richard Snyder, and Lea Weber. Bipartite independence number in graphs with bounded maximum degree. SIAM J. Discret. Math. , 35(2):1136--1148, 2021

    work page 2021

  5. [5]

    Bi-covering: Covering edges with two small subsets of vertices

    Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Bi-covering: Covering edges with two small subsets of vertices. SIAM J. Discret. Math. , 31(4):2626--2646, 2017

    work page 2017

  6. [6]

    Free bits, pcps, and nonapproximability-towards tight results

    Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, pcps, and nonapproximability-towards tight results. SIAM J. Comput. , 27(3):804--915, 1998

    work page 1998

  7. [7]

    Boppana and Magn \' u s M

    Ravi B. Boppana and Magn \' u s M. Halld \' o rsson. Approximating maximum independent sets by excluding subgraphs. In John R. Gilbert and Rolf G. Karlsson, editors, SWAT , pages 13--25, 1990

    work page 1990

  8. [8]

    On finding balanced bicliques via matchings

    Parinya Chalermsook, Wanchote Po Jiamjitrak, and Ly Orgo. On finding balanced bicliques via matchings. In WG 2020 , pages 238--247, 2020

    work page 2020

  9. [9]

    Towards optimal lower bounds for clique and chromatic number

    Lars Engebretsen and Jonas Holmerin. Towards optimal lower bounds for clique and chromatic number. Theor. Comput. Sci. , 299(1-3):537--584, 2003

    work page 2003

  10. [10]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In STOC , pages 534--543, New York, NY, USA, 2002. ACM

    work page 2002

  11. [11]

    Approximating maximum clique by removing subgraphs

    Uriel Feige. Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. , 18(2):219--225, 2004

    work page 2004

  12. [12]

    An introduction to probability theory and its applications, Volume 2 , volume 2

    William Feller. An introduction to probability theory and its applications, Volume 2 , volume 2. John Wiley & Sons, 1991

    work page 1991

  13. [13]

    Interactive proofs and the hardness of approximating cliques

    Uriel Feige, Shafi Goldwasser, L \' a szl \' o Lov \' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM , 43(2):268--292, 1996

    work page 1996

  14. [14]

    Hardness of approximation of the balanced complete bipartite subgraph problem

    Uriel Feige and Shimon Kogan. Hardness of approximation of the balanced complete bipartite subgraph problem. Technical report, Weizmann Institute of Science, Rehovot, Israel, 2004

    work page 2004

  15. [15]

    Balanced coloring of bipartite graphs

    Uriel Feige and Shimon Kogan. Balanced coloring of bipartite graphs. J. Graph Theory , 64(4):277--291, 2010

    work page 2010

  16. [16]

    Garey and David S

    Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA, 1979

    work page 1979

  17. [17]

    Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

    Eran Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. , 31(5):1608--1623, 2002

    work page 2002

  18. [18]

    Clique is hard to approximate within n^ 1 -

    Johan H stad. Clique is hard to approximate within n^ 1 - . In FOCS , pages 627--636, 1996

    work page 1996

  19. [19]

    David S. Johnson. The np-completeness column: An ongoing guide. J. Algorithms , 8(5):438--448, September 1987

    work page 1987

  20. [20]

    Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations , pages 85--103, 1972

    work page 1972

  21. [21]

    Kleinberg and Michel X

    Jon M. Kleinberg and Michel X. Goemans. The lov \' a sz theta function and a semidefinite programming relaxation of vertex cover. SIAM J. Discret. Math. , 11(2):196--204, 1998

    work page 1998

  22. [22]

    Improved inaproximability results for maxclique, chromatic number and approximate graph coloring

    Subhash Khot. Improved inaproximability results for maxclique, chromatic number and approximate graph coloring. In FOCS , pages 600--609, 2001

    work page 2001

  23. [23]

    Ruling out ptas for graph min‐bisection, dense k‐subgraph, and bipartite clique

    Subhash Khot. Ruling out ptas for graph min‐bisection, dense k‐subgraph, and bipartite clique. SIAM Journal on Computing , 36(4):1025--1071, 2006

    work page 2006

  24. [24]

    Better inapproximability results for maxclique, chromatic number and min-3lin-deletion

    Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In ICALP , pages 226--237, 2006

    work page 2006

  25. [25]

    On the shannon capacity of a graph

    L \' a szl \' o Lov \' a sz. On the shannon capacity of a graph. IEEE Trans. Inf. Theory , 25(1):1--7, 1979

    work page 1979

  26. [26]

    Almost-polynomial ratio eth-hardness of approximating densest k-subgraph

    Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In STOC , pages 954--961, 2017

    work page 2017

  27. [27]

    Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis

    Pasin Manurangsi. Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms , 11(1):10, 2018

    work page 2018

  28. [28]

    Answer to ``approximation algorithm for balanced bipartite independent set?''

    Pasin Manurangsi. Answer to ``approximation algorithm for balanced bipartite independent set?''. Theoretical Computer Science Stack Exchange, August 2022. Online; accessed 14-April-2026

    work page 2022

  29. [29]

    Linear degree extractors and the inapproximability of max clique and chromatic number

    David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. , 3(1):103--128, 2007

    work page 2007