1
$\begingroup$

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. Max weight closure problem

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?

$\endgroup$
3
  • 1
    $\begingroup$ Isn't the maximum weight closure actually the empty set, which matches the (8+7) cut? $\endgroup$
    – Dmitry
    Aug 28, 2022 at 16:08
  • $\begingroup$ 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? $\endgroup$
    – rhodeo
    Aug 28, 2022 at 17:07
  • $\begingroup$ It should be right, if the empty set is allowed by definition. $\endgroup$
    – Dmitry
    Aug 28, 2022 at 21:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.