# st_min_cuts

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

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

- Keywords
- graphs

##### 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 unweighed (=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:

Numeric scalar, the size of the minimum cut(s).

A list of numeric vectors containing edge ids. Each vector is a minimum \((s,t)\)-cut.

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\).

##### References

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

##### See Also

##### Examples

```
# NOT RUN {
# A difficult graph, from the Provan-Shier paper
g <- graph_from_literal(s --+ a:b, a:b --+ t,
a --+ 1:2:3:4:5, 1:2:3:4:5 --+ b)
st_min_cuts(g, source="s", target="t")
# }
```

*Documentation reproduced from package igraph, version 1.0.1, License: GPL (>= 2)*