stcut

Stcut is a term used in graph theory and network analysis to denote a partition of a graph's vertices that separates a designated start vertex s from a terminal vertex t. In many sources it is used interchangeably with the standard concept of an s-t cut, with "stcut" written as a single word or as "s-t cut." The main idea is to divide V into two disjoint sets S and T = V \ S such that s ∈ S and t ∈ T; the cut is the set of edges that cross from S to T and, in weighted graphs, the cut capacity is the sum of the weights of those crossing edges (directed graphs count edges from S to T).

Direct and undirected variants: In directed graphs, only the edges oriented from S to T contribute to the cut capacity. In undirected graphs, the cut capacity is the sum of weights of edges with endpoints in different sets. A minimum stcut is the cut with the smallest possible capacity among all s-t cuts. By the max-flow min-cut theorem, the value of a minimum s-t cut equals the value of a maximum s-t flow within the same network.

Algorithms and properties: Classic algorithms to compute minimum s-t cuts include Ford-Fulkerson, Edmonds-Karp, Dinic's algorithm, and push-relabel methods. These methods use residual graphs and augmenting paths to reach optimality. The family of stcuts can be analyzed via lattice and submodularity properties and is central to many optimization problems.

Applications and history: The concept is foundational in network design, reliability assessment, and image segmentation via graph cuts. It also underpins resource allocation and circuit layout. The origin of the underlying idea traces to early work on maximum flow and min-cut in the 1950s by Ford and Fulkerson.