Integer Linear Programs and Local Search for Max-Cut
Svatopluk Poljak · SIAM Journal on Computing · 1995
The paper deals with the complexity of the local search, a topic introduced by Johnson, Papadimitriou, and Yannakakis. One consequence of their work, and a recent paper by Schaffer and Yannakakis, is that the local search does not provide a polynomial-time algorithm for finding locally optimum solutions for several hard combinatorial optimization problems. This motivates us to seek “easier” instances for which the local search is polynomial. In particular, it has been proved recently by Schaffer and Yannakakis that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence belongs among the most difficult problems in the PLS class. The FLIP neighborhood of a 2-partition is defined by moving a single vertex to the opposite class. We prove that, when restricted to cubic graphs, the FLIP local search becomes “easy” and finds a local max-cut in $O(n^{2})$ steps. To prove the result, we introduce a class of integer linear programs associated with cubic graphs and provide a combinatorial characterization of their feasibility.