Sunday, January 16, 2011

Looking for a PTAS for Maxcut in less dense graphs

There is a PTAS for Maxcut on dense graphs, i.e. with average degree cn.

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?


  1. Approximating Max Cut even in graphs of average degree n^{0.99} is as hard as approximating in general graphs.

    Take 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}


Note: Only a member of this blog may post a comment.