Sharp Polynomial-Time Upper Bounds for Minimum Bisection

Definitions and mathematical statement

Source formulation. Let $\mathcal G$ denote the graph class intended by the source, and let $\operatorname{OPT}(G)$ denote its minimum-bisection objective. The supplied record does not specify the graph class or fully define this objective.

Under the conventional interpretation for a finite, undirected, unweighted graph $G=(V,E)$, define \[ \delta_G(S)=\{e\in E: e\text{ has exactly one endpoint in }S\}. \] If bisections are permitted to have part sizes differing by at most one, their minimum cut size is \[ \operatorname{OPT}(G)=\min_{\substack{S\subseteq V\\ |S|=\lfloor |V|/2\rfloor}}|\delta_G(S)|. \] For even $|V|$, this requires two parts of equal size. This definition is a conditional interpretation: the record does not specify whether odd-order graphs are included, whether graphs are simple or weighted, or whether another normalization of the objective is intended.

Requested construction. Construct a function $\operatorname{UB}$, computable in time polynomial in the input encoding length, such that \[ \forall G\in\mathcal G,\qquad \operatorname{OPT}(G)\leq \operatorname{UB}(G), \] and such that $\operatorname{UB}(G)$ is asymptotically sharp on random graphs. The direction of the inequality is retained exactly as supplied: it requests an upper bound on a minimization objective.

The random-graph distribution, its parameter regime, and the meaning of asymptotic sharpness are unspecified. In particular, the record does not determine whether sharpness means a vanishing relative error, an additive error on a specified scale, or agreement of a centered leading-order term; nor does it specify a probabilistic mode of convergence. Consequently the random-graph requirement cannot be given a unique quantified formulation from this record. The background mentions sparse random graphs, but supplies no distribution or sparsity regime and does not establish that this is the entire intended target class.

Short English statement

Find a polynomial-time computable upper bound for the minimum-bisection value that is valid for every graph in the intended class and asymptotically matches that value on the intended random graphs. The graph conventions, random model, and required accuracy remain unspecified, so this is a conditional statement-only draft requiring mathematical review.

Sources

• Local UnsolvedMath registry, supplied complete source record for permanent ID $30003679$, source problem code catalogue entry, titled "Sharp Polynomial-Time Upper Bounds for Minimum Bisection," in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2017 and names no proposer.
• Supplied report citation: Network Models: Structure and Function (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/57, pp. 3427--3470. https://doi.org/10.4171/owr/2017/57. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation is supplied provenance; its support for the precise formulation has not been independently verified.
• Supplied literature source: Semidefinite programs on sparse random graphs. https://arxiv.org/abs/1504.05910.
• Supplied literature source: On the Max-Cut of sparse random graphs. https://arxiv.org/abs/1411.1698.
• Supplied literature source: OWR Report 57/2019. https://ems.press/content/serial-article-files/46721.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem "partially solved" and states that polynomial-time semidefinite programs give rigorous upper bounds with the correct leading-order scale for sparse random graphs, while the requested generally sharp approximation to the optimum remains open. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says that mathematical content was preserved while notation, typography, and sentence structure were repaired for publication. These are supplied editorial assertions, not independent mathematical verification of this draft.