Symmetric Demands and Directed Treewidth in Routing Studies

Routing Symmetric Demands and Directed Treewidth Chandra Chekuri Univ. of Illinois, Urbana-Champaign Joint work with Alina Ene (Boston) Marcin Pilipczuk (Warsaw)

s-t flow and cut difficult to compute directly min cut max integer flow max frac flow = = easy to compute

Multicommodity Flows/Cuts Several pairs (s1,t1), (s2,t2), , (sk,tk), k part of input NP-hard NP-hard Polytime via LP max integer flow max frac flow min multicut

Multicommodity Flows/Cuts Several pairs (s1,t1), (s2,t2), , (sk,tk) NP-hard NP-hard Polytime via LP max integer flow max frac flow min multicut Flow-cut gap theorems [LR88, GVY93, LLR95 ...] ??

Multicommodity Flows/Cuts Several pairs (s1,t1), (s2,t2), , (sk,tk) NP-hard NP-hard Polytime via LP max integer flow max frac flow min multicut Flow-cut gap theorems [LR88, GVY93, LLR95 ...] ?? graph theory

Maximum Throughput Routing Problems Undir graph G=(V,E) and k node-pairs s1t1, s2t2, ..., sktk MEDP: maximize # of input pairs that can be connected by edge-disjoint paths MNDP: maximize # of input pairs that can be connected by node-disjoint paths

Complexity MNDP/MEDP: NP-Complete if k is part of input [Knuth/Karp, Even-Itai-Shamir] Poly-time solvable (in fact FPT) if k is fixed [Robertson-Seymour] Questions: Can we approximate well? Gap between fractional flow and integer flow?

Integrality Gap for MEDP/MNDP tk tk-1 ti t3 t2 [GVY] (n1/2) gap t1 sk si s3 s2 s1 sk-1

Two Relaxations MNDP/MEDP with Congestion: Allow paths to use an edge/node c times for some small c. All-or-Nothing Flow (MANF): Allow pairs to route one unit of flow along any # of paths

Reduction to Graph Theory [C-Khanna-Shepherd 05] Well-linked-decomposition via flow-cut gap results Reduce problem at polylog(k) loss to answering: Question: If G has treewidth k, does it have a routing structure of large size?

Route many pairs to the grid Use grid as a switch to connect the pairs with one crossing (congestion 2)

Reduction to Graph Theory [C-Khanna-Shepherd 05] Well-linked-decomposition via flow-cut gap results Reduce problem at polylog(k) loss to answering: Question: If G has treewidth k, does it have a routing structure of size k/polylog(k)?

Answers to the Question Question: If G has treewidth k, does it have a routing structure of size k/polylog(k) ? Planar graphs: Via [Robertson-Seymour-Thomas] there is a grid-minor of size ck General graphs: Building on several tools and results, [Chuzhoy 11] showed that an expander of size k/polylog(k) can be embedded in G. Improved in [Chuzhoy-Li 12] to optimal congestion 2. [C-Ene 13,C- Chuzhoy 15] for node congestion.

Directed Graphs MNDP/MEDP: NP-Hard even for 2 pairs! [Fortune- Hopcroft-Wylie 80] MNDP/MEDP/MANF strongly intractable Flow-cut gap is min(k,n?)[Saks-Samordnitsky- Zosin,Chuzhoy-Khanna] Integrality gap and hardness of n?(1/c) even for congestion c [Chuzhoy-Guruswami-Khanna-Talwar]

Symmetric Demands Directed graph G=(V,E) and k unordered node-pairs s1t1, s2t2, ..., sktk siti is routed if path from si to tiand a path from ti to si

Motivation Practical: communication is symmetric in many settings despite network being asymmetric Mathematical/Algorithmic: Generalizes undirected problems Appears tractable: flow-cut gap is O(log k log log k) Connections to directed treewidth

(Directed) Treewidth and Well-linked Sets Treewidth is defined typically via tree decompositions Hard to define and understand in the directed setting but done in [Johnson-Robertson-Seymour- Thomas 01, Reed] For our purposes, easier to use well-linked sets which approximately characterize treewidth

Well-linked Sets A set X V is well-linked in G if for all A, B X there are min(|A|,|B|) node-disjoint A-B paths G

Well-linked Sets A set X V is well-linked in G if for all A, B X there are min(|A|,|B|) node-disjoint A-B paths G

Well-linked Sets: Directed Graphs A set X V is well-linked in G if for all A, B X there are min(|A|,|B|) node-disjoint A-B paths G

Well-linked Sets: Directed Graphs A set X V is well-linked in G if for all A, B X there are min(|A|,|B|) node-disjoint A-B paths G

Treewidth & Well-linked Sets wl(G) = cardinality of the largest well-linked set in G tw(G) = treewidth of G tw(G) ~ wl(G) (within constant factor)

Two Relaxations MNDP/MEDP with Congestion: Allow paths to use an edge/node c times for some small c. All-or-Nothing Flow (MANF): Allow pairs to route one unit of flow along any # of paths

All-or-Nothing Flow [C-Ene 14] Generalize well-linked-decomposition framework of [C-Khanna-Shepherd 05] via flow-cut gap results Theorem: polylog(k) approximation with constant congestion for MANF for symmetric demands in directed graphs

Reduction to Graph Theory [C-Ene 14] Generalize well-linked-decomposition framework of [C-Khanna-Shepherd 05] via flow-cut gap results Reduce problem at polylog(k) loss to answering: Question: If G has directed treewidth k, does it have a routing structure of large size?

Conjecture of JRST There exists f: such that if G has directed treewidth at least f(k) then G has a cylindrical grid of size k as a butterfly minor

Proofs of Conjecture [JRST 01] unpublished, for planar graphs [Kawarabayashi-Kreutzer 13] planar and minor-free graphs, some what different proof than [JRST 01] [Kawarabayashi-Kreutzer 15] for general graphs f(k) is very fast growing function

Weaker Structure [C-Ene-Pilipczuk 14] If G is planar and has directed treewidth k then there is a weak cylinder of size k/polylog(k)

Proof Sketch Follow the scheme from [JRST 01] Add some tools to improve bounds and obtain poly- time algorithm

Proof Outline Reduce to Eulerian graph with small degree Use undirected grid-minor theorem Show existence of many disjoint concentric directed cycles Connect inner cycle to outer cycle with many directed paths Connect outer cycle to inner cycle with many directed paths

Eulerian and Low Degree Given G=(V,E) with treewidth k Output a multi-graphH=(V,E ) such that H is Eulerian Support of E is E H has large treewidth Max degree in H is small [JRST 01] achieve above with constant degree for H but lose a lot in treewidth

Eulerian and Low Degree Given G=(V,E) with treewidth k Output a multi-graphH=(V,E ) such that H is Eulerian Support of E is E H has treewidth k/polylok(k) Max degree in H is O(log2 k) Tool: Use cut-matching game of [Khandekar-Rao- Vazirani] extended by [Louis] to directed graphs to embed an expander in G

Undirected Grid H directed Eulerian graph with small degree H undirected version of H tw(H ) is roughly dtw(H) implies H has a large wall

Concentric Cycles H has a large wall. Large flow from middle to outer face implies also large directed flow in H (Eulerian and small degree)

Concentric Cycles

Paths from inner cycle to outer and vice-versa

Open Problems Generalize to graphs embeddable in bounded genus surfaces General graphs? Treewidth decomposition is a simpler step which is already challenging. Improve Erdos-Posa bounds from [Reed-Robertson-Seymour-Thomas] For planar graphs can we get O(1) degree Eulerian graph that preserves treewidth to constant factor? Has applications to flow-cut gap and will improve weak cylinder size

Thank You!