Advertisement
Published in:
2016 | OriginalPaper | Chapter
Approximation and Hardness Results for the Max k-Uncut Problem
Authors : Peng Zhang, Chenchen Wu, Dachuan Xu, Xinghe Zhang
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we propose the \(\mathsf{Max}~k\text {-}\mathsf{Uncut}\) problem. Given an n-vertex undirected graph \(G = (V, E)\) with nonnegative weights \(\{w_e \mid e \in E\}\) defined on edges, and a positive integer k, the \(\mathsf{Max}~k\text {-}\mathsf{Uncut}\) problem asks to find a partition \(\{V_1, V_2, \cdots , V_k\}\) of V such that the total weight of edges that are not cut is maximized. This problem is just the complement of the classic \(\mathsf{Min}~k\text {-}\mathsf{Cut}\) problem. We get this problem from the study of complex networks. For \(\mathsf{Max}~k\text {-}\mathsf{Uncut}\), we present a randomized \((1-\frac{k}{n})^2\)-approximation algorithm, a greedy \((1-\frac{2(k-1)}{n})\)-approximation algorithm, and an \(\varOmega (\frac{1}{2} \alpha )\)-approximation algorithm by reducing it to \(\mathsf{Densest}~k\text {-}\mathsf{Subgraph}\), where \(\alpha \) is the approximation ratio for the \(\mathsf{Densest}~k\text {-}\mathsf{Subgraph}\) problem. More importantly, we show that \(\mathsf{Max}~k\text {-}\mathsf{Uncut}\) and \(\mathsf{Densest}~k\text {-}\mathsf{Subgraph}\) are in fact equivalent in approximability up to a factor of 2. We also prove a weak approximation hardness result for \(\mathsf{Max}~k\text {-}\mathsf{Uncut}\) under the assumption \(\text {P} \ne \text {NP}\).