min_separators {igraph}

Minimum size vertex separators

Description

Find all vertex sets of minimal size whose removal separates the graph into more components

Usage

min_separators(graph)

Arguments

graph

The input graph. It may be directed, but edge directions are ignored.

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.

Value

A list of numeric vectors. Each numeric vector is a vertex separator.

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)
min_separators(mw1)
min_separators(mw2)
min_separators(mw3)
min_separators(mw4)
min_separators(mw5)

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