INTEGER LINEAR-PROGRAMS AND LOCAL SEARCH FOR MAX-CUT

The paper deals with the complexity of the local search, a topic intro duced by Johnson, Papadimitriou, and Yannakakis. One consequence of th eir work, and a recent paper by Schaffer and Yannakakis, is that the l ocal search does not provide a polynomial-time algorithm for finding l ocally optimum solutions for several hard combinatorial optimization p roblems. 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 neig hborhood is polynomial-time local search (PLS) complete, and hence bel ongs among the most difficult problems in the PLS class. The FLIP neig hborhood of a 2-partition is defined by moving a single vertex to the opposite class. Wr prove that, when restricted to cubic graphs, the FL IP 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 pro grams associated with cubic graphs and provide a combinatorial charact erization of their feasibility.