Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Approximation Algorithms for Connected Maximum Cut and Related Problems
verfasst von : Mohammad Taghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi Sarpatwar
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\Omega(\frac{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.