Skip to content

Implement DigraphMinimumCutSet #867

@reiniscirpons

Description

@reiniscirpons

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).

Metadata

Metadata

Assignees

No one assigned

    Labels

    difficulty: 1A label for feature requests of moderate difficultygood-second-issueA label for issues that are good second time contributorshelp wantedA label for issues or PRs where help is wantednew-featureA label for new features.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions