Complexity and Approximation of Planar Min-Bisection

Planar bisection: exact balance on trees and failure of additive-error transfer

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

A PTAS has approximation ratio $1+\varepsilon$ for minimization (or $1-\varepsilon$ for maximization), with polynomial runtime for each fixed $\varepsilon>0$. A fully polynomial scheme is polynomial also in $\varepsilon^{-1}$.

A bisection partitions the vertices into two parts of equal size (or differing by one for odd order). Its cut consists of the edges joining the parts; minimum bisection minimizes their total weight.

Statement recorded in the supplied source.

What is the exact computational complexity of PLANAR MIN-BISECTION, and does PLANAR MIN-BISECTION admit a polynomial-time approximation scheme? [S2]

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Classify the difficulty of minimum bisection on planar graphs and decide whether arbitrarily accurate efficient approximation is possible.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000061 (OWR-730-011). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Approximation Algorithms for NP-Hard Problems $2005$, Oberwolfach Reports, DOI 10.4171/owr/2004/28, pp. 1461--1540 https://doi.org/10.4171/owr/2004/28.
• S3 planar Min-Bisection complexity survey https://sites.cs.ucsb.edu/~daniello/papers/bisection.pdf. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

What is the exact computational complexity of PLANAR MIN-BISECTION, and does PLANAR MIN-BISECTION admit a polynomial-time approximation scheme?

Attempted separator and balance route

The source asks both exact complexity and a multiplicative PTAS for planar minimum bisection. We retain exact part-size balance, with a one-vertex difference allowed at odd order. To isolate the global constraint, we first give a complete dynamic program for trees and then test the proposed extension of an additive cut bound to a multiplicative guarantee. Trees are only a planar special class.

A complete tree dynamic program.

Root a weighted tree at $r$. Let $V_v$ denote the vertices of the subtree rooted at $v$, and let $D_v(k,b)$ be the minimum weight of crossing edges internal to that subtree among assignments of its vertices to sides zero and one, with exactly $k$ vertices on side one and $v$ on side $b\in\{0,1\}$. Impossible states have value $+\infty$. For a leaf, $D_v(b,b)=0$ and all other states are impossible. Process the children $u$ one at a time, starting from these single-vertex states. If a partial table is $D$, the update is \[ D_{\rm new}(k,b)=\min_{\substack{0\le j\le |V_u|\\c\in\{0,1\}}} \{D(k-j,b)+D_u(j,c)+w(vu){\bf1}_{b\ne c}\}, \] where $j$ ranges over all valid subtree sizes and the notation means a minimum over such $j$ and the two choices of $c$. Every assignment uniquely restricts to the earlier children, the new child's subtree, and the one edge $vu$. Its cost is exactly the displayed sum. Conversely any two feasible component assignments combine because no other edge joins them. This proves the recurrence in both directions. Induction over children and then vertices proves every table value. Finally minimize $D_r(k,b)$ over $b$ and $k\in\{\lfloor n/2\rfloor,\lceil n/2\rceil\}$. Backtracking the minimizing choices gives an actual bisection.

There are $O(n)$ entries per table and at most $n-1$ child merges, each using at most $O(n^2)$ pairs of counts and a constant number of side labels, so $O(n^3)$ arithmetic operations suffice. For rational edge weights, finite sums and comparisons have polynomial bit cost in their encoded lengths, since each sum involves at most $n-1$ input weights. This is an exact algorithm for trees, not for arbitrary planar graphs with edges across several subproblems.

Two explicit failed simplifications.

On the unit-weight star with $2m$ vertices, $m\ge2$, every bisection has exactly $m$ leaves opposite the center and cut size $m$. The unconstrained nontrivial minimum cut isolates one leaf and has size one. Thus solving minimum cut and hoping balance comes automatically loses an unbounded factor, already on a tree.

An additive guarantee of the form $A\le\operatorname{OPT}+\eta n$ also does not imply a $(1+\eta)$ ratio uniformly. On a unit path with $2m$ vertices, the first $m$ versus last $m$ vertices gives a bisection of size one; every nontrivial cut has size at least one because the path is connected. Hence $\operatorname{OPT}=1$, while the additive allowance is $2\eta m$. To get relative error $\varepsilon$ from this allowance one would need $\eta\le\varepsilon/(2m)$, not a fixed accuracy parameter. This disproves only the logical conversion of bounds. It does not prove that every algorithm with an additive guarantee returns a bad cut on paths, or preclude a PTAS using additional structure.

Audit and first general gap

The primary two questions on printed page 1533 were inspected, without importing the nearby planar maximum-bisection result. The recurrence retains the count in every state. General planar subproblems can interact through multiple boundary vertices, so the two-state root-side summary is no longer sufficient; an algorithm must control those boundary configurations and the relative error when the optimum is small. No general planar recurrence or cost bound is proved. The audit checked odd $n$, exact balance, rational weights, and the difference between additive and relative error. No computational experiment was run and no current complexity classification is claimed.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. An exact tree algorithm and two obstruction families are proved, but neither general planar exact complexity nor a multiplicative PTAS is resolved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 28/2004, Approximation Algorithms for NP-Hard Problems, original question and surrounding discussion read from the cached primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://doi.org/10.4171/owr/2004/28.

Final status

Unresolved in this attempt. An exact tree algorithm and two obstruction families are proved, but neither general planar exact complexity nor a multiplicative PTAS is resolved.