4 ms·
There are a few misconceptions that some other commenters are already making. This min-cut is different from the max-flow min-cut theorem's min-cut. This is wh
by chaoxu 6y ago
There are a few misconceptions that some other commenters are already making.
This min-cut is different from the max-flow min-cut theorem's min-cut. This is what referred to as global min-cut, which does not fix the terminals. In max-flow min-cut theorem, it is about disconnecting two fixed vertices s and t. In the global min-cut, it is about disconnecting two arbitrary vertices.
Source: thesis was on hypergraph min-cut
- est31 6y agoSo the question is to find an arbitrary set of edges that partition the graph? In a K_n with equally weighted edges this problem seems easy: just take a random vertex and remove the edges connecting it to the neighbourhood. Any attempt at removing more vertices would yield in having to cut more edges, so the strategy removes the least amount of edges while partitioning the graph. In a tree with equally weighted edges, this problem seems easy too: just remove a leaf. Every tree has leaves. I can't think about graphs "between" the two creating a property that makes the the "I just take the vertex with the fewest adjacencies and remove it" strategy moot. Is it trivial with equally weighted edges? Is the problem only interesting when edges have differing weights?