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

## 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.

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

## 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.

## References

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

## See also

Other flow:
`dominator_tree()`

,
`edge_connectivity()`

,
`is_min_separator()`

,
`is_separator()`

,
`max_flow()`

,
`min_cut()`

,
`min_separators()`

,
`min_st_separators()`

,
`st_cuts()`

,
`vertex_connectivity()`

## Author

Gabor Csardi csardi.gabor@gmail.com

## Examples

```
# 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")
#> $value
#> [1] 2
#>
#> $cuts
#> $cuts[[1]]
#> + 2/14 edges from 87f32a6 (vertex names):
#> [1] s->a s->b
#>
#> $cuts[[2]]
#> + 2/14 edges from 87f32a6 (vertex names):
#> [1] s->a b->t
#>
#> $cuts[[3]]
#> + 2/14 edges from 87f32a6 (vertex names):
#> [1] a->t b->t
#>
#>
#> $partition1s
#> $partition1s[[1]]
#> + 1/9 vertex, named, from 87f32a6:
#> [1] s
#>
#> $partition1s[[2]]
#> + 2/9 vertices, named, from 87f32a6:
#> [1] s b
#>
#> $partition1s[[3]]
#> + 8/9 vertices, named, from 87f32a6:
#> [1] s b a 5 4 3 2 1
#>
#>
```