Find all vertex sets of minimal size whose removal separates the graph into more components
Details
This function implements the Kanevsky algorithm for finding all minimal-size vertex separators in an undirected graph. See the reference below for the details.
In the special case of a fully connected input graph with \(n\) vertices, all subsets of size \(n-1\) are listed as the result.
References
Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph. Networks 23 533–541, 1993.
JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351–372, 1996.
J. Moody and D. R. White. Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review, 68 103–127, Feb 2003.
See also
Other flow:
dominator_tree(),
edge_connectivity(),
is_min_separator(),
is_separator(),
max_flow(),
min_cut(),
min_st_separators(),
st_cuts(),
st_min_cuts(),
vertex_connectivity()
Examples
# The graph from the Moody-White paper
mw <- graph_from_literal(
1 - 2:3:4:5:6, 2 - 3:4:5:7, 3 - 4:6:7, 4 - 5:6:7,
5 - 6:7:21, 6 - 7, 7 - 8:11:14:19, 8 - 9:11:14, 9 - 10,
10 - 12:13, 11 - 12:14, 12 - 16, 13 - 16, 14 - 15, 15 - 16,
17 - 18:19:20, 18 - 20:21, 19 - 20:22:23, 20 - 21,
21 - 22:23, 22 - 23
)
# Cohesive subgraphs
mw1 <- induced_subgraph(mw, as.character(c(1:7, 17:23)))
mw2 <- induced_subgraph(mw, as.character(7:16))
mw3 <- induced_subgraph(mw, as.character(17:23))
mw4 <- induced_subgraph(mw, as.character(c(7, 8, 11, 14)))
mw5 <- induced_subgraph(mw, as.character(1:7))
min_separators(mw)
#> [[1]]
#> + 1/23 vertex, named, from 5d1ba99:
#> [1] 7
#>
min_separators(mw1)
#> [[1]]
#> + 2/14 vertices, named, from f1ca6bc:
#> [1] 5 19
#>
#> [[2]]
#> + 2/14 vertices, named, from f1ca6bc:
#> [1] 5 7
#>
#> [[3]]
#> + 2/14 vertices, named, from f1ca6bc:
#> [1] 7 21
#>
#> [[4]]
#> + 2/14 vertices, named, from f1ca6bc:
#> [1] 21 19
#>
min_separators(mw2)
#> [[1]]
#> + 2/10 vertices, named, from 7472eda:
#> [1] 10 16
#>
#> [[2]]
#> + 2/10 vertices, named, from 7472eda:
#> [1] 14 16
#>
#> [[3]]
#> + 2/10 vertices, named, from 7472eda:
#> [1] 8 10
#>
min_separators(mw3)
#> [[1]]
#> + 2/7 vertices, named, from c0b3f1b:
#> [1] 21 19
#>
min_separators(mw4)
#> [[1]]
#> + 3/4 vertices, named, from 0aac650:
#> [1] 8 11 14
#>
#> [[2]]
#> + 3/4 vertices, named, from 0aac650:
#> [1] 7 11 14
#>
#> [[3]]
#> + 3/4 vertices, named, from 0aac650:
#> [1] 7 8 14
#>
#> [[4]]
#> + 3/4 vertices, named, from 0aac650:
#> [1] 7 8 11
#>
min_separators(mw5)
#> [[1]]
#> + 5/7 vertices, named, from 11272f8:
#> [1] 2 3 4 5 6
#>
#> [[2]]
#> + 5/7 vertices, named, from 11272f8:
#> [1] 1 3 4 5 7
#>
#> [[3]]
#> + 5/7 vertices, named, from 11272f8:
#> [1] 1 2 4 6 7
#>
# Another example, the science camp network
camp <- graph_from_literal(
Harry:Steve:Don:Bert - Harry:Steve:Don:Bert,
Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat,
Holly - Carol:Pat:Pam:Jennie:Bill,
Bill - Pauline:Michael:Lee:Holly,
Pauline - Bill:Jennie:Ann,
Jennie - Holly:Michael:Lee:Ann:Pauline,
Michael - Bill:Jennie:Ann:Lee:John,
Ann - Michael:Jennie:Pauline,
Lee - Michael:Bill:Jennie,
Gery - Pat:Steve:Russ:John,
Russ - Steve:Bert:Gery:John,
John - Gery:Russ:Michael
)
min_separators(camp)
#> [[1]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Pat Holly
#>
#> [[2]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Pat Michael
#>
#> [[3]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Pat John
#>
#> [[4]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Holly Gery
#>
#> [[5]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Michael Gery
#>
#> [[6]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] John Gery
#>
#> [[7]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Gery Russ
#>
#> [[8]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Holly Michael
#>
#> [[9]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Holly John
#>
#> [[10]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Steve Bert
#>
#> [[11]]
#> + 2/18 vertices, named, from 94b11dc:
#> [1] Steve Russ
#>