# Finding the minimum vertex cut of a graph

Bug introduced in 9.0.1 or earlier and fixed in 10.2.0
Note: FindVertexCut is new in 9.0.

It seems that Mathematica is not correctly finding the smallest set of vertices that will disconnect a graph. Here is an example:

 g = GraphData[{"Cycle", 5}]
FindVertexCut[g];
HighlightGraph[g, %]


results in vertices {3, 4} being removed. But removing two adjacent vertices of a cycle doesn't increase the number of components. If we remove 3 and 4, the graph is a tree and is still connected. This ends up happening with quite a few graphs, another example being the complete graph with 6 vertices. It only removes one vertex and doing so will obviously not disconnect the complete-6 graph. But it does work some of the time; e.g., with a 6-cycle, Mathematica removes two non-adjacent vertices.

Have I used FindVertexCut incorrectly? FindVertexCut with only a graph as its argument will result in "the smallest vertex cut of" my graph, and according to documentation, "A vertex cut of a graph g is a list of vertices whose deletion from g disconnects g." What's the problem here?

• Seems like a bug ... Works OK. for n > 5 – Dr. belisarius Oct 22 '14 at 12:26
• Your conjecture appears to only be true for cycles. From what I can see, it never works on complete graphs (except for n = 2 or n = 3). – Sultan of Swing Oct 22 '14 at 12:35
• Yup. I was talking about cycles. You're right about complete graphs too. – Dr. belisarius Oct 22 '14 at 12:37
• Other users: Please confirm and tag as bugs if you can repro – Dr. belisarius Oct 22 '14 at 12:39

## 2 Answers

This is bugged still in 10.1.

If you are forced to live with the buggy function, here's a brute-force method that should work correctly: it checks the size of a minimum cut, and tries all subsets of vertices of that size. Below, I assume that VertexConnectivity still works correctly.

g = CycleGraph[5, VertexLabels -> "Name"]

DisconnectedGraphQ[g_] := ! ConnectedGraphQ[g];
gh = VertexDelete[g, #] & /@ Subsets[VertexList[g], {VertexConnectivity[g]}];
cut = SelectFirst[gh, DisconnectedGraphQ, {}];
If[SameQ[{}, cut], VertexList[g], Complement[VertexList[g], VertexList[%]]]


Furthermore, the overloaded version FindVertexCut[g,s,t] is bugged. Consider the following:

g = Graph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 1 <-> 5, 2 <-> 3, 2 <-> 4,
2 <-> 5, 3 <-> 4, 3 <-> 5, 4 <-> 5, 1 <-> 8, 8 <-> 3},
VertexLabels -> "Name"];
HighlightGraph[g, FindVertexCut[g, 5, 8]]
Length[ConnectedComponents[VertexDelete[g, FindVertexCut[g, 5, 8]]]]


Here, removing the claimed vertex cut {1} does not increase the number of components, and is not a vertex separator for vertices 5 and 8.

Update: Now I recommend using IGraph/M instead:

<<IGraphM

IGMinSeparators[g]
(* {{2, 5}, {2, 4}, {3, 5}, {1, 3}, {1, 4}} *)


An alternative workaround is using igraph through my IGraphR package.

minimum.size.separators gives all possible smallest vertex cuts.

Example:

<< IGraphR

g = CycleGraph[5, VertexLabels -> "Name", VertexSize -> Large]

vcs = IGraph["minimum.size.separators"][g]
(* {{2., 5.}, {2., 4.}, {3., 5.}, {1., 3.}, {1., 4.}} *)

HighlightGraph[g, #] & /@ Round[vcs] • @mrm You can't compare them in general. There's of course an overhead to calling igraph, but igraph will sometimes use different algorithms which might make its performance significantly different. – Szabolcs Apr 9 '15 at 13:31
• Can you double check my claim for the st-version of FindVertexCut (see my update)? Thanks! :-) – Juho Apr 13 '15 at 13:27
• @mrm Sorry, today is very busy here. Remind me in a few days if I don't respond. – Szabolcs Apr 13 '15 at 17:05