Bernhard Haeupler�� (ADHD & Dyslexia – Let’s talk about Neurodiversity!!!)�

Institute in Sofia, Bulgaria �&�ETH Zurich�

together with��Thatchaphol Saranurak�&�Ellis Hershkowitz, Antti Ryoeskoe, Goran Zuzic, Jason Li, David Wajc�& �Yaowei Long, Mohsen Ghaffari, Zihan Tan, Harald Raecke, Jonas Huebotter, …

​

​

STOC 2024 Workshop on

​

Network Flows

Graph Decompositions�

​

​

Network Flows

Graph Decompositions�

​

​

• Undirected Graph
• Length & Capacities
• Find good flow paths

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

• Undirected Graph
• Length & Capacities
• Find good flow paths

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

• Undirected Graph
• Length & Capacities
• Find good flow paths

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

​

​

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

Network Flows

Graph Decompositions�(= cut into well-behaved sub-graphs)

Plan for this Talk:

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Hierarchical Graph Decomposition

20

Hierarchical Graph Decomposition

21

small fraction of edges

Hierarchical Graph Decomposition

22

Hierarchical Graph Decomposition

23

Hierarchical Graph Decomposition

24

25

Sparse Cuts & Flow-Cut Gap

Expander Decomposition

Hierarchical Expander Decomposition

30

Expander decomposition

Hierarchical Expander Decomposition

31

Expander decomposition

Hierarchical Expander Decomposition

32

Expander decomposition

Hierarchical Expander Decomposition

33

Hierarchical Expander Decomposition

34

Hierarchical Expander Decomposition

35

Hierarchical Expander Decomposition

36

Theorem [Oblivious Routing]:�For every graph, there exists distributions over flow paths for every two nodes such that oblivious routing any demand via these paths is competitive with an optimized routing.

Length-Constrained Sparse Cuts (& Flow-Cut Gap)

Length-Constrained Sparse Cuts (& Flow-Cut Gap)

LC-Expander Decompositions

Applications (Oblivious Routing & Shortcuts)

So Far

• Both Length and Congestion Graph Decompositions are Powerful Tools
• A Graph Decomposition for Jointly Length & Congestion is possible
• LC-Expanders are Well-Behaved Graphs for Length & Congestion
• LC-Expander =
• G is a good router for (h,s)-length flows
• Every neighborhood has a phi-hidden expander (power)
• every h-diameter neighborhood is phi-stable �(deleting |C| edges changes distances for at most |C|/phi nodes)
• With the right (LC-flow) prespective LC-Expanders operate very much like normal expanders and tools transfer, like, Expander Pruning, Expander Hierarchy, Expander Routing, Boundary-Linkedness, Cut-Matching Games, Hop-Sets…
• Sparse Moving Cuts circumvent large Flow-Cut Integrality Gaps and are crucial circumvent integrality/hardness barriers (LC, vertex capacities, directed graphs, …)

Directed Low-Step Emulator Conjecture/Hypothesis/Problem

Thank you!