License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.9
URN: urn:nbn:de:0030-drops-180619
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18061/
Go to the corresponding LIPIcs Volume Portal

Agassy, Daniel ; Dorfman, Dani ; Kaplan, Haim

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

pdf-format:
LIPIcs-ICALP-2023-9.pdf (0.8 MB)

Abstract

A (ϕ,ε)-expander decomposition of a graph G (with n vertices and m edges) is a partition of V into clusters V₁,…,V_k with conductance Φ(G[V_i]) ≥ ϕ, such that there are at most ε m inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized Õ(m/ϕ) time algorithm for computing a (ϕ, ϕlog²n)-expander decomposition. This improves upon the (ϕ, ϕlog³n)-expander decomposition also obtained in Õ(m/ϕ) time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal.
One crucial component of SW’s algorithm is a non-stop version of the cut-matching game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): The cut player does not stop when it gets from the matching player an unbalanced sparse cut, but continues to play on a trimmed part of the large side. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.

BibTeX - Entry

@InProceedings{agassy_et_al:LIPIcs.ICALP.2023.9,
  author =	{Agassy, Daniel and Dorfman, Dani and Kaplan, Haim},
  title =	{{Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18061},
  URN =		{urn:nbn:de:0030-drops-180619},
  doi =		{10.4230/LIPIcs.ICALP.2023.9},
  annote =	{Keywords: Exapander Decomposition, Cut-Matching Game}
}

Keywords: Exapander Decomposition, Cut-Matching Game
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI