DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.93

Approximating Connected Maximum Cuts via Local Search

Authors: Baruch Schieber and Soroush Vahidi

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

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 𝒪(α)-approximation for the CMC problem. We present an 𝒪(log log |V|)-approximation algorithm for the MLD problem via local search. This implies an 𝒪(log log |V|)-approximation algorithm for the CMC problem. Thus, improving (exponentially) the best known 𝒪(log |V|) approximation of the Connected Max Cut problem [Hajiaghayi et al. 2015].

Cite as

Baruch Schieber and Soroush Vahidi. Approximating Connected Maximum Cuts via Local Search. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 93:1-93:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schieber_et_al:LIPIcs.ESA.2023.93,
  author =	{Schieber, Baruch and Vahidi, Soroush},
  title =	{{Approximating Connected Maximum Cuts via Local Search}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{93:1--93:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.93},
  URN =		{urn:nbn:de:0030-drops-187466},
  doi =		{10.4230/LIPIcs.ESA.2023.93},
  annote =	{Keywords: approximation algorithms, graph theory, max-cut, local search}
}

Search Results

Documents authored by Vahidi, Soroush

Approximating Connected Maximum Cuts via Local Search

Abstract

Cite as

Thanks for your feedback!

Could not send message