Optimal distributed covering algorithms

We survey previous results for mwhvc and mwvc. A comprehensive list of previous results appears in Tables 1 and 2.

Vertex Cover. The understanding of the round complexity for distributed mwvc has been established in two papers: a lower bound in [19] and a matching upper bound in [4]. Let \(\varDelta \) denote the maximum vertex degree in the graph G. The lower bound states that any distributed constant-factor approximation algorithm requires \(\varOmega (\log \varDelta / \log \log \varDelta )\) rounds to terminate. This lower bound holds for every constant approximation ratio, for unweighted graphs and even if the message lengths are not bounded (i.e., LOCAL model) [19]. The matching upper bound is a \((2+\varepsilon )\)-approximation distributed algorithm in the congest model, for every \(\varepsilon =\varOmega (\log \log \varDelta / \log \varDelta )\).² In [16] an \(O(\log n)\)-round 2-approximation randomized algorithm for weighted graphs in the congest model is given. We note that [16] was the first to achieve this running time with no dependence on W, the maximum weight of the nodes. Recently, Ben-Basat et al. [6] showed an \(O(OPT^2\log OPT)\) rounds algorithm for computing the minimal (unweighted) vertex cover and a O(OPT) rounds for a \((2+\varepsilon )\)-approximation. Here, OPT is the size of the smallest cover and thus these algorithms are adequate when a small solution exists.

Hypergraph Weighted Vertex Cover. For constant values of f, Astrand et al. [2] present an f-approximation algorithm for anonymous networks whose running time is \(O(\varDelta ^2 + \varDelta \cdot \log ^* W)\). Khuller et al. [15] provide a solution that runs in \(O(f \cdot \log \varepsilon ^{-1} \cdot \log n)\) rounds in the congest model for any \(\varepsilon > 0\) and achieves an \((f+\varepsilon )\)-approximation. Setting \(\varepsilon = 1/W\) (recall that \(W=\hbox {poly}(n)\)) results in a f-approximation in \(O(f\log ^2 n)\)-rounds. For constant \(\varepsilon \) and f values, Kuhn et al. [17, 18] present an \((f+\varepsilon )\)-approximation algorithm that terminates in \(O(\log \varDelta + \log W)\) rounds.

For the Minimum Cardinality (i.e., unweighted) Vertex Cover in Hypergraphs Problem, the lower bound was recently matched by [9] with an \((f+\varepsilon )\)-approximation algorithm in the congest model. The round complexity in [9] is \(O\left( f/\varepsilon \cdot \frac{\log (f\cdot \varDelta )}{\log \log (f\cdot \varDelta )}\right) \), which is optimal for constant f and \(\varepsilon \). The algorithm in [9] and its analysis is a deterministic version of the randomized maximal independent set algorithm of [10].

In this paper, we present a deterministic distributed \((f+\varepsilon )\)-approximation algorithm for minimum weight vertex cover in f-rank hypergraphs, which completes inrounds in the congest model. For any constants \(\varepsilon \in (0,1)\) and \(f\in {\mathbb {N}}^+\) this implies a running time of \(O(\log {\varDelta } / \log \log \varDelta )\), which is optimal according to [19]. This is the first distributed algorithm for this problem whose round complexity does not depend on the node weights nor the number of vertices.

Our algorithm is one of a handful of distributed approximation algorithms for local problems which are provably optimal [3, 4, 7‐9, 11]. Among these are the classic Cole-Vishkin algorithm [8] for 3-coloring a ring, the more recent results of [3] and [4] for mwvc and Maximum Matching, and the result of [9] for Minimum Cardinality Hypergraph Vertex Cover.

Our algorithm also achieves a deterministic f-approximation for the problem in \(O(f\log n)\) rounds. This improves over the best known deterministic result for hypergraphs \(O(f\log ^2 n)\) [15] and matches the best known randomized results for weighted vertex cover (\(f=2\)) of \(O(\log n)\)-rounds [16].

We also show that general covering Integer Linear Programs (ILPs) can be reduced to mwhvc in the distributed setting. That is, LP constraints can be translated into hyperedges such that a cover for the hyperedges satisfies all covering constraints. This allows us to achieve anrounds \((f\lceil \log _2(M)+1 \rceil +\varepsilon )\)-approximate integral solution, where f bounds the number of variables in a constraint, \(\varDelta \) bounds the number of constraints a variable appears in, and \(M=\max \left\{ 1, \lceil 1/a_{\min } \rceil \right\} \), where \(a_{\min }\) is the smallest normalized constraint coefficient.

The Primal-Dual schema. The Primal-Dual approach introduces, for every hyperedge \(e \in E\), a dual variable denoted by \(\delta (e)\). The dual edge packing constraints are \(\forall v\in V,\sum _{v \in e} \delta (e) \le w(v)\). If for some \(\beta \in [0,1)\) it holds that \(\sum _{v \in e} \delta (e) \ge (1-\beta )\cdot w(v)\), we say the node v is \(\beta \)-tight. Let \(\beta =\varepsilon /(f+\varepsilon )\). For every feasible dual solution, the weight of the set of \(\beta \)-tight vertices is at most \((f+\varepsilon )\) times the weight of an optimal (fractional) solution. The algorithm terminates when the set of \(\beta \)-tight edges constitutes a vertex cover.

The fractional LP relaxation of mwhvc is defined as follows.

The dual LP is an Edge Packing problem defined as follows:

The following claim is used for proving the approximation ratio of the mwhvc algorithm.

The challenge. When designing a Primal-Dual distributed algorithm, the main challenge is in controlling the rate at which we increase the dual variables. On the one hand, we must grow them rapidly to reduce the number of communication rounds. On the other hand, we may not violate the edge packing constraints. This is tricky in the distributed environments as we have to coordinate between nodes. For example, the result of [4] does not generalize to hypergraphs, as hyperedges require the coordination of more than two nodes in order to increment edge variables.

Our algorithm. The algorithm proceeds in iterations, each of which requires a constant number of communication rounds. We initialize the dual variables in a “safe” way so that feasibility is guaranteed. We refer to the additive increase of the dual variable \(\delta (e)\) as \({{\,\mathrm{bid}\,}}(e)\). Similarly to [5] (where bids are called deals), we use levels to measure the progress made by a vertex. Whenever the level of a vertex increases, it sends a message about it to all incident edges, which multiply (decrease) their bids by 0.5. Intuitively, the level of a vertex equals the logarithm of its uncovered portion. Formally, we define the level of a vertex v as \(\ell (v)\triangleq \left\lfloor \log \frac{w(v)}{w(v)-\sum _{e\ni v} \delta (e)} \right\rfloor \). That is, the initial level of v is 0 and it is increased as the dual variables of the edges incident to v grow. The level of a vertex never reaches \(z\triangleq \lceil \log \beta ^{-1} \rceil \) as this implies that it is \(\beta \)-tight and entered the cover. Loosely speaking, the algorithm increases the increments \({{\,\mathrm{bid}\,}}(e)\) exponentially (multiplication by \(\alpha \)) provided that no vertex \(v\in e\) is \((0.5^{\ell (v)} / \alpha )\)-tight with respect to the bids of the previous iteration. Here, \(\alpha \ge 2\) is a positive parameter that we determine later. This is achieved by checking if all the vertices in e can increase the dual variables by an \(\alpha \) factor while staying at the current level. Namely, each vertex either sends a “raise” message, that signals that an \(\alpha \)-factor increase in the dual variables of all its adjacent edges would keep it in its current level, or a “stuck” message otherwise. \({{\,\mathrm{bid}\,}}(e)\) is then increased only if all the edge’s vertices sent a “raise” message. The analysis builds on two observations: (1) The number of times that the increment \({{\,\mathrm{bid}\,}}(e)\) is multiplied by \(\alpha \) is bounded by \(\log _\alpha \varDelta \). (2) The number of iterations in which \({{\,\mathrm{bid}\,}}(e)\) is not multiplied by \(\alpha \) is bounded by \(O(f\cdot z\cdot \alpha )\). Loosely speaking, each such iteration means that for at least one vertex \(v\in e\) the sum of bids is at least an \(1/(2\alpha )\)-fraction of its slack. Therefore, after at most \(O(\alpha )\) such iterations that vertex will level up. Since there are z levels per vertex and f vertices in e, we have that the number of such iterations is at most \(O(f\cdot z\cdot \alpha )\). Hence the total number of iterations is bounded by \(O(\log _\alpha \varDelta +f\cdot z\cdot \alpha )\).

Integer linear programs (ILPs).   We show distributed reductions that allow us to compute an \((f+\varepsilon )\)-approximation for general covering integer linear programs (ILPs). To that end, we first show that any Zero-One covering program (where all variables are binary) can be translated into a set cover instance in which the vertex degree is bounded by \(2^f\) times the bound on the number of constraints each ILP variable appears in. We then generalize to arbitrary covering ILPs by replacing each variable with multiple vertices in the hypergraph, such that the value associated with the ILP variable will be the weighted sum of the vertices in the cover.

The following invariants are satisfied throughout the execution of the algorithm. In the following claim we bound the sum of the bids of edges incident to a vertex.

If an edge e is covered in iteration j, then e terminates and \(\delta _i(e)\) is not set for \(i\ge j\). In this case, we define \(\delta _i(e)=\delta _{j-1}(e)\), namely, the last value assigned to a dual variable.

Let \(\textsf {opt}\) denote the cost of an optimal (fractional) weighted vertex cover of G.

In this section, we prove that the number of communication rounds of Algorithm mwhvc is bounded by (where \(\gamma >0\) is a constant, e.g., \(\gamma =0.001\))It suffices to bound the number of iterations because each iteration consists of a constant number of communication rounds.

Let \(z\triangleq \lceil \log _2 {\frac{1}{\beta }} \rceil \). Note that \(z=O\left( \log ({f}/{\varepsilon })\right) \).

We denote the number of rows of the matrix A by m and the number of columns by n. Let f(A) (resp., \(\varDelta (A)\)) denote the maximum number of nonzero entries in a row (resp., column) of A.

Given a covering ILP, \(ILP(A,\mathbf {b},\mathbf {w})\), the communication network N(ILP) over which the ILP is solved is the bipartite graph \(N=(X\times C, E)\), where: \(X=\{x_j\}_{j\in [n]}\), \(C=\{c_i\}_{i\in [m]}\), and \(E=\{(x_j,c_i)\mid A_{i,j}\ne 0\}\). We refer to the nodes in X as variable nodes, and to those in C as constraint nodes. Note that the maximum degree of a constraint node is f(A) and the maximum degree of a variable node is \(\varDelta (A)\).

We assume that the local input of every variable node \(x_j\) consists of \(w_j\) and the j’th column of A (i.e., \(A_{i,j}\), for \(i\in [m]\)). Every constraint vertex \(c_i\) is given the value of \(b_i\) as its local input. We assume that these inputs can be represented by \(O(\log (nm))\) bits. In \((f+1)\) rounds, every variable node \(v_j\) can learn all the components in the rows i of A such that \(A_{i,j}\ne 0\) as well as the component \(b_i\).

The special case in which a variable may be assigned only the values 0 or 1 is called a zero-one program. We denote the zero-one covering ILP induced by a matrix A and vectors \(\mathbf {b}\) and \(\mathbf {w}\) by \(ZO(A,\mathbf {b},\mathbf {z})\). Every instance of the mwhvc problem is a zero-one program in which the matrix A is the incidence matrix of the hypergraph. The following lemma deals with the converse reduction.

How does N(ILP) (a bipartite graph with \(m+n\) vertices) simulate the execution of mwhvc over the hypergraph H? Each variable node \(x_j\) simulates all hyperedges \(e_{i,S}\), where \(j\in \sigma _i\) and \(S\in \mathcal {S}_i\). First, the variable nodes exchange their weights with the variables nodes they share a constraint with in O(f(A)) rounds – first every \(x_j\) broadcasts its own weight and then each \(c_i\) sends all neighbors the weights it received. At each iteration, the variable node sends a raise/stuck message and whether its level was incremented.⁵ Notice that the number of rounds required for each such iteration is \(O(1+f(A)/\log n)\) (i.e., constant for \(f(A)=O(\log n)\)). Each edge node \(c_i\) then broadcasts to all vertices two f(A)-bit messages that indicate two subsets of vertices of the edge: those that sent a raise message (the complement sent a stuck message) and those that incremented their level. Each variable node \(x_j\) knows how to update its bid with every \(e_{i,S}\) for which \(j\in \sigma _i\) and \(S\in \mathcal {S}_i\).

We summarize the complexity of the distributed algorithm for solving a zero-one covering program.

Consider the covering ILP \(ILP(A,\mathbf {b},\mathbf {w})\). We present a reduction of the ILP to a zero-one covering program.

We abbreviate and write M for \(M(A,\mathbf {b})\) when the context is clear.

Combining Claims 5 and 6 , we obtain the following result.

After some simplifications, the running time of the resulting algorithm for \((f\cdot \lceil \log _2(M)+1 \rceil +\varepsilon )\)-approximate integer covering linear programs is