Exponential time local search heuristics for Weighted MAX-CUT-Flip I have read multiple times [Theorem 5.15, 1][End of page 2, 2] that local search heuristics for $\textsf{Weighted Max-Cut}$ with $\textsf{Flip}$ neighbourhood takes an exponential time in some cases.

In particular, the problem is as follows. Given a partition $(V1,V2)$, its neighbours are partitions which can be obtained by moving one vertex from $V1$ to $V2$, or from $V2$ to $V1$. Such neighbourhood is polynomial in size. At each step algorithm chooses the neighbour with highest value strictly greater than that of the current partition (o/w, it is locally optimal and so the algorithm terminates). 

I am asking for a weighted graph and an initial partition of the vertices such that the above local heuristics would need exponential number of iterations to get to a local optimum.

I have not seen a single concrete example. 

References

[1] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to
solve. SIAM J. Comput., 20(1):56–87, February 1991.

[2] Lecture notes: https://courses.engr.illinois.edu/cs598csc/sp2011/lectures/lecture_12.pdf
Check out the paper: On the Power of Nodes of Degree Four in the
Local Max-Cut Problem - Burkhard Monien and Tobias Tscheuschner.

In the paper they take a sub-graph of size 5 constructed from two types of vertices (they call them type-1 vertices and type-3 vertices). Then they build a graph from n sub-graphs concatenated, and show a specific initial start of the max-cut algorithm. In this initial start, there would be an exponential number of flips until the local optima would be obtained.