 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/1/d/i/solution

Yes, for arbitrary signed weights. A hyperedge meets both

S

and

V ∖ S

exactly when it meets both

V ∖ S

and

S

. Therefore

δ (S) = δ (V ∖ S)

, and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.

 New to topics? Read the docs here!