Finding all cuts (or all st cuts) in non-decreasing order

Development
,
1

Hi,

I’m wondering if there is a possibility of implementing the algorithm in the following paper, for finding all cuts in a graph as a whole in non-decreasing order (or all st cuts similarly):
Yeh, Li-Pu, Biing-Feng Wang, and Hsin-Hao Su. 2010. “Efficient Algorithms for the Problems of Enumerating Cuts by Non-Decreasing Weights.” Algorithmica. An International Journal in Computer Science 56 (3): 297–312.

I’m working on a program to find tangles in a graph, and these are based on edge cuts.

igraph currently includes a function to find all_st_cuts, or all_st_mincuts, based on Provan and Shier, 1996. But there doesn’t appear to be a function for finding all cuts or mincuts in the graph as a whole.

The number of mincuts in an undirected graph as a whole is O(n^2) , whereas the number of st_mincuts can be exponential, even in an undirected graph.

Obviously, the number of non-minimum cuts grows rapidly as the size increases, but there exist several algorithms for finding all cuts in non-decreasing order, such as the one in the paper cited above, so implementation could run only to a certain size.

I have created a rough implementation of such an algorithm based on an earlier paper, but the algorithm in the paper cited above is O(n) more efficient, and I am having trouble working out how to implement it.
The earlier paper:
Vazirani, Vijay V., and Mihalis Yannakakis. 1992. “Suboptimal Cuts: Their Enumeration, Weight and Number.” In Automata, Languages and Programming , 366–77. Springer Berlin Heidelberg.

Additionally, I only know really python, and am not the world’s most efficient programmer, so my implementation runs only for very small graphs.

Alternatively, does anyone knows of any existing efficient implementation or function for finding all cuts up to a certain (fairly small) size?

Thanks
Michal Salter-Duke

2

Feel free to open a feature request on GitHub. It will be helpful if you can write down all relevant details, such as: (1) a mathematically precise statement of what you need (2) references, including links (3) practical uses cases (yours, or other potential use cases) (4) comments on the algorithms, such as complexity, some assessment of implementation difficulty, a review of various approaches/papers, etc.

Realistically, it is very unlikely that anyone would have the time to start working on this non-trivial project soon. However, this is a reasonable feature request, and the first step towards implementing it is to file the issue with as many details as possible.