## 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].

Original language | English (US) |
---|---|

Title of host publication | 31st Annual European Symposium on Algorithms, ESA 2023 |

Editors | Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772952 |

DOIs | |

State | Published - Sep 2023 |

Externally published | Yes |

Event | 31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands Duration: Sep 4 2023 → Sep 6 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 274 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 31st Annual European Symposium on Algorithms, ESA 2023 |
---|---|

Country/Territory | Netherlands |

City | Amsterdam |

Period | 9/4/23 → 9/6/23 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- approximation algorithms
- graph theory
- local search
- max-cut