Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph.

• A bicriteria approximation algorithm for Max k -Uncut with ratio at least 1/2. • A bicriteria approximation algorithm for Densest k -Subgraph with ratio at least 1/4. • A new perspective to the Densest k -Subgraph problem. The Max k -Uncut problem arose from the study of homophily of large-scale networks. 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 { V 1 , V 2 , ⋯ , V k } of V such that the total weight of edges that are not cut is maximized. This problem is the complement of the classic Min k -Cut problem, and was proved to have surprisingly rich connection to the Densest k -Subgraph problem. In this paper, we give an approximation algorithm for Max k -Uncut using a non-uniform approach combining LP-rounding and the greedy strategy. The algorithm partitions the vertices of G into at least (1 − 1 e) k parts in expectation, and achieves a good expected approximation ratio 1 2 (1 + (n − k n) 2). [ABSTRACT FROM AUTHOR]