Exact penalties for maximum-edge bicliques in bipartite graphs
Abstract
Given a bipartite graph G, we denote by g(G) the largest product |A||B| over pairs of vertex sets A and B, one on each side, with no edge between them. These pairs are the bicliques of the bipartite complement of G; hence, computing g(G) is the maximum-edge biclique problem, which is NP-hard, as shown by Peeters in 2003. Gillis and Glineur characterized it by a continuous quadratic program, in which a large enough penalty on the edges of G makes the global maximizers correspond to the maximum pairs and the local maximizers to the maximal ones. We propose a new threshold for the penalty, which depends only on g(G). For any penalty at or above it, the global maximizers correspond exactly to the maximum pairs, and every local maximizer with positive value corresponds to a maximal pair. This threshold is never larger than theirs and is sharp up to an additive 1/2. Spectral and semidefinite bounds give computable penalties; in experiments, a simple local ascent succeeds far more often with the semidefinite one than with the earlier thresholds, although on our graphs that bound already reveals g(G). The penalty formulation, whose optimal value is √(g(G))/2, is also a copositive formulation of g(G). Strengthening a semidefinite bound of Laurent, Polak and Vargas with the completely positive cone gives exactly √(g(G))/2, while the doubly nonnegative strengthening is already inexact on six vertices. Finally, Pólya's linear programming approximations of the copositive cone become finite at an explicit level and converge to √(g(G))/2 without ever being exact.
Related
- Maximum number of spanning trees in bipartite graphs with a given diameter
- Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
- Exact three-component covers in 2-coloured random bipartite graphs
- Tree-independence number of P5-free graphs with no large bicliques
- When are random regular triangle-free graphs bipartite?
BibTeX
@misc{emine2026exact,
title = {{Exact penalties for maximum-edge bicliques in bipartite graphs}},
author = {Youssouf Emine and Bissan Ghaddar},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07239},
eprint = {2611.07239},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07239},
}
RIS
TY - UNPB
TI - Exact penalties for maximum-edge bicliques in bipartite graphs
AU - Youssouf Emine
AU - Bissan Ghaddar
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07239
UR - https://arxiv.org/abs/2611.07239
AB - Given a bipartite graph G, we denote by g(G) the largest product |A||B| over pairs of vertex sets A and B, one on each side, with no edge between them. These pairs are the bicliques of the bipartite complement of G; hence, computing g(G) is the maximum-edge biclique problem, which is NP-hard, as shown by Peeters in 2003. Gillis and Glineur characterized it by a continuous quadratic program, in which a large enough penalty on the edges of G makes the global maximizers correspond to the maximum pairs and the local maximizers to the maximal ones. We propose a new threshold for the penalty, which depends only on g(G). For any penalty at or above it, the global maximizers correspond exactly to the maximum pairs, and every local maximizer with positive value corresponds to a maximal pair. This threshold is never larger than theirs and is sharp up to an additive 1/2. Spectral and semidefinite bounds give computable penalties; in experiments, a simple local ascent succeeds far more often with the semidefinite one than with the earlier thresholds, although on our graphs that bound already reveals g(G). The penalty formulation, whose optimal value is √(g(G))/2, is also a copositive formulation of g(G). Strengthening a semidefinite bound of Laurent, Polak and Vargas with the completely positive cone gives exactly √(g(G))/2, while the doubly nonnegative strengthening is already inexact on six vertices. Finally, Pólya's linear programming approximations of the copositive cone become finite at an explicit level and converge to √(g(G))/2 without ever being exact.
ER -