ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 08 Jan 2023 02:56:46 +0100Find all minimal edge cuts of a graph.https://ask.sagemath.org/question/65504/find-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.
g="S~tIID@OI?{@n~V?goYEDOWd?qI?sJ?[C"
G = Graph(g, sparse=True);
![image description](/upfiles/16718860962466291.png)
How to find its all minimal edge cuts? I have searched Literature [1] for the corresponding polynomial algorithm (which you can view). But I don't see any code implementation. For the above graph (with 20 vertices), perhaps a violent search would be possible.
[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/BF01074775Sat, 24 Dec 2022 13:47:14 +0100https://ask.sagemath.org/question/65504/find-all-minimal-edge-cuts-of-a-graph/Comment by licheng for <p>An <em>edge cut</em> is a set of edges that, if removed from a connected graph, will disconnect the graph. </p>
<p>A <em>minimal edge cut</em> is an edge cut such that if any edge is put back in the graph, the graph will be reconnected. </p>
<p>A <em>minimum edge cut</em> is an edge cut such that there is no other edge cut containing fewer edges. </p>
<p><strong>Note that</strong> a minimum edge cut is always minimal, but a minimal edge cut is not always minimum. </p>
<pre><code>g="S~tIID@OI?{@n~V?goYEDOWd?qI?sJ?[C"
G = Graph(g, sparse=True);
</code></pre>
<p><img src="/upfiles/16718860962466291.png" alt="image description"></p>
<p>How to find its all minimal edge cuts? I have searched Literature [1] for the corresponding polynomial algorithm (which you can view). But I don't see any code implementation. For the above graph (with 20 vertices), perhaps a violent search would be possible. </p>
<p>[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). <a href="https://doi.org/10.1007/BF01074775">https://doi.org/10.1007/BF01074775</a></p>
https://ask.sagemath.org/question/65504/find-all-minimal-edge-cuts-of-a-graph/?comment=65813#post-id-65813@ David Coudert 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.
- [complexity-of-listing-all-minimal-cut-sets-connected-2-partitions-of-a-graph](https://cstheory.stackexchange.com/questions/39039/complexity-of-listing-all-minimal-cut-sets-connected-2-partitions-of-a-graph)
(I don't know how I became an anonymous in this question)Sun, 08 Jan 2023 02:56:46 +0100https://ask.sagemath.org/question/65504/find-all-minimal-edge-cuts-of-a-graph/?comment=65813#post-id-65813Comment by David Coudert for <p>An <em>edge cut</em> is a set of edges that, if removed from a connected graph, will disconnect the graph. </p>
<p>A <em>minimal edge cut</em> is an edge cut such that if any edge is put back in the graph, the graph will be reconnected. </p>
<p>A <em>minimum edge cut</em> is an edge cut such that there is no other edge cut containing fewer edges. </p>
<p><strong>Note that</strong> a minimum edge cut is always minimal, but a minimal edge cut is not always minimum. </p>
<pre><code>g="S~tIID@OI?{@n~V?goYEDOWd?qI?sJ?[C"
G = Graph(g, sparse=True);
</code></pre>
<p><img src="/upfiles/16718860962466291.png" alt="image description"></p>
<p>How to find its all minimal edge cuts? I have searched Literature [1] for the corresponding polynomial algorithm (which you can view). But I don't see any code implementation. For the above graph (with 20 vertices), perhaps a violent search would be possible. </p>
<p>[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). <a href="https://doi.org/10.1007/BF01074775">https://doi.org/10.1007/BF01074775</a></p>
https://ask.sagemath.org/question/65504/find-all-minimal-edge-cuts-of-a-graph/?comment=65569#post-id-65569You can certainly implement the algorithm described in the paper.Tue, 27 Dec 2022 12:21:12 +0100https://ask.sagemath.org/question/65504/find-all-minimal-edge-cuts-of-a-graph/?comment=65569#post-id-65569