Approximation algorithms for connected maximum cut and related problems
Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
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.
This page was built for publication: Approximation algorithms for connected maximum cut and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828271)
