Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs
Mark Glass, Meir Feder · 2026
Read Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs by Mark Glass, Meir Feder (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28478.txt.
Description
Mark Glass and Meir Feder revisit maximum cut, the problem of splitting a graph's vertices into two groups so the total weight of edges crossing between them is as large as possible. For flat, planar graphs an efficient exact algorithm has existed since 1975, but only for nonnegative weights.
Glass and Feder map the general planar problem to a minimum T-join problem in the absolute dual graph, a reformulation that unlocks shortest-path machinery. Hadlock's classic algorithm then extends straightforwardly to arbitrary weights. For doughnut-shaped toroidal graphs, which are not planar, they prove that ignoring the topology and running the planar algorithm yields a valid upper bound. Several benchmark values, including the three largest toroidal instances, match their bounds and are therefore provably optimal. A new heuristic also found a previously unknown best value for one benchmark.
Catalog record
| CREATOR | Mark Glass, Meir Feder |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28478