Digraphs icon indicating copy to clipboard operation
Digraphs copied to clipboard

Implement `DigraphMinimumCutSet`

Open reiniscirpons opened this issue 5 months ago • 3 comments

Let $D$ be an edge weighted digraph and $s, t$ be two vertices. A cut-set with source $s$ and target $t$ is, in some sense, a set of edges whose removal disconnects $s$ from $t$ in $D$ (this is precisely the case when $D$ is a symmetric edge-weighted digraph). See the Cuts definition from Wikipedia https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Cuts for the full definition for a digraph. A minimum cut-set with source $s$ and target $t$ is a cut set whose sum of edge-weights is as small as possible.

It would be nice to have a function DigraphMinimumCutSet such that DigraphMinimumCutSet(D, s, t) returns the minimum cut set with source $s$ and target $t$ in the weighted digraph $D$. PR #584 contains some commented out code for for this, but I think we should be able to compute DigraphMinimumCutSet(D, s, t) from the flow computed by DigraphMaximumFlow(D, s, t) (in digraphs since PR #751) due to the max-flow min-cut theorem (see https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Proof for a proof and the rest of the article for the statement of equivalence between the minimum cut and maximum flow).

reiniscirpons avatar Oct 01 '25 15:10 reiniscirpons

I may look at this if no-one else is currently.

frankiegillis avatar Oct 29 '25 16:10 frankiegillis

Go for it! Let me know if you have any questions.

reiniscirpons avatar Oct 29 '25 22:10 reiniscirpons

@reiniscirpons I've opened a pull request with a possible implementation of this. Let me know what you think, and if any changes are necessary!

frankiegillis avatar Nov 02 '25 11:11 frankiegillis