✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-241

Minimum Cut Problems

Minimum Cut Problems identify the least total capacity of edges whose removal separates a source from a sink in a network. The concept is closely connected to maximum flow through the Max-Flow Min-Cut Theorem.

Explanation

Overview

A cut in a directed network divides its vertices into two disjoint sets, S and T, such that the source belongs to S and the sink belongs to T. The capacity of the cut is the sum of the capacities of all edges directed from S to T. A minimum cut is a cut with the smallest possible capacity among all source-to-sink cuts.

Key concepts

name: Cut; description: A partition of the network's vertices into a source side and a sink side.; name: Cut Capacity; description: The sum of capacities of edges crossing from the source side to the sink side.; name: Minimum Cut; description: A source-to-sink cut having the smallest possible capacity.; name: Cut Edges; description: Edges directed from the source side to the sink side that contribute to the cut capacity.

Mathematical model

objective: Minimize the sum of capacities of edges directed from the source side to the sink side.; constraint: The source must remain on one side and the sink on the other.; importantNote: For directed graphs, only edges directed from the source side to the sink side contribute to the cut capacity.

Complexity

usingEdmondsKarp: O(V × E²) for the maximum-flow computation, followed by O(V + E) for the residual reachability search.; additionalSpace: O(V + E) for graph and search structures.

Example

scenario: A communication network connects a server to a destination through several routers.; description: Each connection has a maximum capacity. A cut separates the server from the destination by dividing the routers into two groups.; interpretation: The capacity of the cut is the combined capacity of all connections crossing from the server's group to the destination's group.; goal: Find the cut with the smallest total capacity, which identifies a minimum-capacity separation of the network.

Applications

Identifying bottlenecks in transportation networks.; Measuring communication network vulnerability.; Image segmentation and computer vision.; Clustering and graph partitioning.; Supply chain analysis.; Reliability and infrastructure planning.

Limitations

A minimum cut identifies a low-capacity separation but does not automatically model every real-world failure scenario.; The result depends on the accuracy of the edge-capacity model.; Some applications require multiple-terminal cuts or other variants rather than a single source-to-sink cut.; A minimum cut based only on capacity may not capture cost, reliability, or fairness considerations.

Example or application

Scenario

A communication network connects a server to a destination through several routers.

Description

Each connection has a maximum capacity. A cut separates the server from the destination by dividing the routers into two groups.

Interpretation

The capacity of the cut is the combined capacity of all connections crossing from the server's group to the destination's group.

Goal

Find the cut with the smallest total capacity, which identifies a minimum-capacity separation of the network.

Definition

A cut in a directed network divides its vertices into two disjoint sets, S and T, such that the source belongs to S and the sink belongs to T. The capacity of the cut is the sum of the capacities of all edges directed from S to T. A minimum cut is a cut with the smallest possible capacity among all source-to-sink cuts.

Key Concepts

NameDescription

Cut

A partition of the network's vertices into a source side and a sink side.

Cut Capacity

The sum of capacities of edges crossing from the source side to the sink side.

Minimum Cut

A source-to-sink cut having the smallest possible capacity.

Cut Edges

Edges directed from the source side to the sink side that contribute to the cut capacity.

Mathematical Model

Objective

Minimize the sum of capacities of edges directed from the source side to the sink side.

Constraint

The source must remain on one side and the sink on the other.

Important Note

For directed graphs, only edges directed from the source side to the sink side contribute to the cut capacity.

Relationship To Maximum Flow

Theorem

Max-Flow Min-Cut Theorem

Statement

The maximum value of an s-to-t flow equals the minimum capacity of an s-to-t cut.

Explanation

When a maximum flow has been found, the vertices reachable from the source through positive residual-capacity edges form the source side of a minimum cut. The edges crossing from that side to the unreachable side identify a minimum cut.

Algorithmic Approach

  • Compute a maximum flow using an algorithm such as Edmonds-Karp.

  • Construct the final residual graph.

  • Run a graph search from the source using edges with positive residual capacity.

  • Place all reachable vertices on the source side.

  • Place all remaining vertices on the sink side.

  • Identify original edges directed from the source side to the sink side.

  • Sum their original capacities to obtain the minimum cut capacity.

Complexity

Using Edmonds Karp

O(V × E²) for the maximum-flow computation, followed by O(V + E) for the residual reachability search.

Additional Space

O(V + E) for graph and search structures.

Applications

  • Identifying bottlenecks in transportation networks.

  • Measuring communication network vulnerability.

  • Image segmentation and computer vision.

  • Clustering and graph partitioning.

  • Supply chain analysis.

  • Reliability and infrastructure planning.

Limitations

  • A minimum cut identifies a low-capacity separation but does not automatically model every real-world failure scenario.

  • The result depends on the accuracy of the edge-capacity model.

  • Some applications require multiple-terminal cuts or other variants rather than a single source-to-sink cut.

  • A minimum cut based only on capacity may not capture cost, reliability, or fairness considerations.

Related Topics

  • INFO-CS-ADS-238

  • INFO-CS-ADS-239

  • INFO-CS-ADS-240

  • INFO-CS-ADS-242

Practice Questions

QuestionAnswer

What is a minimum cut?

A source-to-sink partition whose crossing edges have the smallest possible total capacity.

Which edges contribute to the capacity of a directed cut?

Edges directed from the source side to the sink side.

How is a minimum cut related to maximum flow?

Their values are equal according to the Max-Flow Min-Cut Theorem.

How can a minimum cut be recovered after computing maximum flow?

Find vertices reachable from the source in the final residual graph and identify original edges crossing to unreachable vertices.

Learning Objectives

  • Explain the central idea and purpose of minimum cut problems.

  • Identify the assumptions, inputs, and conditions relevant to minimum cut problems.

  • Evaluate an application of minimum cut problems for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Algorithm Theory and Applications

Suggest a correction or source · More in Algorithms & Data Structures