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.


[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

  • $\begingroup$ @A.Vaicenavicius: in case it is useful for you, observe that the number of different values that the objective function of the heuristic can take determines its worst-case running time. In the unweighted case, the running time is polynomial because the objective function is bounded above by the number of edges of the graph. In the weighted case, in contrast, the objective function is bounded above by the total weight of the edges of the graph, and, therefore, it can have an exponential number of different possibilities. $\endgroup$ – Mario Cervera Feb 20 '17 at 16:40
  • $\begingroup$ @MarioCervera, that doesn't sound right to me, and I don't think it answers the question. The number of possible values that the objective function can take is an upper bound to the running time. However, I'm not aware of any proof that it is a lower bound, so showing that the objective function can take exponentially many values doesn't seem to necessarily imply that the running time will be exponential. Also, the question asks for a concrete example where this search procedure takes an exponential number of iterations. $\endgroup$ – D.W. Feb 20 '17 at 22:32
  • $\begingroup$ @D.W. I am also not aware of any lower bound proof, but I did hear (in a course by Stanford university) about local search with exponential behavior in practice in the maximum cut problem. I know my comment didn't answer the question (because it asks for a particular example, which I do not have), but I wanted to give the information just in case it was useful in any way. Should I delete the comment? $\endgroup$ – Mario Cervera Feb 21 '17 at 9:24
  • $\begingroup$ Thank you. I have added the references. @MarioCervera Yes, in the unweigted case we have that the problem in $\textsf{P}$-complete. In the weighted case, We know that the longest path is of exponential length as there is a chain of tight $\textsf{PLS}$-reductions from $\textsf{Circuit/Flip}$, which is $\textsf{PLS}$-complete. We can have an exponentially long path for $\textsf{Circuit/Flip}$ (which is complicated already) and as there is a chain of 2 tight reductions we have that $\textsf{Weighted Max-Sat}$ has an exponential local heuristics. tightness is essential here. $\endgroup$ – A. Vaicenavicius Feb 21 '17 at 10:45

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.