Uncrossing

Uncrossing is a technique used in combinatorial optimization to simplify families of sets or cuts by removing crossings between pairs of sets. The goal is to transform a potentially complex collection into a laminar family, where any two sets are either disjoint or one contains the other. This structural simplification often makes analysis and computation easier without losing feasibility or worsening the objective in many optimization problems.

The method relies on submodularity, a natural property of many set functions in optimization. For two sets A and B, a submodular function f satisfies f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B). In practice, when a collection F contains crossing pairs, one can replace the pair (A,B) with (A ∪ B) and (A ∩ B) and argue that feasibility is preserved (or improved) and the objective does not deteriorate under certain conditions. Repeating this replacement across all crossing pairs yields a laminar family. The result is often an optimal or near-optimal structure that is easier to handle computationally and conceptually.

Uncrossing appears in a wide range of settings, including network design, cut theory, and polyhedral studies of submodular and matroid-related problems. It is used to prove the existence of optimal solutions with laminar constraints, derive tight structural lemmas, and justify simplifications in approximation algorithms for problems such as Steiner trees and other connectivity issues. Variants include dual uncrossing and applications to polymatroids and submodular function minimization.