# Homework 6 Optional Problems

Prove that in graphs with positive integer edge weights, the local search algorithm for the maximum cut problem is not guaranteed to converge in a polynomial number of iterations.

**ANSWER:** See How Easy Is Local Search.