An instance of the connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that t...
详细信息
An instance of the connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that the induced graph G[S] is connected. We present the first non-trivial Omega(1/log n) approximation algorithm for the connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论