@inproceedings{cea0a4844a2b49cf96a905eea979eaae,

title = "Approximating Connected Maximum Cuts via Local Search",

abstract = "The Connected Max Cut (CMC) problem takes in an undirected graph G(V, E) and finds a subset S ⊆ V such that the induced subgraph G[S] is connected and the number of edges connecting vertices in S to vertices in V \ S is maximized. This problem is closely related to the Max Leaf Degree (MLD) problem. The input to the MLD problem is an undirected graph G(V, E) and the goal is to find a subtree of G that maximizes the degree (in G) of its leaves. [Gandhi et al. 2018] observed that an α-approximation for the MLD problem induces an O(α)-approximation for the CMC problem. We present an O(log log |V |)-approximation algorithm for the MLD problem via local search. This implies an O(log log |V |)-approximation algorithm for the CMC problem. Thus, improving (exponentially) the best known O(log |V |) approximation of the Connected Max Cut problem [Hajiaghayi et al. 2015].",

keywords = "approximation algorithms, graph theory, local search, max-cut",

author = "Baruch Schieber and Soroush Vahidi",

note = "Publisher Copyright: {\textcopyright} Baruch Schieber and Soroush Vahidi;; 31st Annual European Symposium on Algorithms, ESA 2023 ; Conference date: 04-09-2023 Through 06-09-2023",

year = "2023",

month = sep,

doi = "10.4230/LIPIcs.ESA.2023.93",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "{Li Gortz}, Inge and Martin Farach-Colton and Puglisi, {Simon J.} and Grzegorz Herman",

booktitle = "31st Annual European Symposium on Algorithms, ESA 2023",

address = "Germany",

}