On planar graphs, the best way to split the vertices into two groups can be found exactly and fast. A two-way split corresponds to a set of closed loops in the dual graph, the graph whose nodes are the faces of the original. Finding the best loops then reduces to minimum-weight perfect matching, the problem of pairing up nodes at minimum total cost, which Blossom V solves in polynomial time. Yarkony and colleagues used this to compute lower bounds for multi-region image segmentation. Their method builds a linear program (LP) whose columns are two-way cuts and finds each new column with one exact matching call. Their LP bounds are often tight, but turning the fractional LP solution into an actual multi-region partition is still done greedily, by recursive two-way splitting. This proposal replaces that greedy step with a structural one.
The idea is simple. Every two-way cut the LP generates is a valid boundary between regions, and the union of any collection of such boundaries is itself a valid multi-region partition. So the cuts the LP uses form a dictionary of candidate boundaries. Merging each region they leave uncut into a single node gives a much smaller graph, and contracting a planar graph keeps it planar. On that small graph the multi-way problem can be solved exactly, either with an ordinary integer program or with the same planar machinery run again. Constraints that the planar machinery cannot express, such as exactly $k$ regions or region sizes within a balance tolerance, can also be added at that stage. The lower bound from the original LP still holds, so every output carries a certified optimality gap.
Core Claim
The claim is that the support of a planar cut-packing LP solution is, in practice, a near-lossless over-segmentation. When the LP is tight, this contraction loses nothing provably: any optimal partition is a union of the positive-weight cuts, so its boundaries survive contraction. When the LP is fractional, the empirical hypothesis is that the optimal multicut (the set of cut edges defining a multi-region partition) still lies almost entirely inside the union of LP columns. If so, solving exactly on the contracted graph should give lower energy and smaller certified gaps than recursive bipartitioning, at a fraction of the cost of a full integer program. A second claim concerns the multi-way side. Fixed-$k$ and size-balanced partitions are hard to impose inside the matching subproblem: adding per-vertex terms to a frustrated planar binary problem destroys tractability unless the graph is outerplanar, as Efficient Exact Inference in Planar Ising Models notes. They become cheap once the graph has been contracted to a few hundred regions.
Relation to Prior Work
Three papers supply the method and motivate the gap. Fast Planar Correlation Clustering for Image Segmentation frames segmentation with an unspecified number of regions as a 4-label problem, using the Four Color Theorem. It tightens an LP with matching-based cutting planes and decodes by recursive bipartitioning or dual rounding. We keep its LP and replace its decoder. Planar Ultrametrics for Image Segmentation solves a hierarchical version by column generation with matching-based pricing and reports integrality gaps around 0.1%. It shows that the columns found are high quality, which is exactly what our dictionary assumption needs, but it never contracts on them or targets flat $k$-way outputs. Tightening MRF Relaxations with Planar Subproblems decomposes multi-label problems into one-versus-all planar binary subproblems and suffers slow subgradient convergence as the label count grows. Our approach sidesteps label-wise decomposition: labels enter only after contraction.
On the multi-way side, Approximation Algorithm for Sparsest k-Partitioning and Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut constrain what we can promise. General-graph relaxations lose factors such as $2(1-1/k)$ or bicriteria slack, so we make no worst-case approximation claim. We offer per-instance certificates instead. Multiply Balanced k -Partitioning and Size Regularized Cut for Data Clustering show why balance matters, since unbalanced objectives isolate outliers. Neither uses planar exactness, and we impose balance only at the contracted stage. Spectral concentration and greedy k-clustering is the strongest fast multi-way method on a planar-like input, its 12,500-vertex body mesh, and serves as our competitor there.
Research Program
The pipeline has four stages:
- Solve the LP. Run the LP of PlanarCC, or the ultrametric LP when a hierarchy is wanted, to convergence. Keep every column with positive weight.
- Form and contract the over-segmentation. Take the union of the kept columns' boundaries. Contract each connected piece of uncut edges into a single node, and sum edge weights between pieces. This yields a planar region adjacency graph, typically far smaller than the original.
- Solve exactly on the small graph. Without cardinality constraints, solve correlation clustering on the contracted graph exactly by branch-and-cut. If the contracted graph is still too large, re-enter the planar LP on it and recurse. For fixed $k$ or balance, add the corresponding linear constraints to the small integer program.
- Report the gap. Compare the energy of the result against the original LP bound.
The analysis has two parts. First, we prove that tight LPs give lossless contraction: an integral optimal solution in the cut cone decomposes into positive-weight cuts, and every one of those boundary edges is preserved. Second, we measure "boundary recall" on fractional instances, meaning the fraction of the best-known multicut's edges that survive contraction. We also study an enlarged dictionary: cuts sampled from the LP weights plus cuts from matching calls on perturbed edge costs. This tests whether a richer dictionary closes the remaining loss.
Baselines
The naive reference is thresholding the fractional edge values $x_e$ at 0.5, then taking connected components of the uncut edges, which by construction yields a valid multicut. This costs nothing beyond the LP and is the simplest decoder a reviewer would try.
The strongest existing method is PlanarCC itself with its recursive-bipartition decoder, on the same BSDS500 graphs, gPb-derived edge costs and LP solution, so that only the decoder differs. Fast Planar Correlation Clustering for Image Segmentation reports a boundary F-measure of 0.72, against 0.73 for UCM (Ultrametric Contour Maps, the standard greedy merging method), and reports that the LP–decoding gap is "often zero". The file gives no reported per-image fraction of nonzero-gap instances. Beating PlanarCC means lower energy and smaller certified gap on the nonzero-gap images, at equal or lower total wall-clock, with F-measure no worse than 0.72.
A full branch-and-cut integer program on the uncontracted graph is the exactness reference. PlanarCC reports itself 10x to 1000x faster than this; we run it with a fixed time cap matched to our total runtime. UCM, with the reported F of 0.73, is the greedy reference for segmentation quality.
Two ablations isolate the key ingredient, which is the LP-derived dictionary. The first contracts on a same-size over-segmentation from UCM at a matched region count. The second runs greedy local search (vertex moves and region merges) from the PlanarCC decoding, with the same time budget as our exact contracted solve. If either matches us, the LP columns are not what makes the method work.
On the body mesh with fixed $k$, the competitors are greedy radius selection from Spectral concentration and greedy k-clustering and $k$-means on the spectral embedding. That paper reports 97.176% vertex agreement between them, but no cut-cost figure. Beating them means lower cut weight at equal balance tolerance.
Why not just…?
Why not just keep recursive bipartitioning? It commits to early splits that later steps cannot undo, the "global blindness" problem. The PlanarCC authors treat it as a heuristic upper bound without guarantees. Our contracted exact solve sees all candidate boundaries at once. The head-to-head on nonzero-gap BSDS images settles the question. If recursive bipartitioning already closes the gap on almost every image, the method's value shrinks to fixed-$k$ and balanced settings, and we would report that.
Why not just threshold $x_e$ and take components? This is a real threat when the LP is nearly integral, since it then recovers the same answer for free. It fails when fractional mass spreads over competing boundaries, as at T-junctions, the points where three regions meet that PlanarCC handles with extra cycle constraints. The threshold baseline is run on every instance. The decisive measurement is energy split by how fractional the LP solution is, and we expect our advantage to appear only in the fractional tail.
Why not just run local search, or a full integer program? Local search gives no certificate and can stall in local optima. The full program is exact but, per the reported 10x–1000x gap, impractical at matched time. The local-search ablation at equal time, and the time-capped integer program, show directly whether contraction buys anything beyond extra compute.
Proposed Experiments
BSDS500 segmentation. Using gPb edge costs on BSDS500, we report the following per image: energy, the certified gap against the LP bound, boundary recall of the best-known multicut after contraction, contracted graph size, runtime and boundary F-measure.
Synthetic grids. On the 10x10 to 30x30 grids with random and layered potentials from Tightening MRF Relaxations with Planar Subproblems, we can push the LP to be heavily fractional. There PSP and MPLP (max-product LP message passing) serve as bound baselines; PSP is reported as up to 15x faster than MPLP when hot-started.
Body mesh with fixed $k$. For fixed $k$ with balance, we use the 12,500-vertex body mesh, after first checking that it is genus zero via Euler's formula $V-E+F=2$; otherwise it is not planar and is dropped. Candidate boundaries are generated by running the planar cut LP on edge costs shifted to be partly negative, so that cuts are encouraged.
Decisive checks. Three checks decide whether the method works:
- Boundary recall after contraction stays above 99% on fractional instances.
- The contracted exact solve strictly lowers energy relative to recursive bipartitioning on those instances.
- Neither the UCM-dictionary ablation nor the matched-time local search reproduces that gain.
If the first check fails, the dictionary-enlargement study becomes the main result. If the third fails, the LP dictionary is not the active ingredient and the claim is withdrawn.
References
- Efficient Exact Inference in Planar Ising Models
- Fast Planar Correlation Clustering for Image Segmentation
- Planar Ultrametrics for Image Segmentation
- Tightening MRF Relaxations with Planar Subproblems
- Approximation Algorithm for Sparsest k-Partitioning
- Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
- Multiply Balanced k -Partitioning
- Size Regularized Cut for Data Clustering
- Spectral concentration and greedy k-clustering