Approximation algorithms for connected maximum cut and related problems

Mohammad Taghi Hajiaghayi, Guy Kortsarz, Robert Macdavid, Manish Purohit, Kanthi Sarpatwar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
EditorsNikhil Bansal, Irene Finocchi
PublisherSpringer Verlag
Pages693-704
Number of pages12
ISBN (Print)9783662483497
DOIs
StatePublished - 2015
Event23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece
Duration: Sep 14 2015Sep 16 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9294
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other23rd European Symposium on Algorithms, ESA 2015
Country/TerritoryGreece
CityPatras
Period9/14/159/16/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms for connected maximum cut and related problems'. Together they form a unique fingerprint.

Cite this