IGraphM
IGraphM copied to clipboard
szhorvat
Add the ability to list all minimal edge cuts of a graph.
Add the ability to list all minimal edge cuts of a graph.
An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph. A minimal edge cut is an edge cut such that if any edge is put back in the graph, the graph will be reconnected. A minimum edge cut is an edge cut such that there is no other edge cut containing fewer edges. Note that a minimum edge cut is always minimal, but a minimal edge cut is not always minimum.
I see that IGFindMinimalCuts[g, s, t] can find all smallest-weight (i.e. minimum) edge cuts that disconnect vertex $t$ from vertex $s$. But what I'm looking for is all minimal edge cuts of a graph, and I did not see the corresponding function. (I don't yet know how a minimal edge cut of a graph is related to a minimal edge cut that disconnect some vertex to another vertex)
I have searched Literature [1] for the corresponding polynomial algorithm (which you can view). I have asked a similar question in mathematica stack and it also seems that there is no corresponding efficient code for finding all minimum edge cuts.
- https://mathematica.stackexchange.com/questions/274840/find-all-the-minimum-edge-cuts-of-a-graph
There appears to be more than one concern about this issue.
- https://stackoverflow.com/questions/70672763/how-to-retrieve-all-minimum-edge-cut-sets-in-networkx
References
- [1] Karzanov, A.V., Timofeev, E.A. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybern Syst Anal 22, 156–162 (1986). https://doi.org/10.1007/BF01074775
From the discussion below, it appears that there is no polynomial algorithm for finding all minimal cuts. I feel that I have misread Literature [1], or the result of Literature [1] itself is wrong.
- https://cstheory.stackexchange.com/questions/39039/complexity-of-listing-all-minimal-cut-sets-connected-2-partitions-of-a-graph
Can you please post this information at https://github.com/igraph/igraph/issues/2275? Let's continue the discussion there as the feature should probably be implemented in the core igraph library.
