The min-cut problem was in fact the last problem for Advent of Code 2023 [0]. Many algorithms were too big-brained for me, but I was able to find "A Simple Min-Cut Algorithm" [1] which was relatively easy to understand. It uses maximum adjacency search [2] to traverse the graph in descending order of the number of incident edges from each vertex to all previously visited vertices, possibly factoring in their weights; the last two visited vertices are then merged, and the cut separating the last vertex visited from the rest of the graph is stored.
The process repeats until all but two vertices have been merged; the smallest cut found in each iteration, by sum of weights of edges that need to be severed to separate the last vertex from the rest of the graph, induces a min-cut for the entire graph; since vertices have been merged together you will need to map from edges incident to the merged vertex back to edges incident to all vertices "contained" in that merged vertex.
The advantage of implementing maximum adjacency search is that it can also be used to traverse and count components of the resulting cut graph to verify it has indeed been partitioned in two.
Something like that anyway. It's been a little while.
The process repeats until all but two vertices have been merged; the smallest cut found in each iteration, by sum of weights of edges that need to be severed to separate the last vertex from the rest of the graph, induces a min-cut for the entire graph; since vertices have been merged together you will need to map from edges incident to the merged vertex back to edges incident to all vertices "contained" in that merged vertex.
The advantage of implementing maximum adjacency search is that it can also be used to traverse and count components of the resulting cut graph to verify it has indeed been partitioned in two.
Something like that anyway. It's been a little while.
[0] https://adventofcode.com/2023/day/25
[1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...
[2] https://dl.acm.org/doi/pdf/10.5555/313559.313872