The Expander Hierarchy and its Applications to Dynamic Graph Algorithms Article Swipe

MAKE IMPACT

Gramoz Goranci , Harald Räcke , Thatchaphol Saranurak , Zihan Tan · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2005.02369

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with $n$ vertices undergoing edge insertions and deletions using $n^{o(1)}$ update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: (1) The first fully dynamic algorithm with $n^{o(1)}$ worst-case update time that allows querying $n^{o(1)}$-approximate conductance, $s$-$t$ maximum flows, and $s$-$t$ minimum cuts for any given $(s,t)$ in $O(\log^{1/6} n)$ time. Our results are deterministic and extend to multi-commodity cuts and flows. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by Räcke [FOCS'02] for constructing competitive oblivious routing schemes. (2) A deterministic fully dynamic connectivity algorithm with $n^{o(1)}$ worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al.~that uses the framework of Nanongkai et al. [FOCS'17]. (3) The first non-trivial deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with $n^{o(1)}$ worst-case update time that maintains a treewidth decomposition of width $\text{tw}(G)\cdot n^{o(1)}$ where $\text{tw}(G)$ denotes the treewidth of the current graph. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures the clustering structure of graphs. Given that the expander decomposition has proved extremely useful in many fields, we expect that our new notion will find more future applications.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2005.02369

PDF

https://arxiv.org/pdf/2005.02369

OA Status

green

Cited By

3

Related Works

10

OpenAlex ID

https://openalex.org/W3118169244

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3118169244

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2005.02369

Digital Object Identifier

Title

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-05-05

Full publication date if available

Authors

Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan

List of authors in order

Landing page

https://arxiv.org/abs/2005.02369

Publisher landing page

PDF URL

https://arxiv.org/pdf/2005.02369

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2005.02369

Direct OA link when available

Concepts

Treewidth, Tree decomposition, Hierarchy, Algorithm, Mathematics, Combinatorics, Graph, Expander graph, Computer science, Discrete mathematics, Pathwidth, Line graph, Market economy, Economics

Top concepts (fields/topics) attached by OpenAlex

Cited by

3

Total citation count in OpenAlex

Citations by year (recent)

2021: 3

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload