# Finding maximum weight closure of a graph using min-cut

I am going through the book "Network Flows" by Ahuja et al. In chapter 19.2 "MAXIMUM WEIGHT CLOSURE OF A GRAPH", I find this example of turning a vertex-weighted (positive or negative) digraph into a flow network. The min-cut in the flow network is supposed to correspond to a max-weight closure in the original graph.

Here, the max weight closure is supposed to be 3, 4, 5 and the capacity of the corresponding cut in the flow network is (8+10). However, the min cut in the flow network is actually just s, with capacity (8+7), which does not correspond to any closure in the original graph. What am I missing?

• Isn't the maximum weight closure actually the empty set, which matches the (8+7) cut? Aug 28, 2022 at 16:08
• Great observation @Dmitry! That means the book is wrong about {3, 4, 5} being the max weight closure, and it should really just be {}. Doesn't this also suggest that the weight of the max weight closure can never be negative, as the weight of the empty set would always be greater than it? Aug 28, 2022 at 17:07
• It should be right, if the empty set is allowed by definition. Aug 28, 2022 at 21:07