Wouldn't it be interesting to have a PTAS for Maxcut on slightly less dense graphs, say graphs with average degree cn^{1/3}?
The dense graph PTAS is based on taking a small random sample S of the vertices, guessing which of those are on which side of the unknown optimal cut, and using the edges between S and the rest to place the other vertices somehow (several algorithms exist for the "somehow").
In less dense graphs, one might hope that many vertices of S, within distance 3 (if you take a random walk of length 3), reach Omega(n) vertices of the graph. So why not take into account S, not just from the perspective of adjacent vertices, but locally, within a limited neighborhood?
Approximating Max Cut even in graphs of average degree n^{0.99} is as hard as approximating in general graphs.
ReplyDeleteTake any graph, then replace every vertex by a group of n^{100} vertices and replace every edge (u,v) by a complete bipartite graph between the u-vertices and the v-vertices. The Max-Cut problem in this graph is exactly equivalent to Max-Cut in the original one (you can use randomized rounding to convert a solution in the new graph to a solution in the old graph), it has n^{101} vertices, and every vertex has degree at least n^{100}
You're right of course!
ReplyDelete