Wishlist: List all minimal cuts in an undirected graph

[szhorvat]

I received a request from @lichengzhang1 for IGraph/M for a function that lists all minimal edge cuts in an undirected graph: https://github.com/szhorvat/IGraphM/issues/126 The below text is copied from the original request and edited to remove Mathematica-specific references.

---

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.

There are already functions for minimum s-t cuts, igraph_all_st_mincuts() and minimal s-t cuts, igraph_all_st_cuts(). (I don't yet know how a minimal edge cut of a graph is related to a minimum 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

[lichengzhang1]

From the discussion below, it appears that there is no polynomial algorithm for finding all minimal cuts. I feel that either I 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

So as for the complexity of the algorithm to find all the minimal cuts, I'm not sure yet. A similar question I put on Mapleprimes ( a maple language forum), Mapleprimes member dharr gave his solution, I think it is well although it could still be improved in the further.

• Minimal-Edge-Cuts-Of-A-Graph-Using-Fundamental