Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs Jarosl aw Byrka1, Mateusz Lewandowski1, Carsten Moldenhauer2 6 1 1 Universityof Wroc law, Poland 0 2 EPFL, Lausanne, Switzerland 2 n a Abstract. We study the prize-collecting version of the Node-weighted J SteinerTreeproblem(NWPCST)restrictedtoplanargraphs.Wegivea 1 newprimal-dualLagrangian-multiplier-preserving(LMP)3-approximation 1 algorithmforplanarNWPCST.Wethenshowa(2.88+ǫ)-approximation which establishes a new best approximation guarantee for planar NW- ] PCST. This is done by combining our LMP algorithm with a threshold S rounding technique and utilizing the 2.4-approximation of Berman and D Yaroslavtsev[3]fortheversionwithoutpenalties.Wealsogiveaprimal- . dual4-approximationalgorithmforthemoregeneralforestversionusing s c techniquesintroduced by Hajiaghay and Jain [18]. [ 1 1 Introduction v 1 In Steiner problems we aim at connecting certain specified vertices (called ter- 8 minals) by buying edges or nodes of the given graph. The classic edge-weighted 4 setting is well known to have many applications in areas like electronic circuits, 2 0 computernetworking,andtelecommunication.Theexpressivepowerofthenode . weighted variants is used to model various settings common to bioinformatics 1 0 [11], maintenance of electric power networks [17], and computational sustain- 6 ability [10]. 1 The node weighted setting is a generalization of the edge weighted case. In : v particular, one may cast the Set Cover problem as an instance of the Node- i weighted Steiner Tree problem, which proves hardness of approximation of the X general node-weighted setting. In this paper we study a natural special case, r a namely planar graphs, for which constant factor approximation algorithms are possible. In the prize-collecting (penalty-avoiding) setting we are given an option not tosatisfya certainconnectivityrequirement,buttopayafixedpenaltyinstead. The main focus of this work is to develop efficient primal-dual approximation algorithms for prize-collecting versions of the node-weighted Steiner problems. 1.1 Previous work The Steiner Tree problem is NP-hard even in planar graphs [13]. The most studied is the standard Edge-weighted Steiner Tree, for which the best known approximation ratio 1.39 is obtained via a randomized iterative rounding tech- nique[7].Bycontrast,thebestapproximationalgorithmsforSteinerForesthave the so far unbreakable ratio of 2 [1,19]. For the Prize-collecting Steiner Tree problem there exists a primal-dual 2- approximationalgorithm[16].ItcanbeshownthatitisalsoLagrangian-preserving. This property was used by Archer et al. to design the currently best 2−ǫ ap- proximation algorithm for PCST [2]. For the Prize-collecting Steiner Forest problem there is a 3 approximation primal-dualalgorithm[18],whichintroducesageneraltechniquetohandleprize- collecting problems. In the same paper the authors use a threshold rounding technique with randomized analysis to obtain ≈2.54 approximation. There are optimal (up to a constant factor) algorithms for node-weighted Steinerproblems.OneexampleistherecentO(lnn)approximationalgorithmfor NWPCSFbyBatenietal[6].K¨onemannetal[9]gaveaLangrangian-multiplier- preserving(LMP)approximationthatachievesthesameguarantee.Establishing theLMPpropertyisofcrucialimportancefortheconstructionofapproximation algorithms for quota and budgeted versions of the NWST problem. Planarityhelpssignificantlyinbothedgeandnodeweightedsetting.BothST andSFadmitPTASinplanargraphs[5].PlanarPCSTcanbealsoapproximated with any constant, but PCSF is APX-HARD already in planar graphs [4]. Planarityallowsforconstantfactorapproximationsfornode-weightedSteiner problems. The NWSF can be expressed as the Hitting Set problem for some uncrossing family of cycles and hence solved as a feedback problem. This was exploited by Berman and Yaroslavtsev in [3] where they obtained 2.4 approxi- mation for NWSF and other problems on planar graphs. In [21] it was observed that using a threshold rounding technique together withthe2.4-approximationofBermanandYaroslavtsev[3]fortheversionwith- out penalties gives a 2.93-approximation algorithm for NWPCST on planar graphs. This was the best approximation guarantee up to date. However, such an algorithm requires solving an LP. We summarize the current best known results in Table 1. Edge-weighted Node-weighted Tree Forest Tree Forest General 1.39 [7] 2 [16] O(log k) [6] O(log k) [6] Planar PTAS [5] PTAS [5] 2.4 [3] 2.4 [3] 3 General 2−ǫ[2] O(log k) [6,9] O(log k) [6] 2.54 (LP) [18] Prize-collecting 3 Planar PTAS [4]APX-HARD[4] 4 2.87+ǫ (LP) Table 1. Summary of best known approximation ratios for Steiner problems. Results of this paper are highlighted. 2 1.2 Our contribution We propose a new LMP 3-approximation algorithm for NWPCST on planar graphs. The algorithm is an adaptation of the original technique developed by Goemans and Williamson in [16] for PCST to the node-weighted version. How- ever, we change the pruning phase of the algorithm. This enables us to analyze the connection and penalty costs separately which is the key ingredient. In par- ticular, we can directly charge the penalty costs to a part of the dual solution yielding Langrangian-multiplier-preservation.Further, the connection costs can be boundedusing a slightly adaptedanalysisfrom[20]for NWSF. The approxi- mationratioof 3 is slightly higherthan the previouslybest approximationratio but the primal-dual algorithm does not require solving an LP. Next, we establish a new best approximation ratio by exploiting the asym- metry of our primal-dual algorithm. Binding two different linear programs to- getherpermitsacarefulcombinationofthenewLMPalgorithmwithathreshold roundingtechnique.Finally,exploitingthe2.4-approximationfrom[3]weobtain a (2.88 + ǫ)-approximationfor NWPCST on planar graphs. Furthermore, we obtain an efficient, direct primal-dual 4-approximation al- gorithm for NWPCSF on planar graphs building up on ideas for edge-weighted PCSFfrom[18].WedeferthedetailsofthisresulttoAppendixB.Thisapproach was previously indicated by Demaine et al. [8], but we give a better constant. 2 The LMP primal-dual 3-approximation algorithm Consider an undirected graph G = (V,E) with non-negative cost function and penalties onthe verticesdenotedby w:V →Q andπ :V →Q , respectively. + + In the NWPCST problem we are allowed to purchase a connected subgraph F of G that connects vertices to a prespecified root r ∈ V. Every bought vertex inducesacostaccordingtow.Everyvertexthatisnotincludedinducesapenalty accordingtoπ.Theobjectiveistominimizethesumofthepurchaseandpenalty costs, i.e., w + π . v∈F v v∈/F v By a standard transformation we can assume that for every vertex v either P P its cost or its penalty is zero. To see this consider a single vertex v with both strictly positive cost and penalty. Add an additional vertex v′, set its cost to zero and penalty to π , add an edge from v′ to v and set the penalty of v to v zero. Now, any solution in the original graph can be transformed to a solution of the same cost in the modified graph and vice-versa. In the sequel, we call a vertex with a positive penalty a terminal. Terminals andtherootcanbepurchasedforfree.Otherverticesdonothaveapenaltyand we call them non-terminals or Steiner vertices. Let Γ(S) denote the set of neighbors of S, i.e., the set of vertices in V \S incidentto verticesfromS ⊆V.LetalsoΠ(X)= π .Thus,NWPCST is v∈X v P 3 the following problem: min w x + Π(X)z (IP ) v v X PCST vX∈V X⊆XV\{r} s.t. x + z ≥1 ∀S ⊆V \{r} v X v∈XΓ(S) XX:S⊆X x ∈{0,1} ∀v ∈V v z ∈{0,1} ∀X ⊆V \{r} X By relaxing the integrality constraints to non-negativity constraints we ob- tain the standard linear relaxation. The dual of this relaxation is max y (DLP ) S PCST S⊆XV\{r} s.t. y ≤w ∀v ∈V (1) S v S:vX∈Γ(S) y ≤Π(X) ∀X ⊆V \{r} (2) S S⊆X X y ≥0 ∀S ⊆V \{r} S 2.1 Algorithm Now we shortly describe our primal-dual algorithm which is an adaptation of the generic moat-growing approach of Goemans and Williamson [16]. In each iteration i we maintain a set of already bought nodes F. We say that some vertex was bought at time i if it was bought in iteration i 3. At the beginning F contains allterminals (including root).We maintainalso the set ofconnected components C of subgraph G[F] induced by the vertices bought so far. We call each of this connected components a moat. Moats can be active or inactive. The moat containing root r is always inactive. In each iteration we increase (grow) dual variables corresponding to all active moats uniformly until one of the following two events happen: – a vertex v goes tight (constraint (1) becomes equality), or – a set X goes tight (constraint (2) becomes equality). In the first case we buy vertex v and possibly merge moats incident to v. If we merge to a moat containing the rootr, this moat becomes inactive, otherwise it is declared active. 3 Whenwe refertotimewe alwayshavein mindthenumberof thecurrent iteration. Note that it implies that the speed of the uniform growth of dual budgets is not constant across iterations, but it does not affect ourdescription of thealgorithm. 4 In the second event we make the moat corresponding to set X inactive. Moreover,we mark all unmarked terminals inside X with the current time. The growth phase terminates when there are no more active moats. After that, we have a pruning phase. In the pruning phase we let F(r) be the con- nected component of F containing the root. Then, we consider vertices in F(r) in the reverseorder ofpurchase.We delete vertex v (bought attime t) if it does not disconnect from r any terminal which was unmarked at time t. When we delete v,wedelete alsoallverticesthatbecomedisconnectedfromr.Asaresult we output the set of bought vertices F′ that survived pruning. Ouralgorithmcanbe implemented with a notionof so-calledpotentials. Let P(X)=Π(X)− y be the potentialof set X. Intuitively, we pay for the S⊆X S growth of moats (increase of dual variables) with potentials of these moats. If P thepotentialofamoatgoestozero,thecorrespondingconstraintbecomestight, so we have to make this moat inactive.When we merge moats to a new moat S by buying a vertex, we compute the potential of S as the sum of potentials of old moats. 2.2 Analysis Theorem 1. (Lagrangian multiplier preservation) Let G be planar. The algo- rithm described in the previous section outputs a set of vertices F′ such that w +3Π(V \F′)≤3 y ≤3 OPT v S vX∈F′ S⊆XV\{r} In the proof we want to use the obtained dual solution y to account for the connection costs and penalties of the primal solution F′. We will partition the y intotwosets.Thefirstsetwillyieldaboundontheconnectioncostsandthe S second a bound on the penalties. Thekeyingredientintheanalysisisthepartitionthatisbasedonthefollow- inglemma.ConsideranyiterationiandtheactivemoatsA beforethisiteration. i Let S ∈ A be an active moat that was not included in the final solution, i.e., i S∩F′ = ∅. Then, the dual variable of S did not contribute to buying any ver- tex in F′. This means that y does not contribute to the left-hand-side of the S constraints (1) for any v ∈ F′. More formally, this means that S does not have a neighbor in F′. Lemma 2. Let S ∈ A be such that S ⊆ V \F′. Then, the moat S does not i have any neighbor in the solution, i.e. F′∩Γ(S)=∅ Proof (of Lemma 2). Note that S ∈A means that S is active in iteration i and therefore there is an i unmarked (before time i) terminal in S. Now, assume for a contradiction that F′∩Γ(S)6=∅andletU ⊆S bethesetofverticeshavinganeighborinF′.Note that all vertices in U were bought before iteration i because S is a connected component of the vertices bought before iteration i and U ⊆ S. Since S is not 5 part of F′, all the vertices in U must have been deleted in the pruning phase. A contradiction,sincethiswoulddisconnecttheunmarked(beforetimei)terminal in S. ⊓⊔ FollowingLemma2,wecanpartitionalldualvariablesintothevariablesthat contributed to buying the vertices of F′ and the dual variables that account for the penalties induced by F′. Let CC be the set of all moats S ⊆ V \{r} that include a vertex of F′ or have a neighbor in F′, i.e., (S ∪Γ(S))∩F′ 6= ∅ and y > 0. Let PC be the set of all other moats, i.e., sets S with y > 0 but S S S 6∈CC. We will show that w ≤3 y and Π(V \F′)= y v S S v∈F′ S∈CC S∈PC X X X which yields Theorem 1. To showthe boundonthe connectioncostwe performthe followingthought experiment. Consider the subgraph G′ of G obtained by restricting to vertices from V′ = V \(∪ S), i.e., restricted to only the root and vertices in the S∈PC moats in CC that contribute to the connection costs. Lemma 2 implies that thereisnoedgesbetweenmoatsinPC andV′.Recallthatineachiteration,the algorithm increases all active moats. Hence, the run of the algorithm restricted to G′ is exactly the same as running the algorithm directly on G′. Formally, let (H,y′) be the primal and dual solution obtained by running the algorithm on G′. Then, H =F′∩V′ and y′ =y|S⊆V′. Now, we can leverage the analysis of the primal-dual algorithm for Node- weighted Steiner Forest given in [20]. Recall that a terminal is a vertex with strictly positive penalty. Let T be the set of terminals that are in any moat of CC. Note that all vertices in T are connected to the root since the moats in CC were not disconnected in the pruning phase. However, the execution of our algorithmonG′ isnot thesameasrunningtheprimal-dualalgorithmforSteiner Forest on G′ with terminal pairs (r,t) (t ∈ T). This is because our algorithm is allowed to deactivate moats due to the penalty constraints. But, the analysis of an iteration of both algorithms is essentially analog. Intuitively, deactivating a moat compares to satisfying a demand pair in the Forest problem. The proof of the following lemma only requires a minor change to the analysis and we therefore defer it to Appendix A. Notethatthecrucialpointisthatweincreasethedualvariablesofall active moats.ThisguaranteesthatthealgorithmrunoninputsubgraphG′ isthesame as the run on input G with restricted view on G′. Choosing just a subset of the active moats can break this property since in each iteration we do not know in advance which moats will be pruned during the pruning phase. Therefore, it is not straight forward to include the advanced violation oracles from [3] that select only a subset of the active moats for increase. 6 Lemma 3 (analog of analysis in [20]). Let F′ be the output of the algorithm and A be the set of active moats before running iteration i. Then, i |F′∩Γ(S)|≤3|A ∩CC|. i S∈AXi∩CC Toconcludetheupperboundontheconnectioncosts,notethatconstraint(1) is tight for all vertices v ∈F′. This gives w = y = |F′∩Γ(S)| y = |F′∩Γ(S)| y . v S S S vX∈F′ vX∈F′S:vX∈Γ(S) S⊆XV\{r} SX∈CC We will show that |F′∩Γ(S)| y ≤ 3 y by induction on the S∈CC S S∈CC S number of iterations. At the beginning all dual variables are equal to 0 and the P P inequality holds. In iteration i we grow each active moat from A ∩CC by ǫ . i i Thisincreasestheleft-handsidebyǫ |F′∩Γ(S)|andtheright-hand i S∈Ai∩CC side by 3ǫ |A ∩CC|. Then, Lemma 3 concludes the proof of the bound on the i i P connection costs. Inordertoprovetheboundonthepenaltiesweemploythefollowinglemma. Lemma 4. Let F′ and y be the primal and dual solution constructed by the S algorithm. The set of vertices X =V \F′ not spanned by the final solution can bepartitioned intosets X ,X ,...X suchthat thepotential ofeach set is 0,i.e., 1 2 l P(X )=0 for each k. k Proof. Observe that there are two ways for a vertex v to be in X: either it was neverapartoftherootcomponent(v ∈V\F(r))oritwasdeletedinthepruning phase (v ∈F(r)). It is easy to see that P(V \F(r))=0. Eachvertex in V \F(r) was at the end a part of some inactive component not containing the root and hence the potentials of these components were 0. Or, it was never in any moat. ItremainstoshowthatthesetS ofverticesdisconnectedfromF′ bypruning a vertex v can be partitioned into sets X for which P(X ) = 0. Let t be the k k timewhenv wasbought.ObservethateveryvertexuintheneighborhoodΓ(S) ofS hasbeenboughtaftertimetorwasnotboughtatall.Now,S containsonly marked terminals at time t, otherwise v would not have been pruned. Hence, S is a union of inactive moats at time t. This gives the desired partition. ⊓⊔ Observe that the sets X are disjoint from CC and that PC is the set of all i S ⊆X with y >0. To conclude the bound on the penalties note that since all i S X have zero potential we have k l l Π(V \F′)= Π(X )= y = y . k S S Xk=1 Xk=1SX⊆Xk SX∈PC 7 3 Combination with threshold rounding A standard technique to generalize primal-dual algorithms from Steiner Tree problems to their price-collecting variations is to use threshold rounding (see Section 5.7 of [23] or [14]). Here, in a first step an LP formulation for the price- collectingversionissolvedoverfractionalvariables.Then,wepickathresholdα andconsidertheverticesthatareboughtwithvalueatleastαtobeterminals.In asecondstep,theprimal-dualalgorithmforthe originalSteinerTreeproblemis runonthissetofterminalstoobtainthefinalsolution.Wenotethattheresulting algorithm is deterministic because we can try all possible thresholds (at most one for every vertex). However,the analysis uses a randomization argument. We observed in [21] that using threshold rounding in combination with the primal-dual2.4-approximationforNode-weightedSteinerForestbyBermanand Yaroslavtsev [3] yields a 2.93-approximationfor NWPCST on planar graphs. In this section, we combine the previous LMP algorithm with the threshold rounding technique to gain an improved approximation factor of 2.88. Our ap- proachis inspiredby anidea ofGoemans [15]. Intuitively,such animprovement is possible because the LMP approximation improves over the factor of 3 if the optimal solution induces a high penalty cost. In contrast, if the penalties are only asmallpartofthe optimalsolution’scost,thresholdrounding canleverage therobustnessoftheunderlying2.4-approximation.Thus,bycombiningthetwo algorithms we can hedge their weaknesses. However, there is a technical difficulty. Applying threshold rounding to the LP that was used for the analysis of the LMP 3-approximation (LP below) a is not straight forward. We circumvent this problem by considering a stronger LP (see LP below) that is suitable for threshold rounding. To link the two b different formulations we will guess the cost of the optimal solution to LP a and restrict LP to have a similar objective value. More precisely, we will solve b multiple versions of LP (see LPk below) and then apply threshold rounding b b to gain a solution. To obtain the final solution, we simply take the best of all solutions stemming from LPk and the LMP 3-approximation. We remark that b the resulting algorithm is deterministic. However, for the analysis, we will use a randomized argument to combine the bounds of all solutions and gain an approximation factor of 2.88. 3.1 Two Linear Programs ConsidertheLPusedintheconstructionoftheprimal-dualLMP3-approximation which we denote by LP . a min w x + Π(X)z (LP ) v v X a vX∈V X⊆XV\{r} s.t. x + z ≥1 ∀S ⊆V \{r} v X v∈XΓ(S) XX:S⊆X x ≥0 ∀v ∈V z ≥0 ∀X ⊆V \{r} v X 8 Let further LP be the following LP that lends itself to threshold rounding b min w x + π y (LP ) v v u u b vX∈V u∈XV\{r} s.t. x +y ≥1 ∀S ⊆V \{r}, u∈S v u v∈XΓ(S) x ≥0 ∀v ∈V y ≥0 ∀u∈V v u While we do not know how to solve LP we can solve LP to optimality using, a b e.g.,theellipsoidmethod.Weremarkthatthealgorithmwhichwillbedescribed inthe sequelonly requirestosolvemultiple instancesofa variationofLP . LP b a is solely used in the analysis to combine the threshold rounding with the LMP 3-approximation. Fact 5. LP is stronger than LP , i.e., every feasible solution to LP is also a b a feasible to LP . b Proof. Let (x,z) be feasible to LP . Set y = z . We claim that (x,y) a u X:u∈X X is feasible to LP . Consider any S ⊆V \{r} and u∈S. We have b P y = z ≥ z u X X X:u∈X X:S⊆X X X Moreover,theobjectivevaluesof(x,z)and(x,y)intheirrespectiveformulations are equal π y = π z = π z = Π(X)z . u u u X u X X uX∈V uX∈V XX:u∈X X⊆XV\{r}uX∈X X⊆XV\{r} ⊓⊔ 3.2 Threshold rounding We will first describe how to link the two different LP formulations and then apply threshold rounding. In the sequel, let (x∗,z∗) be the optimum solution to LP with objective value OPT . Further, if T is a solution to NWPCST, let a a w(T) be the total connection and π(V \T) be the total penalties of T. We also use this notation for (fractional) solutions: w(x), π(z) and π(y). Binding the two LPs. For comparison with the LMP 3-approximation we require a bound on the thresholdrounding solution with respect to (x∗,z∗), the optimal solution to LP , which requires to link LP and LP . This is done by a a b guessing the value of w(x∗) and restricting LP to find a solution (x#,y#) with b 9 objective function value close to w(x∗). For given k consider LPk defined as b min w x + π y (LPk) v v u u b vX∈V u∈XV\{r} s.t. x +y ≥1 ∀S ⊆V \{r}, u∈S v u v∈XΓ(S) w x ∈ (1+ǫ)k,(1+ǫ)k+1 ∀S ⊆V \{r} v v v∈XΓ(S) (cid:2) (cid:1) x ≥0 ∀v ∈V y ≥0 ∀u∈V v u Note that the number of different k which we need to consider is bounded by a polynomial in the size of the input. Therefore, assume that k is set such that w(x∗) ∈ (1+ǫ)k,(1+ǫ)k+1 . Let further (x#,y#) be the optimal solution to LPk+1. b (cid:2) (cid:1) Fact 6. w(x#)≤(1+ǫ)2w(x∗). Fact 7. π(y#)≤π(z∗). Proof. Consider the feasible solution s = (x∗,y∗) to LP which is derived from b (x∗,z∗)usingtheconstructionfromFact5.Duetothisconstructionwehavethat π(y∗)=π(z∗).Letcbesuchthatc·w(x∗)=w(x#).Nowconsiders′ =(c·x∗,y∗) whichisfeasibletoLP sincec>1.Moreover,s′ isalsofeasibletoLPk+1.Thus b b w(x#)+π(y#)≤w(c·x∗)+π(y∗)=w(x#)+π(y∗).Thisconcludestheproof. ⊓⊔ Threshold rounding. We use the standard threshold rounding technique (cf. [23]). Let β ∈ (0,1) be a constant to be determined later. For every possible value α of y# that is at most β, let Q = {u : y# ≤ α}. Consider the instance u I of the NWST problem which is derived from I by keeping NWSTQ NWPCST only terminals from Q. Let LP be the following linear program NWSTQ min w x (LP ) v v NWSTQ v∈V X x ≥1 ∀S ⊆V \{r}, Q∩S 6=∅ v v∈XΓ(S) x ≥0 ∀v ∈V v LetOPT betheoptimumobjectivefunctionvalueofLP .Werunthe LPQ NWSTQ 2.4-approximationalgorithmforI byBermanandYaroslavtsev[3]which NWSTQ returns a solution F such that its cost is no greaterthan 2.4·OPT . Finally, LPQ return the best of all obtained solutions F (due to different values of α). Though the algorithm is deterministic its analysis is based on a randomized argument. Instead of trying all possible values of α, consider α to be chosen uniformly at random from [0,β]. Consider x′ = 1 x#. It follows that x′ is a 1−α 10