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

**URL:** <https://igraph.discourse.group/t/finding-all-cuts-or-all-st-cuts-in-non-decreasing-order/1083>\
**Category:** Development\
**Tags:** C, Python\
**Created:** [27 January 2022 02:50 UTC](https://igraph.discourse.group/t/finding-all-cuts-or-all-st-cuts-in-non-decreasing-order/1083 "2022-01-27T02:50:17Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![salterduke](https://avatars.discourse-cdn.com/v4/letter/s/eb9ed0/32.png) [@salterduke](https://igraph.discourse.group/u/salterduke)\
**Post date:** [27 January 2022 02:50 UTC](https://igraph.discourse.group/t/finding-all-cuts-or-all-st-cuts-in-non-decreasing-order/1083/1 "2022-01-27T02:50:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [27 January 2022 09:18 UTC](https://igraph.discourse.group/t/finding-all-cuts-or-all-st-cuts-in-non-decreasing-order/1083/2 "2022-01-27T09:18:03Z")

</div>

[Feel free to open a feature request on GitHub.](https://github.com/igraph/igraph/issues/new/choose) 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.