Mohammadtaghi Hajiaghayi, Rohit Khandekar, et al.
Theoretical Computer Science
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 Ω([Formula presented]) 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.
Mohammadtaghi Hajiaghayi, Rohit Khandekar, et al.
Theoretical Computer Science
Mohammad Taghi Hajiaghayi, Rohit Khandekar, et al.
SPAA 2011
Mohammad Taghi Hajiaghayi, Rohit Khandekar, et al.
Theory of Computing Systems
Rohit Khandekar, Guy Kortsarz, et al.
Theoretical Computer Science