# 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. – Mr.Wizard Apr 1 '17 at 19:55
• @Mr.Wizard Since v10.4 (I think) almost all graph related functions can take a rule list. – Szabolcs Apr 1 '17 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? – Mr.Wizard Apr 1 '17 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. – george2079 Jun 1 '17 at 17:33

## 2 Answers

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[%[]] &]


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

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