Robustness of �Length-Constrained Expanders�Part 2

Outline

Local Cutmatch

Dynamic Routers

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Remarks

Moving Cuts

Outline

Local Cutmatch

Dynamic Router

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Cutmatch

Cutmatch from approx. length constrained maxflows

Local Cutmatch from local approx. LC-maxflows

Outline

Local Cutmatch

Dynamic Router

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Dynamic Routers

Each vertex can send/receive 1 unit

New vertices

Dynamic Routers initialization

​

​

​

Dynamic Routers edge deletions

Dynamic Routers matching insertions

​

​

​

Dynamic Routers constant batched updates

​

​

​

Outline

Local Cutmatch

Dynamic Router

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Dynamic LC Expander Decompositions

Strictly speaking, we maintain a weak LC-ED

but enough for applications e.g. distance oracles

Dynamic Certified LC-ED

​

​

​

​

​

​

Dynamic Certified LC-ED

Dynamic Certified LC-ED

router routing

unfold router paths

using embedding

Dynamic Certified LC-ED initialization

Dynamic Certified LC-ED recourse

Dynamic Certified LC-ED batched edge insertions

Dynamic Certified LC-ED batched edge deletions

Matching part reconnected to router

Unmatched part decomposed locally

Dynamic Certified LC-ED batched edge deletions

Matching part reconnected to router

Unmatched part decomposed locally

Dynamic Certified LC-ED batched edge deletions

Matching part reconnected to router

Unmatched part decomposed locally

Dynamic Certified LC-ED batched edge deletions

Matching part reconnected to router

Unmatched part decomposed locally

Dynamic Certified LC-ED batched edge deletions

Matching part reconnected to router

Unmatched part decomposed locally

Dynamic Certified LC-ED batched edge deletions

Dynamic Certified LC-ED �correctness of the batched edge deletions algo.

Outline

Local Cutmatch

Dynamic Router

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Vertex Sparsifier preserving bounded distances

Vertex Sparsifier preserving bounded distances

Vertex Sparsifier preserving bounded distances

Vertex Sparsifier preserving bounded distances

Dynamic Vertex Sparsifier recourse

Outline

Local Cutmatch

Dynamic Router

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Introduce Boundary Linkedness [GRST21]

called ED with density in our paper

Introduce Landmarks

A small technical issue…

handling edge deletions

New cut

New extended terminals

Raising weights of new terminals

Outline

Local Cutmatch

Dynamic Routers

Dynamic LC-Expander Decomposition

Dynamic Vertex Sparsifiers

Dynamic LC-Expander

Hierarchy

Dynamic LC-Expander Hierarchy Recourse

Dynamic low-step emulator

Dynamic Low-Step Emulators

Conclusion

Take away

• When solving pure distance problems in the dynamic setting, controlling the congestion will be helpful, since update time depends on congestion.
• When analysing dynamic algorithms, keep track of the recourse.

Thank you!