11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Seems like a bug ... Works OK. for n > 5 $\endgroup$ – Dr. belisarius Oct 22 '14 at 12:26
  • $\begingroup$ 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). $\endgroup$ – Sultan of Swing Oct 22 '14 at 12:35
  • $\begingroup$ Yup. I was talking about cycles. You're right about complete graphs too. $\endgroup$ – Dr. belisarius Oct 22 '14 at 12:37
  • 1
    $\begingroup$ Other users: Please confirm and tag as bugs if you can repro $\endgroup$ – Dr. belisarius Oct 22 '14 at 12:39
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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]

Mathematica graphics

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Szabolcs Apr 9 '15 at 13:31
  • $\begingroup$ Can you double check my claim for the st-version of FindVertexCut (see my update)? Thanks! :-) $\endgroup$ – Juho Apr 13 '15 at 13:27
  • $\begingroup$ @mrm Sorry, today is very busy here. Remind me in a few days if I don't respond. $\endgroup$ – Szabolcs Apr 13 '15 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.