Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

Given a graph G = (V, E), a weight function w: E → R⁺, and a parameter k, we consider the problem of finding a subset U ⊆ V of size k that maximizes: Max-Vertex Cover_k the weight of edges incident with vertices in U, Max-Dense Subgraph_k the weight of edges in the subgraph induced by U, Max-Cut_k the weight of edges cut by the partition (U, V \ U), Max-Uncut_k the weight of edges not cut by the partition (U, V \ U). For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80% of the edges.