2015/07/02 by Mohammad Taghi Hajiaghayi, MohammadTaghi Hajiaghayi, Hajiaghayi, MohammadTaghi +8
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.1507.00648
17 pages, Conference version to appear in ESA 2015
arxiv created 2015/07/02 · arxiv updated 2015/07/03
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 ⊆ V that maximizes the number of edges in the cut δ(S) such that the induced graph G[S] is connected. We present the first non-trivial Ω(1/log n) approximation algorithm for the connected maximum cut problem in general graphs using novel techniques. We then extend our algorithm to an edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in stark contrast to the classical max-cut problem, we show that the connected maximum cut problem remains NP-hard even 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 graphs with bounded genus.