MincutLPbased
MincutLPbased refers to a class of algorithms for computing minimum s-t cuts by formulating the problem as a linear program (LP). The approach exploits linear programming duality with the classic max-flow min-cut theorem: solving an LP that encodes a cut yields the minimum cut value, and, in many graph families, the LP solution is integral and corresponds to a valid cut.
A typical formulation assigns a variable x_e to each directed edge e, representing whether e is included
Variants of mincutLPbased extend the basic model to directed or undirected graphs, multiple sources or sinks,
Relation to other approaches: while highly tuned max-flow algorithms (for example, push-relabel) remain the fastest for
See also: maximum flow, min-cut theorem, Gomory-Hu tree, linear programming, cutting planes.