# Find ALL minimum vertex cuts in a directed graph

Bug introduced in 10.0 or earlier and persisting through 12.1

Suppose I have this graph

edges = {TX -> R1, R1 -> R3, R3 -> R5, R5 -> RX, TX -> R2, R2 -> R4,
R4 -> R6, R6 -> RX, R1 -> R2, R2 -> R3, R3 -> R4, R4 -> R5,
R5 -> R6, TX -> R7, TX -> R8, R7 -> R9, R9 -> R6, R9 -> RX,
R8 -> R6};


When I use FindVertexCut[edges, TX, RX] it returns node {R5, R6}. To disconnect this graph I should be getting {R5,R6,R7} and {R5,R6,R9}. Any advice? Basically, how can I find the ALL minimum cut sets and minimum path sets where a set may contain 1 element, 2 elements, 3 elements, ..., n elements?

• In the version you use does FindVertexCut work on the edges list directly? In v10.1 I need to use Graph. Commented Apr 1, 2017 at 19:55
• @Mr.Wizard Since v10.4 (I think) almost all graph related functions can take a rule list. Commented Apr 1, 2017 at 19:57
• Attempting to work through this I wonder if the problem is underspecified, or if your example is poor. The two n=3 examples you give are supersets of {R5, R6}. Would not this family of cuts be R5, R6, and one of any of the other nodes beside TX and RX? Is that really what you want? Commented Apr 1, 2017 at 20:06
• just an observation, the same issue persists if we make this an undirected graph. FindVertexCut[g, TX, RX]->{R5, R6} however FindVertexCut[g, RX, TX] correctly gives {R5, R6, R9}. Clearly there is a bug here. Commented Jun 1, 2017 at 17:33

This question relate with my this question.The VertexConnectivity[edges,TX,RX] give a right answer,but FindVertexCut[edges, TX, RX] will not..

edges = {TX -> R1, R1 -> R3, R3 -> R5, R5 -> RX, TX -> R2, R2 -> R4,
R4 -> R6, R6 -> RX, R1 -> R2, R2 -> R3, R3 -> R4, R4 -> R5,
R5 -> R6, TX -> R7, TX -> R8, R7 -> R9, R9 -> R6, R9 -> RX,
R8 -> R6};


# Method one(violence but reliable)

This is a workaroud can find all vertex cut as its definition.Of course,this method based on Subsets,which mean it is very low efficiency.I hope it be refined by other user.

Find all vertex set except that start and end vertex

vertexSets = Rest[Subsets[Complement[VertexList[edges], {TX, RX}]]]


Find the vertex connectivity

vertexConn = Catch[Do[If[! WeaklyConnectedGraphQ[VertexDelete[Graph[edges], i]],
Throw[Length[i]]], {i, vertexSets}]]


3

Then you can select those vertex cut

Select[GroupBy[vertexSets, Length][vertexConn],
!WeaklyConnectedGraphQ[VertexDelete[Graph[edges], #]] &]


{{R5,R6,R7},{R5,R6,R9}}

# Method two(based on VertexConnectivity)

Of course,if you trust that function VertexConnectivity totally,there is a higher efficiency and more concise method

Select[Subsets[Complement[
VertexList[edges], {TX, RX}], {VertexConnectivity[edges, TX,
RX]}], ! WeaklyConnectedGraphQ[VertexDelete[edges, #]] &]


{{R5, R6, R7}, {R5, R6, R9}}

here is an approach that recursively drops vertices along the shortest path:

edges = {TX -> R1, R1 -> R3, R3 -> R5, R5 -> RX, TX -> R2, R2 -> R4,
R4 -> R6,
R6 -> RX, R1 -> R2, R2 -> R3, R3 -> R4, R4 -> R5, R5 -> R6,
TX -> R7, TX -> R8, R7 -> R9, R9 -> R6, R9 -> RX, R8 -> R6} ;
g = Graph[edges];
droppv[{g_Graph /; WeaklyConnectedGraphQ[g], dl_List}, a_, b_] :=
droppv[{VertexDelete[g, #], Append[dl, #]}, a, b] & /@
FindShortestPath[g, a, b][[2 ;; -2]]
SortBy[Sort /@
Cases[droppv[{g, {}}, TX, RX] ,
droppv[{ g_Graph , dl_}, _, _] :> dl , Infinity] // Union, Length]


this gives all unique sets of vertices to disconnect the graph:

{{R5, R6, R7}, {R5, R6, R9}, {R1, R2, R6, R7}, {R1, R2, R6, R9}, {R1, R2, R7, R8}, {R1, R2, R8, R9}, ... (54 sets)

pick the minimum length sets:

Select[%, Length[#] == Length[%[[1]]] &]


{{R5, R6, R7}, {R5, R6, R9}}

• ALL minimum flash my eyes, or maybe I have missed something.:)
– yode
Commented Jun 1, 2017 at 18:04
• ok, so pick the first two.. @yode Commented Jun 1, 2017 at 18:08
• Or MinimalBy[#, Length] &..
– yode
Commented Jun 1, 2017 at 18:31