C:/documents and settings/msozio/desktop/conferenze/primal dual capvc/sicomp - last version/jochen110108last/capvc-jv.dvi

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Abstract
In this paper we consider the capacitated vertex cover problem which is the variant of vertex coverwhere each node is allowed to cover a limited number of edges. We present an efficient, deterministic,distributed approximation algorithm for the problem. Our algorithm computes a (2 + ǫ)-approximatesolution which violates the capacity constraints by a factor of (4 + ǫ) in a polylogarithmic number ofcommunication rounds. On the other hand, we also show that every efficient distributed approximationalgorithm for this problem must violate the capacity constraints.
Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual al- gorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributedversion of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchro-nization which forces any naive distributed implementation to use a linear number of communicationrounds. The challenge in this step is therefore to achieve a reduction of the communication complexityto a polylogarithmic number of rounds without worsening the approximation guarantee too much.
Keywords: Vertex Cover, Approximation Algorithms, Distributed Algorithms, Primal-Dual Algorithms
∗A preliminary version of this paper appeared in the Proceedings of the 24th Symposium on Principles of Distributed Computing, †Dipartimento di Informatica, Sistemi e Produzione, Universit`a di Roma Tor Vergata, Via del Politecnico 1, 00133, Roma, Italy.
‡Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada. Email: [email protected]. This work was done while being on leave at the Dipartimento di Informatica,Sapienza Universit`a di Roma.
§Dipartimento di Informatica, Sapienza Universit`a di Roma, Via Salaria 113, 00198, Roma, Italy.
¶Department of Databases and Information Systems, Max-Planck-Institut f¨ur Informatik, Stuhlsatzenhausweg 85, 66123 Saarbr¨ucken, Germany. Email: [email protected].
Introduction
The capacitated vertex cover problem (capVC) is the variant of vertex cover in which there is a limit onthe number of edges that a vertex can cover. A precise formulation of the problem is as follows. We aregiven an n-vertex undirected graph G = (V, E), non-negative weights wtv and vertex capacities Bv ≥ 1 forall vertices v ∈ V . A solution to a given capVC instance consists of a subset C ⊆ V and an assignmentπ : E → C of edges to vertices such that 1. π(e) ∈ {u, v} ∩ C for all edges e = (u, v) ∈ E, and 2. |π−1(v)| ≤ Bv for all v ∈ C.
The first set of constraints says that every edge must be covered by some vertex in the cover C. The secondcondition limits the number of edges that can be assigned to any cover vertex v to Bv. The goal is to find afeasible solution that has minimum total weight We emphasize the difference between the above hard-capacity version of capVC and its soft-capacity coun-terpart (capVCs): in capVCs, each vertex v ∈ V may be included xv ≥ 0 times in a cover. Vertex v thencontributes xvwtv to the weight of the cover, and the maximum number of edges that can be assigned to v isxvBv.
In this paper we present bicriteria sequential and distributed approximation algorithms for the (hard) capac-itated vertex cover problem. Given a feasible instance of the problem of optimal weight opt, our sequentialprimal-dual algorithm computes a vertex cover C of weight 2Bv edges to each cover vertex v ∈ C. Note that, differently from the hard-capacity case, capacities mightbe violated. However, the amount of the violation is bounded, which is not the case for capVCs. We alsoremark that, unlike capVCs, every v ∈ C contributes wtv to the weight of the cover even when its capacityBv is exceeded.
The distributed implementation of our method has an additional input parameter ǫ > 0 and computes acover of weight at most (2 + ǫ)opt that violates the capacity bound of each cover vertex by a factor of atmost (4 + ǫ). In the synchronous, message-passing model of computation the distributed algorithm takesO(log(nW )/ǫ) many rounds, where is the ratio of largest to smallest vertex weight in the given instance. This reduces to O(log n/ǫ) for theinteresting case of unit weights. We remark that our algorithm is deterministic, while typically efficientdistributed algorithms for graph problems require randomization (see [11, 20, 22, 23, 27, 28] among others).
Observe that any sub-linear distributed algorithm for capVC must violate the capacity constraints. Considerfor instance a ring where every vertex has unit capacity. A feasible solution provides a consistent orientationof the ring, something that requires a linear number of communication rounds. Therefore a bicriteria solutionis the best one can hope for in a distributed setting. In this paper we show that indeed every efficientdistributed approximation algorithm for capVC must violate the capacity constraints by a large additiveterm.
In our opinion the most interesting aspect of our work is that the distributed algorithm is derived in a sys-tematic fashion from a sequential primal-dual algorithm. To our knowledge, the first result of this kind is the(2 + ǫ)-approximate vertex cover algorithm described in [16]. Although described for the PRAM setting,the algorithm can be easily adapted to the distributed case. Our paper takes the primal-dual approach pio-neered in [16] one step further, giving a new and considerably more sophisticated example. Chudak et al. [4]recently showed that the techniques introduced in this paper can be extended to yield efficient distributedprimal-dual algorithms for vertex cover with soft capacities and for the facility location problem. The powerof the primal-dual method in the design of approximation algorithms is well established. In this paper weprovide further evidence to the fact that it is also a valuable tool in the design of distributed algorithms.
Capacity constraints arise naturally in distributed computing and computer networking. E.g., the scatternet-formation problem of ad hoc Bluetooth networks asks for a small dominating set where each vertex in theset dominates at most 7 vertices [6]. More generally, a small dominating set can act as the backbone ofthe routing infrastructure of an ad hoc network (see [29, 26] and references therein). Capacities modelcomputational and energy limitations and provide effective means to enforce load distribution among thevertices of the backbone. To the best of our knowledge, our paper is the first result that considers a capacitatednetwork design problem from the distributed computing point of view. Recently, Moscibroda and Kuhn gavean LP-based, bicriteria distributed solution to the capacitated dominating set problem [17].
Related work. Vertex cover with capacities has received considerable attention in recent years in the se-
quential setting, while our main motivation is to study it from a distributed point of view. The capacitated
vertex cover problem was first introduced by Guha et al. [12] who presented a simple 4-approximate LP-
rounding based algorithm for capVCs. Later on, the authors showed a 2-approximate primal-dual algorithm.
Subsequently, Gandhi et al. [10] presented a 2-approximate LP-rounding algorithm for capVCs.
The hard-capacitated vertex-cover problem is significantly harder than its soft-capacitated variant. Chuzhoyand Naor [5] first gave a sophisticated 3-approximate LP-rounding algorithm for the special case of capVCwith uniform vertex weights. Finally, in [9], Gandhi et al. presented an LP-rounding-based 2-approximationalgorithm for capVC with uniform weights.
In [5], Chuzhoy and Naor also showed that capVC in the presence of non-uniform vertex weights is as hardto approximate as set-cover. Lund and Yannakakis [24] proved that there is no o(log n)-approximation forthe latter problem unless NP ⊆ DTIME(nO(log log n)) (see also [8] for a refined result). Based on work byBellare et al. [3], and Raz and Safra [30], Alon et. al [1] recently improved upon this result and showed thatno o(log n)-approximation for the set-cover problem is possible unless P = NP. Chuzhoy and Naor’s workimplies that these hardness bounds translate to the capVC problem.
The best known approximation algorithm for the vertex-cover problem without capacity constraints, is dueto Karakostas [15] who presented a (2 − Θ(1/ log(n))-approximation for the problem. This improves upon earlier (2 − o(1))-approximation algorithms due to Halperin [13], Bar-Yehuda and Even [2] andHochbaum [14]. As mentioned, the same bound is essentially achievable in the distributed setting [16].
Unconditional lower-bounds based on communication constraints, as opposed to unproven complexity the-oretic assumptions, have been proved since the early stages [21, 25]. For more recent work see [18]. Also,Elkin [7] recently established trade-offs between the performance guarantee of a distributed approximationalgorithm for the minimum-cost spanning tree problem and the number of communication rounds it needs.
Finally, we mention that LP-duality has been previously used to design distributed algorithms for the domi-nating set problem [19, 28].
Our contribution. The first result we give is a bicriteria primal-dual approximation algorithm for capVC.
Theorem 1 Given a feasible capVC instance with capacities Bv ≥ 1 for all v ∈ V . There is a polynomial-
time primal-dual algorithm that computes a vertex cover (C, π) of weight at most 2opt that assigns at most
2Bv edges to each vertex v ∈ C.
We remark that if the input instance does not have a feasible solution, then our algorithm either computesa feasible solution for the (capacity) relaxed version of the problem, or it terminates with a certificate ofinfeasibility.
Theorem 1 is a natural step toward proving the main result of this paper.
Theorem 2 Given a feasible instance of capVC with capacities Bv ≥ 1 for all v ∈ V , and let ǫ ∈ (0, 1]
be an input parameter. There is a distributed deterministic algorithm that computes a vertex cover (C, π) of
weight at most (2 + ǫ)opt that assigns at most (4 + ǫ)Bv edges to each vertex v ∈ C. The algorithm needs
O(log(nW )/ǫ) rounds.
We remark that the message-size of our algorithm is O(log n + log wtmax).
Note that the running time is strongly polylogarithmic for polynomially large weights only. This includesthe important special case of unit weights. Obtaining a strongly polylogarithmic algorithm in general is achallenging open problem.
Similar to the sequential case, if the input instance does not have a feasible solution the algorithm eithercomputes a feasible solution for the relaxed version of the problem, or terminates with a certificate of infea-sibility. The latter however is necessarily local in nature. That is, some vertices will know that the algorithmhas failed, but it requires a linear number of communication rounds to distribute this information across thenetwork in general.
These theorems are complemented by the following lower-bound on the communication complexity of anyalgorithm for the weighted capVC problem with hard capacities: Theorem 3 Let B, k ≥ 1 be integer parameters. There is a capVC instance with uniform vertex capacities
B, for which any distributed approximation algorithm that assigns less than (1 + 1/k) · B edges to all
vertices, must take at least k communication rounds.
This result shows in particular that violating the capacity constraints is necessary and provides a trade-offbetween violation of capacities and running time.
Organization of the paper. In the following Section 2 we describe a sequential algorithm for the capacitated
vertex-cover problem and give a proof of Theorem 1. The next section shows how to turn the sequential
algorithm into a distributed one. This is done in two steps. First, we show how to convert the sequential
algorithm into a distributed one that computes a vertex cover that satisfies the approximation requirement.
In this step we assign only a subset of the edges. In the second and final step we assign all the remaining
edges. The proof of Theorem 3 is given in Section 4.
A sequential primal-dual algorithm
We present a so called primal-dual algorithm for the capVC problem. The algorithm and its analysis arebased on linear programming duality. In the next section we therefore introduce a linear programmingformulation of the problem together with its dual. Following that we describe our sequential algorithm andwe conclude this section with an analysis of the presented method.
A linear programming formulation
The problem can be formulated as an integer program where we introduce a binary indicator variable xv foreach v ∈ V . We let xv = 1 if v ∈ C and xv = 0 otherwise. For each edge e = (u, v) ∈ E we introduce twobinary variables ye,v and ye,u. For w ∈ {u, v} we let ye,w = 1 if and only if π(e) = w. In the following letδ(v) be the set of edges incident to vertex v ∈ V in G.
We now let (LP) be the standard LP relaxation obtained from (IP) by replacing the constraints (4) by In the following we use (i)v, (i)e, and (i)e,v to denote constraint (i) for vertex v ∈ V , edge e ∈ E, and pair(e, v) ∈ E × V , respectively. In the linear-programming dual of (LP) we associate variables αe, βe,w, γv andωv with constraints (1)e, (2)e,w, (3)v, and (5)v, respectively. The linear programming dual of (LP) is then The algorithm
We remark that the following simple LP rounding scheme similar to that proposed by Guha et al. [12] yieldsa 2-approximate vertex cover in which each vertex v covers at most 2Bv edges: Solve the LP relaxation (LP) and let (x, y) be its optimal solution. The cover set C consists of all vertices v with xv ≥ 1/2. Fore = (u, v) ∈ E, constraint (1)e implies that there is w ∈ {u, v} such that ye,w ≥ 1/2. We assign edgee to vertex w in this case. Clearly, the weight of the vertices in C is at most twice the optimal LP value.
Moreover, each vertex v ∈ C has at most 2Bv assigned edges.
We provide an alternate primal-dual algorithm in this section. As we shall see later, this algorithm possessesan efficient distributed implementation.
The high-level idea in primal-dual algorithms is to find a pair of feasible solutions for (D) and (IP). Subse-quently we upper-bound the performance ratio of the algorithm by bounding the multiplicative gap betweenthe objective values of the two solutions. Thus, our goal is to find a primal-dual pair of solutions whoseobjective functions values are within a small multiplicative constant of each other. Primal-dual algorithmstypically construct such a pair in an iterative manner: starting from a trivial feasible dual solution and aninfeasible primal one, the algorithm continuously raises the objective value of the dual solution while main-taining its feasibility, and it changes the partial primal solution in order to attain feasibility.
Our primal-dual capVC algorithm starts with the dual feasible solution α = β = γ = ω = 0 and theinfeasible primal solution x = y = 0. In order to obtain a feasible vertex cover, we have to a) select a setof cover vertices, and b) assign each edge e ∈ E to one of its end-points (which must be in the cover). Asis typical in primal-dual approximation algorithms, these decisions are governed by primal complementaryslackness.
In the following we say that a vertex v ∈ V is tight for a current dual solution (α, β, γ, ω) if constraint (7)vholds with equality. Similarly, a pair (e, w) ∈ E × V is tight if constraint (6)e,w is satisfied with equality.
Our algorithm will now increase the value of some of the dual variables and as a consequence create tightvertices and tight edge-vertex pairs. Tight vertices are candidates for our final cover and we will eventuallychoose a subset of these. Each edge e will eventually be assigned to one of its tight endpoints. In particular,edge e = (u, v) ∈ E will only be assigned to endpoint w ∈ {u, v} if (e, w) is tight. Once an edge is assignedto a vertex, we will remove it from the graph and continue. Similarly, once all edges incident to a certainvertex v ∈ V have been decided, the vertex is removed from the graph. The algorithm terminates, when thegraph is empty and, hence, when all edges have been assigned.
We now describe the algorithm. As customary with primal-dual algorithms, we describe it as a continuousprocess that can be implemented in polynomial-time by standard techniques. Initially all edges are unas-signed. At any given point, the algorithm increases the value of dual variables αe of all unassigned edgesuniformly at the same (unit) rate. Increasing variables αe for unassigned edges increases the left-hand sideof constraints of type (6) and we will have to also increase some of the β and γ variables in order to maintaindual feasibility. We describe the update process for these variables for each vertex v ∈ V depending on itstightness: v is non-tight In this case, we increase βe,v for all e ∈ δ(v) uniformly. Thus, the left- and right-hand side
of constraint (6)e,v for all e ∈ δ(v) increase at the same rate and feasibility is maintained.
v is tight If v has at most 2Bv incident edges, we add v to the cover, assign all edges in δ(v) to v and delete v
and the newly assigned edges from G. Otherwise v has more than 2Bv incident edges. In this case, weincrease ωv at rate Bv, γv at unit rate and we leave βe,v as is for all e ∈ δ(v). As a consequence, left-and right-hand side of (7)v remain unchanged, and left- and right-hand side of (6)e,v for all e ∈ δ(v)change at the same (unit) rate. Feasibility is therefore maintained also in this case.
Figure 1: An example instance for the primal-dual capVC algorithm.
We emphasize that our algorithm maintains a feasible dual solution for (D) for the original instance. Inparticular, deleting a vertex v and an edge e ∈ δ(v) means that the values of variables αe, βe,v, ωv and γvare frozen at their current state from this point on in the algorithm. The algorithm terminates when all edgeshave been assigned.
We demonstrate the algorithm using the example instance in Figure 1 (i) where we let Bu = 2, Bv = 3 andBw = ∞ for all other vertices w. We also choose wta = 2, wtu = 5, wtv = 6 and all other vertices haveinfinite weight. In the following we use V and E to refer to the vertex and edge sets of the given instance.
Running our algorithm for one time unit results in αe = 1 for all e ∈ E and βe,w = 1 for all w ∈ V and forall e ∈ δ(w). At this point, constraint (7)u is tight. As u has 5 > 2 · Bu = 4 unassigned incident edges, wecan not assign any edge at this point. Thus, we continue to increase αe for all edges e ∈ E. Simultaneously,we increase βe,w for all w ∈ V \ {u} and for all e ∈ δ(w) at unit rate, we increase ωu at rate Bu = 2 and γuat unit rate.
After 1 more time unit, the positive dual variable values are βe,w = 2 ∀w ∈ V \ {u}, ∀e ∈ δ(w) At this point, vertices a, u and v are tight. Vertex a and v have one and three incident edges, respectively,and we can hence add both vertices to the cover and delete them and their incident edges from the graph.
The number of remaining edges all of which are incident to u is now 4 = 2Bu. We can assign all of them tou.
Figure 1 (ii) shows the computed primal solution; cover vertices are shaded and arc directions indicate edgeassignment. We note that the primal solution is feasible for (IP) only if we relax the capacity constraint ofvertex u. In fact, it is not hard to see that any feasible solution to (IP) for this instance must have infiniteweight.
Analysis
In this section we present a proof of Theorem 1.
Assume first that the algorithm from Section 2.2 does not terminate for a given input instance. It is thennot hard to see that the algorithm must reach a point in the execution, where each tight vertex v ∈ V hasdegree more than 2Bv and where each remaining edge is incident to tight vertices on both ends. Using thepigeon-hole principle it follows that, in any assignment of edges to vertices, there must be at least one tightvertex v that is assigned more than Bv edges. Thus the given input instance is infeasible, and the set of tightvertices together with the set of unassigned edges certifies this fact.
In the following we focus on feasible capVC instances. For such instances our algorithm terminates with acover C, an assignment {ye,v}e∈E,v∈V of edges to vertices in the cover, and a corresponding dual solution(α, β, ω, γ). We first show that the dual is feasible for (D).
Lemma 1 The dual solution (α, β, ω, γ) is feasible for (D).
Proof: We can think of the execution of the algorithm as a process over time: The algorithm starts at time0 and then raises αe by 1 for all edges per unit of time. We prove the lemma by induction on (appropriatelydiscretized) time.
Our initial dual solution is clearly feasible. Now consider a later time in the algorithm. Let O be the set oftight vertices at that time.
For a vertex v ∈ V \ O and for an edge e ∈ δ(v) we raise αe and βe,v simultaneously and hence maintaindual feasibility. For a vertex v ∈ O we raise ωv at a rate of Bv per time unit and we raise γv at unit rate. Forall edges e ∈ δ(v) we raise αe at unit rate as well. It is not hard to see that we maintain dual feasibility thisway.
We are ready to prove that our algorithm computes a 2-approximate primal solution.
Lemma 2 Our algorithm terminates with a vertex cover C and a corresponding feasible dual solution
(α, β, γ, ω) whenever there exists a feasible solution (x, y) for (LP). In particular, we must have
Let v ∈ C be a vertex in the computed vertex-cover and let e ∈ δ(v) be an edge that is incident to v. Noticethat our algorithm always maintains since αe is raised whenever βe,v increases and the rate of increase is the same.
Observe also that γv is only increased if the degree deg(v) of vertex v exceeds 2Bv. Let δ1(v) ⊆ δ(v) bethe set of edges that are incident to v when γv is increased for the last time in the algorithm and notice thatwe must have |δ1(v)| > 2Bv.
Consider an edge e ∈ δ1(v) and note that γv and αe increase at the same rate after the point of time wherev becomes tight. Notice also that the algorithm increases αe and βe,v at the same rate before v becomes tight. Variable βe,v is not increased after v becomes tight, and γv is not increased before v becomes tight.
Therefore, for all e ∈ δ1(v) we must have Since v is tight when the algorithm adds it to the cover and deletes it from the graph, it must also be the casethat where the last equality follows from the fact that we raise ωv at a rate of Bv if and only if we raise γv at arate of 1.
We use δ2(v) = δ(v) \ δ1(v) and obtain where the first inequality uses (10), the second inequality uses (8) and (9), and the last inequality followsfrom the fact that v is incident to at least 2Bv edges whenever γv is increased.
Now observe that we raise γv and ωv only for tight vertices in our algorithm. Given that the input instanceis feasible, the degree of any tight vertex v will eventually drop below 2Bv. It therefore follows from thealgorithm description that any vertex that becomes tight during the execution of the algorithm is eventuallyincluded in the vertex cover C. Hence (12) implies The lemma follows from Bvγv = ωv for all v ∈ V and from the fact that |e ∩ C| ≤ 2.
Lemmas 1 and 2 complete the proof of Theorem 1.
A distributed algorithm
In this section we will describe a distributed primal-dual algorithm for capVC which uses the ideas de-veloped in Section 2. As before, the algorithm maintains a pair of (infeasible) primal and (feasible) dualsolutions at all times. However, these solutions need to be stored in a distributed fashion: each vertex v ∈ Vstores and manipulates (a) primal variables xv and ye,v for all e ∈ δ(v), and (b) dual variables γv, ωv, αe and βe,v for all e ∈ δ(v).
Figure 2: The figure shows the possible states of vertex v ∈ V in the vertex-selection phase. The arrowsindicate the possible transitions between the states. Shaded states are active while others are inactive states.
Note that, for every edge e = (u, v), both u and v store a copy of αe. The algorithm guarantees theconsistency of the two copies.
Observe that a naive distributed implementation of the method described in Section 2 yields an algorithmthat needs a linear number of communication rounds in the worst case. In fact, consider a graph G withvertex set {v1, . . . , vn, u1, . . . , u2B} for some n, B ≥ 1. Let the edge-set of G be E = {(vi, vi+1) : 1 ≤ i ≤ n − 1} ∪ {(vi, uj) : 1 ≤ i ≤ n, 1 ≤ j ≤ 2B − 1} ∪ {(vn, u2B)} and notice that vertex v1 has degree 2B while vertices v2, . . . , vn have degree 2B +1. Let the cost of verticesv1, . . . , vn be 0 and assign a unit cost to all other vertices in G. In the execution of the sequential primal-dualalgorithm, all vertices v1, . . . , vn are tight immediately and all other vertices are non-tight. Vertex v1 is theonly tight vertex with degree at most 2B. After assigning the 2B edges in δ(v1) to v1, the degree of vertexv2 drops to 2B. In general, the degree of vertex vi drops to 2B after assigning edges to vertices v1, . . . , vi−1for all 1 ≤ i ≤ n. Doing this in in a distributed fashion takes n communication rounds.
Adapting the algorithm in order to cope with the above synchronization problem is not an easy task. In factit can be seen that synchronous increase of the duals is at the heart of Lemma 2 where it is used to argue thatthe dual constraints of type (6) are satisfied with equality at all times.
The distributed algorithm has two main phases: Vertex-Selection In this phase we compute a vertex cover C ⊆ V that is (2 + ǫ)-approximate. It is here that
we solve the above mentioned synchronization problem. While computing an approximate cover, wealso assign part of the edges to the vertices in C. At most 2Bv edges are assigned to each v ∈ C.
Edge-Assignment Here, we assign all the remaining edges to the vertices in C. This time, at most (2 + ǫ)Bv
For ease of presentation we assume from now on that the given capVC instance is feasible.
Vertex-selection phase
As said, the distributed algorithm mimics the primal-dual algorithm from Section 2. Each vertex v ∈ Vstores part of the dual solution and it initially sets γv = ωv = 0 and it also lets αe = βe,v = 0 for all edgese ∈ δ(v).
The distributed algorithm works in rounds. At the beginning of any given round i, we let the residual weightwtiv of vertex v be the difference between the right-hand side and the left-hand side of (7)v for the currentfeasible dual solution. Thus, we initialize wt0v to wtv for all v ∈ V . A vertex v ∈ V is either active orinactive in any given round i. An active vertex v can be in one of two states: Vertex v is non-tight whenever the slack in constraint (7)v is more than θ · wtv for aparameter θ ≥ 0 whose exact value will be determined later.
We let the state of vertex v be tight if wtiv ≤ θ · wtv and if v has more than 2Bvnon-tight neighbors. Intuitively, a tight vertex v will eventually be part of the computedcover. It will be assigned a subset of at most 2Bv of the edges to its non-tight neighbors.
We will say that an edge (u, v) ∈ E is active in round i if both u and v are active in that round. For anyvertex v ∈ V , we let degit(v) and degint(v) be the number of its tight and non-tight neighbors in round i. Wealso let degi(v) = degit(v) + degint(v) be the active neighbors of v in round i. An inactive vertex v can bein one of two states: A tight vertex switches its state to inside if the number degint(v) of non-tight neigh-bors is at most 2Bv. Vertex v will be part of the final cover and we assign all edgesbetween v and any of its non-tight neighbors to vertex v.
We switch the state of a non-tight vertex v to outside if it has no tight ornon-tight neighbors. We will later argue that all neighbors of v in G are inside inthis case.
The vertex-selection phase terminates when no active vertices remain. The resulting vertex cover C consistsof all vertices whose final state is inside.
We proceed with a detailed description of round i of the distributed algorithm. The round has two steps: Step 1: All non-tight vertices are dormant. Each tight vertex v ∈ V counts the number of active non-tight
neighbors. If this number is at most 2Bv we assign all edges connecting v to non-tight neighbors to v. We
also switch v’s state to inside and let v communicate its state-switch to all active neighbors. At this point
each active vertex v ∈ V knows the number degi(v) of active neighbors in G.
Step 2: The behavior of an active vertex v ∈ V depends on its current state:
v is non-tight: If degi(v) is 0 we know that all edges incident to v have been assigned to other vertices.
Therefore, we can switch the state of v to outside.
On the other hand, assume that v has active neighbors. Raising αe and βe,v uniformly by wtiv/degi(v) forall active edges e ∈ δ(v) decreases the residual weight of v to 0. Vertex v strives for tightness and thereforeproposes to any active neighbor u to raise α(u,v) and also β(u,v),v by its proposal Consider an active edge e = (u, v) ∈ δ(v). We raise αe and βe,v by min{pu, pv} and decrease the residualweight wtiv of v by the same amount.
v is tight: Notice that step 1 guarantees that v has more than 2Bv non-tight neighbors. Vertex vreceives proposals from all such neighbors and lets pv be their minimum. Vertex v then sends pv to all suchneighbors.
For all non-tight neighbors u of v we increase α(u,v) by pv. In order to maintain dual feasibility, wecannot increase β(u,v),v since v is tight. Hence we increase ωv by Bvpv and γv by pv.
Observe that tight vertices have to wait for the proposals of their non-tight neighbors before making theirown proposal. Hence two communication rounds are needed to update all the variables.
We can show that the number of communication rounds needed to complete the vertex-selection phase issmall. Recall that W denotes the ratio of largest to smallest vertex weights.
Lemma 3 The vertex-selection phase ends in O(log(nW )/θ) rounds.
Proof: We use a potential function argument in order to show the bound on the number of communicationrounds. For round j ≥ 0 we define the potential of each vertex v ∈ V as Φjv = wtv/degj(v) if degj(v) > 0and we let Φjv = wtmax otherwise. Then let Note that Φj is a non-decreasing function of j. In fact, we will show that Φj doubles at least every ⌈2/θ⌉rounds. The lemma then follows since wtmin ≤ Φj ≤ wt Consider any given round i. Let V j be the set of non-tight vertices at the beginning of round j, j ≥ i, with v ’s and degj (v)’s are non-increasing, while the Φjv ’s are non- decreasing. Consider any vertex v ∈ V i ∈ V j′ for j′ ≥ i + ⌈2/θ⌉. As a consequence, v > 2Φi, and hence Φj′ > 2Φi.
Assume by contradiction that v ∈ V j′. Then, by the observation above, v ∈ V j for any j ∈ {i, i+1, . . . , j′}.
non-tight vertex with the smallest proposal pw in round j. Recall that wtw ≥ θ wtw for non-tight vertices. We then have It follows that the reduction of the residual weight of v in round j is at least degj (v) · pmin,j ≥ degj(v) · θ · Φj ≥ degj(v) · θ · Φi ≥ degj(v) · θ · Φjv/2 = θ · wtv/2, where the first inequality uses (13) and the third inequality uses the definition of the set V j. Hence which contradicts the assumption that v ∈ V j′.
We now prove that the weight of the vertices in C is small.
Lemma 4 The total weight of the vertices in C is at most 2 times the optimum.
Assume that the distributed algorithm finishes after t ≥ 0 rounds and let (α, β, γ, ω) be the final dual. A proof very similar to that of Lemma 1 shows that the dual is indeed feasible. We proceed as in theproof of Lemma 2.
Consider a vertex v ∈ C and observe that v must have been tight before switching to the inside state.
Thus wttv ≤ θwtv, and Equation (15) is trivially satisfied if we consider only the steps in which v is non-tight. In fact, in thesesteps ωv = 0 and βe,v = αe, for all e ∈ δ(v).
Consider now a step in which v is tight. The value of the left-hand side of Equation (15) does not change.
If ωv increases by a quantity Bv · pv, γv increases by a quantity pv. It follows that, for all edges e = (v, u)between v and a non-tight neighbor u of v in the current step, the value of αe also increases by at leastpv. Since there are at least 2Bv such neighbors, the right-hand side of (15) cannot decrease.
where the first inequality uses (14) and the second inequality (15). Since every edge is incident to at mosttwo vertices from C we have that the right hand-side of the last inequality is bounded by For a given accuracy parameter ǫ ≥ 0 we now let θ = 1 − 2/(2 + ǫ). Note that this choice implies that1/θ = O(1/ǫ) for ǫ ∈ (0, 1]. Hence, given a feasible instance of capVC our distributed algorithm terminateswithin O(log(nW )/ǫ) communication rounds with a cover of weight at most (2 + ǫ)opt as was claimed inTheorem 2.
Edge-assignment phase
At the end of the vertex-selection phase we are left with a subset C′ ⊆ C of the tight vertices such that allunassigned edges have both their end-points in C′. In the following we let G0 = G[C′] = (V, E) be thegraph induced by the vertices in C′. Assuming that the given capVC instance is feasible, there must be anassignment of the edges in G0 to the vertices in C′ that obeys the original capacity bounds. We describea deterministic distributed algorithm which assigns at most (2 + ǫ)Bv edges to each v ∈ C′ in O(log n/ǫ)rounds.
Our algorithm starts with all edges unassigned and computes a final assignment iteratively. In each round twe consider all vertices v ∈ V with at most (2 + ǫ)Bv incident unassigned edges, and we assign all suchedges (u, v) ∈ δ(v) to v. We continue until no unassigned edges remain.
To prove that the number of rounds is polylogarithmic we need the following lemma. Let H be the set ofvertices with degree more than (2 + ǫ)Bv and let E(H) be the set of those edges that have both of theirendpoints in H. Finally use E(H) as an abbreviation for the set E \ E(H) of edges that have at most oneendpoint in H.
Lemma 5 If there is a feasible assignment, then we must have |E(H)| ≥ ǫ|E(H)|.
Proof: Let π : E → V be a feasible assignment of edges to vertices. We have that: as every edge in E(H) is counted exactly twice in the sum on the left-hand side while an edge in E(H) iscounted at most once. Moreover, since every edge in E(H) must be assigned to some vertex in H. From equations (16) and (17) it followsthat: Lemma 6 If there is a feasible assignment, then the algorithm above assigns at most (2 + ǫ)Bv edges to
each v ∈ V . The number of rounds required is O(log n/ǫ).
Proof: The capacity bound in the theorem follows immediately since for each vertex v in V there is at mostone round t in which we assign at most (2 + ǫ)Bv edges to it.
Let Et be the set of unassigned edges at the beginning of iteration t and let Gt = G[Et] be the subgraph ofG induced by Et. We also use Ht to denote the set of vertices v ∈ V whose degree is more than (2 + ǫ)Bv inGt. Note that for any t, there must exist a feasible assignment in Gt as Gt is a subgraph of the initial graphG where a feasible assignment exists. So we can apply Lemma 5 and conclude that: |Et| = |E(Ht)| + |E(Ht)| ≥ (1 + ǫ)|E(Ht)|.
In round t all the edges in E(Ht) are assigned to some vertex and so |Et+1| ≤ |E(Ht)|. Hence, |Et+1| ≤ 1 |Et| and the number of unassigned edges decreases by a factor of (1 + ǫ) in every round.
Since at most 2Bu edges are assigned to each u during the vertex-selection phase, this concludes the proofof Theorem 2.
A Lower Bound
In this section we show that every efficient distributed approximation algorithm for capVC needs to violatethe capacity constraints by a large additive term.
Consider the following two families of graphs G0 L0, L1 . . . Lk, each one containing 2B + 1 vertices. Each vertex in level Li, i = 0, 1 . . . k − 1, is adjacentto exactly B vertices in level Li+1. Symmetrically, each vertex in level Li, i = 1, 2 . . . k, is adjacent toexactly B vertices in level Li−1. There are no other edges in the graph. In particular, each level Li inducesan independent set. Graph G1 by adding an edge between each pair of vertices in L0. Let the capacity of all vertices in both graphs be B. Moreover, all vertices have cost zero, except for thevertices in level Lk, which have cost one. Figure 3 shows an instance of the two graphs.
For 0 ≤ i ≤ k − 1, let δi be the set of edges that connect vertices in Li to those in Li+1. We obtain a feasiblesolution for G0 and assign all edges in δi to the vertices in Li for 0 ≤ i ≤ k − 1.
has n = (k + 1)(2B + 1) vertices and Bn edges. Thus, any feasible capacitated vertex cover must contain all vertices. Moreover, the edges belonging to the clique on L0 clearly have to be assigned tothe vertices in L0. Thus, the unique feasible capVC solution for G0 in Li+1 for all 0 ≤ i ≤ k − 1.
The following lemma turns out to be useful in the proof of the lower bound.
Lemma 7 Consider a solution for G1
that assigns at most (B + c) edges to each vertex, for some c ≥ 1. For 0 ≤ i ≤ k − 1, let Ai be the number of edges in δi that are assigned to vertices in Li. Then for all 0 ≤ i ≤ k − 1. Proof: The proof is by induction on i. For i = 0, all clique edges need to be assigned to vertices in L0. Thespare capacity of the vertices in L0 is thus (2B + 1)c and this is the maximum number of edges in δ0 thatcan be assigned to the vertices in L0.
Now assume that the claim is true for all 0 ≤ i < k. Using the induction hypothesis, at most (2B +1)(i+1)cedges in δi are assigned to the vertices in Li. Therefore, the remaining (2B + 1)(B − (i + 1)c) edges needto be assigned to vertices in Li+1. The remaining capacity of the vertices in Li+1 is thus (2B + 1)(B + c) − (2B + 1)(B − (i + 1)c) = (2B + 1)(i + 2)c and this is the maximum number of edges in δi+1 that can be assigned to vertices in Li+1.
Armed with the above lemma we are now ready to provide a proof of Theorem 3. We restate it here forcompleteness.
Theorem 3 Let B, k ≥ 1 be integer parameters. There is a capVC instance with uniform vertex capacities
B, for which any distributed approximation algorithm that assigns less than (1 + 1/k) · B edges to all
vertices, must take at least k communication rounds.
Proof: The proof is by contradiction. Let c < B/k and consider a distributed approximation algorithm forcapVC that assigns at most (B + c) edges to each vertex for any given (uniform capacity) instance whoserunning time is less than k.
We first execute this algorithm on graph G1 . Lemma 7 shows that at most (2B + 1) · kc of the edges in δk−1 are assigned to the vertices in Lk−1. The number of edges that need to be assigned to vertices in Lk istherefore at least where the inequality uses our assumption on c. Hence at least one vertex in Lk needs to be in any cover ofG1 that assigns at most B + c edges to each vertex. Let u be this vertex.
We now run the algorithm again on G0 . Since the graphs G0 from u, this vertex will be included in the cover in this case too. On the other hand, no vertex in Lk can bepart of any approximate solution for G0 .
For instance, consider an (efficient) distributed approximation algorithm for capVC with running timeO(logd n), where d is a positive constant. Theorem 3 then shows that there is a family of (uniform capacity)capVC instances for which this algorithm must assign at least B + Ω( B have n = (2B + 1)(k + 1) vertices. This implies that B = Θ n , which is large in the interesting case when k is polylogarithmic. However, this hitch is easily removed bydefining a graph G0 (resp. G1) consisting of t disjoint copies of the main building block G0 Using the new parameter t we can now produce instances in which B is arbitrarily small in comparison to nwhile our proof argument goes through unchanged.
Acknowledgments We would like to thank Volker Kaibel for pointing out a much simplified proof of
Lemma 5.
References
[1] N. Alon, D. Moshkovitz, and S. Safra. Algorithmic construction of sets for k-restrictions. ACM Trans. on Algorithms, 2(2):153–177, 2006.
[2] R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover prob- lem. Annals of Discrete Mathematics, 25:27–45, 1985.
[3] M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs: Applications to approximation. In Proceedings, ACM Symposium on Theory of Computing, pages294–304, 1993.
[4] F. Chudak, T. Erlebach, and A. Panconesi. Primal-dual based distributed algorithms for vertex cover with soft capacities and facility location. Manuscript, 2004.
[5] J. Chuzhoy and J. Naor. Covering problems with hard capacities. In Proceedings, IEEE Symposium on Foundations of Computer Science, pages 481–489, 2002.
[6] D. Dubhashi, O. H¨aggstr¨om, G. Mambrini, A. Panconesi, and C. Petrioli. Blue pleieades, a new solution for device discovery and scatternet formation in multi-hop bluetooth networks. ACM-Kluwer WirelessNetworks (Winet), 13(1):107–125, 2007.
[7] M. Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed mini- mum spanning tree problem. In Proceedings, ACM Symposium on Theory of Computing, pages 331–340, 2004.
[8] U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998.
[9] R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan. An improved approximation algo- rithm for vertex cover with hard capacities (extended abstract). In Proceedings, International Collo-quium on Automata, Languages and Programming, pages 164–175, 2003.
[10] R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding in bipartite graphs. In Proceedings, IEEE Symposium on Foundations of Computer Science, pages 323–332, 2002.
[11] D. Grable and A. Panconesi. Nearly optimal distributed edge colouring in o(log log n) rounds. Random Structures and Algorithms, 10(3):385–405, 1997.
[12] S. Guha, R. Hassin, S. Khuller, and E. Or. Capacitated vertex covering. J. Algorithms, 48(1):257–270, [13] E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hyper- graphs. SIAM J. Comput., 31(5): 1608–1623, 2002.
[14] D. S. Hochbaum. Approximation algorithms for set covering and vertex cover problems. SIAM J. Com- [15] G. Karakostas. A better approximation ratio for the vertex cover problem. In Proceedings, International Colloquium on Automata, Languages and Programming, pages 1043–1050, 2005.
[16] S. Khuller, U. Vishkin, and N. Young. A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms, 17(2):280–289, 1994.
[17] F. Kuhn, T. Moscibroda. Distributed Approximation of Capacitated Dominating Sets. In Proceedings, ACM Symposium on Parallelism in Algorithms and Architectures, pages 161–170, 2007.
[18] F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In Proceedings, ACM Symposium on Principles of Distributed Computing, pages 300–309, 2004.
[19] F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. In Proceedings, ACM Symposium on Principles of Distributed Computing, pages 25–32, 2003.
[20] L. Jia, R. Rajaraman and T. Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193-205, 2002.
[21] N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992.
[22] M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., Removing randomness in parallel without processor penalty.
[24] C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. ACM, [25] M. Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete [26] P. Wan, K. M. Alzoubi and O. Frieder Distributed construction of connected dominating set in wireless ad hoc networks. Proceedings of INFOCOM, 2002.
[27] A. Panconesi and A. Srinivasan. The local nature of delta-coloring and its algorithmic applications.
Combinatorica, 15(2):255–280, 1995.
[28] S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation algorithms for (multi)set (multi)cover and covering integer programs. SIAM J. Comput., 28(2):525–540, 1998.
[29] R. Rajaraman. Topology control and routing in ad hoc networks: a survey. SIGACT News, 2002.
A sub-constant error-probability low-degree test, and a sub-constant error- probability PCP characterization of NP. In Proceedings, ACM Symposium on Theory of Computing,pages 475–484, 1997.

Source: http://www.disp.uniroma2.it/users/grandoni/Pubblicazioni/GKPS08sicomp.pdf