Zhang, Peng 

Title: Max k-Uncut, Densest k-Subgraph, and Unique Games

Abstract: We propose the Max k-Uncut problem in the study of network homophyly. Given an n-vertex undirected graph G = (V, E) with nonnegative weights defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a partition {V1, V2, ..., Vk} of V such that the total weight of edges that are not cut is maximized. This problem is just the complement of the classic Min k-Cut problem. For Max k-Uncut (MkU), we present a randomized (1-k/n)2-approximation algorithm, a greedy (1-2(k-1)/n)-approximation algorithm, and an alpha/2-approximation algorithm by reducing it to Densest k-Subgraph (DkS), where alpha is the approximation ratio for the DkS problem. More importantly, we show that MkU and DkS are in fact equivalent in approximability up to a factor of 2. We also prove an approximation hardness result for MkU under the assumption P != NP.