TY - GEN

T1 - Approximation algorithms for connected maximum cut and related problems

AU - Hajiaghayi, Mohammad Taghi

AU - Kortsarz, Guy

AU - Macdavid, Robert

AU - Purohit, Manish

AU - Sarpatwar, Kanthi

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - 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 nontrivial (Formula presented) 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.

AB - 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 nontrivial (Formula presented) 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.

UR - http://www.scopus.com/inward/record.url?scp=84945552129&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945552129&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48350-3_58

DO - 10.1007/978-3-662-48350-3_58

M3 - Conference contribution

AN - SCOPUS:84945552129

SN - 9783662483497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 693

EP - 704

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

A2 - Bansal, Nikhil

A2 - Finocchi, Irene

PB - Springer Verlag

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -