In　this　paper,　we　propose　the　Max　k-Uncut　problem.　Given　an　n-vertex　undirected　graph　G　=　(V,E)　with　nonnegative　weights　{we|　e　∈　E}　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.　We　get　this　problem　from　the　study　of　complex　networks.　For　Max　k-Uncut,　we　present　a　randomized　(1　−　k/n　)2-approximation　algorithm,　a　greedy　(1　−　2(k−1)/　n　)-　approximation　algorithm,　and　an　Ω(　1/2α)-approximation　algorithm　by　reducing　it　to　Densest　k-Subgraph,　where　α　is　the　approximation　ratio　for　the　Densest　k-Subgraph　problem.　More　importantly,　we　show　that　Max　k-Uncut　and　Densest　k-Subgraph　are　in　fact　equivalent　in　approximability　up　to　a　factor　of　2.　We　also　prove　a　weak　approximation　hardness　result　for　Max　k-Uncut　under　the　assumption　P　≠　NP.　©　Springer　International　Publishing　AG　2016.