Approximation algorithms for connected maximum cut and related problems (Q6828271)

The paper obtains new results on the Connected Maximum Cut (CMC) problem, which is defined as follows: given an undirected graph \(G =(V , E)\), the goal is to find a subset of vertices \(S\subseteq V\) that maximizes the number of edges in the cut \(\delta(S)\) such that the induced graph \(G[S]\) is connected.\N\NThe principal results are:\N\N1. The first \(\Omega(\frac1{\log n})\) approximation algorithm for the CMC problem in general graphs. The authors employ a novel approach which is to look for \(\alpha\)-thick trees, which are basically sub-trees such that leaves of the tree have a large degree in the original graph.\N\N2. An \(\Omega(\frac1{\log^2 n})\) approximation algorithm for the Weighted Connected Maximum Cut problem. The basic idea here is to group the edges into a logarithmic number of weight classes and show that the problem on each weight class boils down to the special case where the weight of every edge is either 0 or 1.\N\N3. A polynomial-time approximation scheme for the unweighted CMC problem in planar graphs and more generally in bounded-genus graphs. This comes with the help of a stronger form of the edge contraction theorem by \textit{E. D. Demaine} et al. [in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. New York, NY: Association for Computing Machinery (ACM). 441--450 (2011; Zbl 1288.05256)].\N\N4. A proof that the CMC problem remains NP-hard even on unweighted, planar graphs. The proof constructs a polynomial-time reduction from a special case of 3-SAT, called the Planar Monotone 3-SAT (PM-3SAT), to the CMC problem in planar graphs.