Approximating Node-Weighted Survivable Networks Zeev Nutov The Open University of Israel Talk Outline Problem Definition History and Our Results Greedy Algorithm for Node Weighted Steiner Trees Reducing NWSN to Finding Minimum Weight Edge-Cover of Uncrossable Set-Family Spider-Cover Decomposition of Edge-Covers of Uncrossable Set-Families Algorithm for Covering Uncrossable Set-Families Node-Weighted k-Flow is harder than Densest -Subgraph 2 Problem Definition

Survivable Network (SN) Instance: A graph G = (V,E), weight function w on edges/nodes, U V, and connectivity requirements r(u,v), u,v U. Objective: A minimum weight spanning subgraph J of G containing U so that J(u,v) r(u,v) for all u,v U J(u,v) = uv-edge-connectivity in J Approximability Edge-weights: 2-approximable [Jain, FOCS 98], APX-hard Node-weights: for r(u,v) {0,1} O(log n)-approximable, Set-Cover hard [Klein and Ravi, IPCO 93] 3 History and Our Results Edge-weights Year Node-weights 2 for r(u,v){0,1} [AKR] 1991 2rmax

[WGMV] 1993 2H(n) for r(u,v){0,1} 2H(rmax) [KR] [GGPSTW] 1994 1996 1.35H(n) for r(u,v){0,1}[GK] 2 [J] 1998 Theorem 1 What about node-weights and rmax =2? NWSN admits a rmax 3H(n)-approximation algorithm. Theorem 2 a polylogarithmic approximation for any r We do not have max -approximation for NWSN with |U|=2 implies But2 this is not our fault! 1/ -approximation for Densest -Subgraph.

4 Node Weighted Steiner Tree Instance: A graph G=(V,E), a set U V of terminals, weights w(v) for nodes in VU. Objective: Find a min-weight subtree T of G containing U. 4 a 1 5 b 2 d 3 v(I) = 0v(I) = 1 w(I)v(I) = 8w(I) =0 =7 w(I) = 5

c The node-weight w(I) of a partial solution I E: w(I) = w(V(I)) = the weight of endnodes of I The deficiency of a partial solution I: v(I) = # (components containing terminals in (V,I)) -1. 5 The Greedy Algorithm Initialize: I While (I) > 0 do: Find S E I so that IIF Return I. The Density Condition w S opt I I S I

Theorem: If is decreasing and w is subadditive then the greedy algorithm has approximation ratio H(()). Objective: Find in polynomial time an augmentation S that satisfies the density condition for small . w I opt I I S I 6 A Lesson in Zoology This is a spider: These are also spiders: In general, a spider is a tree on at least 2 nodes, which has at most one node of degree 3. 7 Spider Decomposition of Trees

Center The single node of degree 3. If there is no node of degree 3, any node can be a center. Leaves The non-center nodes of degree 1. Lemma: Every tree can be decomposed into node-disjoint spiders such that every leaf of the tree belongs to a unique spider. 1. Select a node v whose subtree is a spider. 2. Remove v and its sub-tree. 3. Remove the path from v to its closet ancestor of degree 3. 4. Repeat. 8 Finding the First Augmentation T = optimal tree; we may assume: terminals = leaves of T {Si} spider-decomposition of T. w T w S i The spiders are disjoint Si leaves Si / 2 T 2 Si By averaging, there is a spider Si such that:

w Si Si w T 2 T Finding a spider S (in fact, a Shortest Path Tree) of optimal density: For each node s in the graph 1. Sort the paths from s to terminals in increasing weight order. 2. Add the two lightest paths. 3. Add paths in increasing weight order, till reaching minimum density. Terminals: 23 Weight: 12 8 Density: 68 = 8/(2-1) 12/(3-1) 2 3

3 4 7 Terminals: 4 Weight: 19 Density: ~ 6.3=19/(4-1) 9 The Complete Algorithm The previous algorithm finds an augmentation obeying the Density Condition with =2 if the current partial cover is I = . Finding an augmentation with a general partial cover I: 1. Contract every connected component of (V,I) into a super-node; a super node is a super-terminal if it contains a terminal. 2. Find an augmentation in the new graph (the partial cover is now ). The approximation ratio of the algorithm is 2H(|U|). 10 Algorithm for NWSN

Instance: A graph G = (V,E), weight function w on the nodes, U V, and connectivity requirements r(u,v), u,v U. Objective: A minimum weight spanning subgraph J of G containing U so that J(u,v) r(u,v) for all u,v U. The algorithm has rmax iterations. In iteration k we find a 3H(n)-approximation for the problem: Given: A graph J=Jk-1 with J(u,v) min{r(u,v),k-1} for all u,v U Find: An edge set I with w(V(I)) minimum so that J+I(u,v) min{r(u,v),k} for all u,v U Hence after rmax iterations, a feasible solution of weight at most rmax 3H(n)opt is found. 11 Covers of Uncrossable Set-Families The augmentation problem we want to solve is a particular case of the following problem: Node-Weighted Set-Family Edge-Cover (NWSFC) Instance: A graph (V,E), node weights {w(v):v V}, and an uncrossable set-family on V. Objective: Find an -cover I E of minimum node-weight (edge e covers set X if e has exactly one endnode in X) is uncrossable if X,Y implies at least one of the following: Y

VY X Y, X Y or X X Y, Y X Note: The inclusion minimal members VX of are pairwise disjoint. 12 Spider-Covers of Uncrossable Set-Families () = (C) = (s,C) = (s,) = the family of inclusion minimal sets in (min-cores) sets in that contain a unique min-core C (cores)

{X (C) : s V-X} {(s,C) : C } s Definition: Let () and let sV. An edge set S is an (s,)-cover if: - S covers (s,C) for every C - if ={C} then no member of (C) contains s An (s,)-cover S is a spider-cover if it can be partitioned into (s,C)-covers {SC:C } so that the node sets {V(SC) s} are pairwise disjoint. s 13 Spider-Coves Decompositions Definition of a Spider-Cover Decomposition: A sub-partition S1,,Sq of a cover I is a spider cover decomposition of I if there exists a partition 1, ,q of () and centers s1,,sq V so that: - Each Si is an (si,i)-cover - The node sets V(Si) are pairwise disjoint.

Spider-Cover Decomposition Theorem: Any uncrossable family cover has a spider-cover decomposition. Proof: Later. 14 Covering Uncrossable Families Density Condition (for I=) = |()| = # (min-cores) (S) = decrease in the deficiency caused by adding S to the partial solution S is a spider with leaves: S is an (s,)-cover with ||=: w S opt S (S) /2 (tight for =2) (S) /3 (tight for =3)

The Spider-Cover IfLemma S is an (s,)-cover then (S) (||-1)/2 if || 2 (S) = 1 if || =1 Tight Example s v1 u0 v2 u2 u1 15 The Algorithm The Spider-Cover Lemma implies that there exists a spidercover that satisfies the Density Condition with =3. Such spider-cover can be found in polynomial time assuming we can compute in polynomial time: - The family () of min-cores (max-flows) - Minimum weight (s,C)-cover (min-cost k-flows) Thus the Greedy Algorithm can be implemented in polynomial

time with =3. Approximation ratio: 3H(()) = 3H(|()|) 3H(n) 16 The Spider-Cover Decomposition Thm Proof Sketch Notation uncrossable family (X,Y implies X Y, X Y or XY,YX) I an -cover (for any X there is eI with exactly one endnode in X) We may assume that I is an inclusion minimal -cover. Then for every eI there exists a witness set We , namely: e is the unique edge in I that covers We. A family = {We : e I} is called a witness family for I (every eI has a unique witness set in We ). Lemma: Let I be an inclusion minimal cover of an uncrossable family . Then there exists a witness family for I which is laminar. 17 The Spider-Cover Decomposition Thm Proof Sketch Assumptions: Every member of is a core Every minimal member (leaf) of is a min-core. For a min-core C() define: LC = the maximal set in containing C

eC = the unique edge in I covering LC, eC=sCvC, vC LC SC = edges in I contained in LC plus eC LC eC sC vC C 18 The Spider-Cover Decomposition Thm Proof Sketch Lemma: The sets {LC : C in ()} are pairwise disjoint. The sets {SC : C in ()} are pairwise disjoint. SC covers all cores contained in LC. Corollary: Any partition 1, , q of () induces a partition S1,,Sq of I. We seek a partition so that S1,,Sq is a spider-cover decomposition. - A natural partition of () is by the stars of {eC : C()}. - Every star with at least 2 edges indeed induces a spider-cover.

- This approach fails for 1-edge stars; SC is not a spider-cover if there is a dangerous set MC containing LC+sC LC eC sC vC eC C MC eC' LC 19 The Spider-Cover Decomposition Thm Proof Sketch How do we group dangerous cores?

- group some together, or - assign to non-dangerous stars. Observation: Every dangerous MC is covered by some edge eC . Grouping dangerous cores together: The relation ={(C,C) : MC MC } is an equivalence, and its classes of size 2 induce spider-covers (center any node in the intersection of MCs) Assigning singleton classes: Every singleton class {MC} of is assigned to the part of any edge eC covering MC . s eC' MC eC LC eC'

s eC MC LC 20 Reducing NWSN to bipartite DS Node-Weighted k-Flow (NW kF): r ( s, t ) k and r (u , v) 0 otherwise. Given an instance J A B, I , of bipartite DS, set w v 1, v A B add nodes s, t and edges sa : a A bt : b B of capacity each. -appr f or NWSN min X : X A B, I X k . 1 2 2 -appr f or D-S

max I X : X A B, X s 1. Run the -approximation algorithm f or min X : X A B, I X k , f or all k 1.. I . For every k we have a (possibly empty) set X k . A 2. Set X X k where k is the largest integer so that X min , A B and I X k .

I Note that I X opt DS . 3. Find X ' X with X so that 2 I X I X 2X B 2 2 1 IX I X .

2 2 2 2 t 21 Summary and Open Questions What did we do? Generalized the decomposition of a tree into spiders to covers of uncrossable families (looks easy after found) What do we get? E.g., an rmax3H(n)-approximation algorithm for NWSN. Any other applications? Probably YES. Open Question: Node-Weighted k-Flow (NWkF) is a special case of NWSN where r(s,t)=k and r(u,v)=0 otherwise. NWkF admits a k-approximation algorithm. Anything better, even for unit weights?

22