# R igraph manual pages

Use this if you are using igraph from R

 st_min_cuts {igraph} R Documentation

## List all minimum `(s,t)`-cuts of a graph

### Description

Listing all minimum `(s,t)`-cuts of a directed graph, for given `s` and `t`.

### Usage

``````st_min_cuts(graph, source, target, capacity = NULL)
``````

### Arguments

 `graph` The input graph. It must be directed. `source` The id of the source vertex. `target` The id of the target vertex. `capacity` Numeric vector giving the edge capacities. If this is `NULL` and the graph has a `weight` edge attribute, then this attribute defines the edge capacities. For forcing unit edge capacities, even for graphs that have a `weight` edge attribute, supply `NA` here.

### Details

Given a `G` directed graph and two, different and non-ajacent vertices, `s` and `t`, an `(s,t)`-cut is a set of edges, such that after removing these edges from `G` there is no directed path from `s` to `t`.

The size of an `(s,t)`-cut is defined as the sum of the capacities (or weights) in the cut. For unweighted (=equally weighted) graphs, this is simply the number of edges.

An `(s,t)`-cut is minimum if it is of the smallest possible size.

### Value

A list with entries:

 `value` Numeric scalar, the size of the minimum cut(s). `cuts` A list of numeric vectors containing edge ids. Each vector is a minimum `(s,t)`-cut. `partition1s` A list of numeric vectors containing vertex ids, they correspond to the edge cuts. Each vertex set is a generator of the corresponding cut, i.e. in the graph `G=(V,E)`, the vertex set `X` and its complementer `V-X`, generates the cut that contains exactly the edges that go from `X` to `V-X`.

### Author(s)

Gabor Csardi csardi.gabor@gmail.com

### References

JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351–372, 1996.

`st_cuts`, `min_separators`
``````