Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs

We start by establishing a tight bound for computing a $(1-\epsilon )$-approximation in trees.

The lower bound is based on a relatively simple reduction from the MCIS problem in paths [8, 16]. The condition $\epsilon >\log (n)/n$ is a technical condition because for arbitrary $\epsilon >0$, the lower bound becomes $\mathrm{\Omega }({\log }^{\ast }(\epsilon n)/\epsilon )$.

The upper bound is based on ideas that were developed for planar graphs in [8] and which are based the following core idea. First, one defines a weight function on edges, where for $\{u,v\}\in E$, we set $w(\{u,v\}):=\min \{w(u),w(v)\}$. The algorithm of [8] then computes a clustering of the nodes of $V$ such that the total weight of the edges connecting nodes in different clusters is at most an $\epsilon /2$-fraction of the total weight of all the edges. By computing an optimal weighted independent set within each cluster, one can then obtain a $(1-\epsilon )$-approximate MWIS solution of the given instance. The independent sets of the clusters are combined by taking the union and removing the smaller weight node of every intercluster edge. The clustering algorithm of [8] obtains clusters of diameter $\text{poly}({\epsilon }^{-1})$ in time $\text{poly}({\epsilon }^{-1})\cdot O({\log }^{\ast }n)$ in the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model. In trees, the clustering algorithm of [8] can be implemented in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model. Further, in trees, an optimal MWIS solution inside each cluster can be computed in time linear in cluster diameter by using a straightforward dynamic programming algorithm. The core challenge for proving the upper bound of Theorem 1 is to obtain a clustering algorithm in which the maximum cluster diameter is only $O(1/\epsilon )$. The algorithm of [8] consists of basic steps in which the cluster diameter grows by constant factor and the total weight of the intercluster edges shrinks by a constant factor. The cluster diameter however grows by a factor that is larger than the factor by which the total weight of the intercluster edges decreases. In our algorithm, we show that in trees, one can interleave those basic steps of [8] with steps in which the clusters are split into clusters of smaller diameter, without increasing the overall weight of the intercluster edges by too much.

For the remainder of this section, we assume that we are given a graph $G=(V,E)$ of arboricity $\beta$. In [14], it is shown that there is a deterministic $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ algorithm to compute an independent set of weight at least $\frac{w(V)}{(4+\epsilon )\dot{\beta }}$ in randomized time $O\left(\frac{\log n\cdot \text{poly}\log \log n}{\epsilon }\right)$ and in combination with an algorithm from [9] in deterministic time $O\left(\frac{{\log }^2\beta \cdot \log (1/\epsilon )\cdot \log n}{\epsilon }\right)$. In the following, we show that for moderately small $\beta$ both those bounds can be improved significantly.

The theorem can be proven by a relatively straightforward blackbox application of the local rounding framework of [9]. More concretely, we can show that Theorem 2 follows almost directly from Lemma 4.2 in [9]. Theorem 2 implies a $\frac{1-\epsilon }{4\beta }$-approximation of MWIS. In [12], it is shown that a $\frac{1}{\lfloor (2+\epsilon )\beta \rfloor }$-approximation can be computed deterministically in $O\left(\frac{\beta \cdot \log n}{\epsilon }\right)$ $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ rounds. For $\epsilon =1/o(\sqrt{\beta })$, we significantly improve on this bound as stated by the following theorem.

A major step towards proving Theorem 3 is an efficient algorithm to compute an independent set of weight arbitrarily close to a natural weighted generalization of the Caro-Wei bound (1). Specifically, we prove the following theorem.

Before discussing the main ideas needed to prove, Theorem 4, we discuss its direct application to approximating the maximum cardinality independent set problem in graphs of arboricity $\beta$. As proven in [6] and discussed in Section 1.2, the Caro-Wei bound (1) provides a $\frac{2\cdot (\sqrt{2}-1)}{\beta +1}$-approximation to the maximum cardinality independent set problem in graphs of arboricity $\beta$. Theorem 4 thus implies that such an approximation can be computed in $O\left(\frac{{\log }^3(\mathrm{\Delta })\cdot \log (1/\epsilon )}{\epsilon }+{\log }^{\ast }n\right)$ rounds in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model. This can be further improved slightly. Because in a graph $G$ of arboricity $\beta$, the average degree is at most $2\beta$, the number of nodes of degree $>c\cdot {\beta }^2/\epsilon$ is at most $2\epsilon n/(c\beta )$, which can be shown to be at most $4\epsilon /c\cdot \alpha (G)$, where $\alpha (G)$ denotes the independence number of $G$. It therefore suffices to apply Theorem 4 to the subgraph induced by the nodes of degree at most $c{\beta }^2/\epsilon$ for a sufficiently large constant $c$. We thus obtain the following corollary.

We next sketch how Theorem 4 is proven and how it is used to prove Theorem 3. The starting point to proving Theorem 4 is an $O\left(\frac{{\log }^2\mathrm{\Delta }\cdot \log (1/\epsilon )}{\epsilon }+{\log }^{\ast }n\right)$-round algorithm from [9] to compute an independent set of weight at least $(1-\epsilon )\cdot \frac{w(V)}{\mathrm{\Delta }+1}$ in a graph of maximum degree $\mathrm{\Delta }$. The idea now is to divide the nodes of $G$ into $O(\log (\mathrm{\Delta })/\epsilon )$ degree classes so that the degrees within one class differ by at most a factor $1+\epsilon$. We then want to essentially apply the algorithm from [9] separately for each degree class, starting from the small degrees. This would work almost directly for unweighted graphs. To make it work, one just has to include all the still available nodes from the lower degree classes when computing the independent set of some degree class.

For weighted graphs, sequential composition of independent set is a bit more tricky. We can however utilize a technique developed in the context of the local-ratio method [2] and used in the context of distributed MWIS approximation in [3, 14, 9]. Given a graph $G$ with node weights $w(v)$ and an independent set $I_0$, one can define a new weight function $w^{\prime }(u):=\max \{0,w(u)-w(I_0\cap N^{+}(u))\}$, where $N^{+}(u)$ denotes the inclusive neigborhood of $u$. If one then computes a second independent set $I^{\prime }$ consisting only of nodes $v$ for which $w^{\prime }(v)>0$, the combined independent set $I:=I^{\prime }\cup (I_0\setminus N^{+}(I^{\prime }))$ is guaranteed to have a total weight of at least $w(I_0)+w^{\prime }(I^{\prime })$ (w.r.t. to the original weight function $w(\cdot )$). In this way, we can iterate through the $O(\log n/\epsilon )$ degree classes in a similar way as in the unweighted case to obtain an independent set satisfying the requirements for Theorem 4.

We next discuss our algorithm to obtain the bound claimed by Theorem 3. Note that since the average degree of a graph of arboricity $\beta$ can be almost $2\beta$, we might have to compute an independent set of weight close to $w(V)$ divided by the average degree. There are graphs of arboricity $\beta$ for which this is best possible (e.g., unweighted cliques) and we therefore in some cases cannot afford to allow too much “slack” when iteratively computing an independent set. A standard tool to algorithmically deal with graphs of bounded arboricity is the so-called $H$-decomposition as introduced in [4]. Because the average degree of a graph with arboricity $\beta$ is at most $2\beta$, the number of nodes of degree more than $(2+\epsilon )\beta$ is at most $(1-\mathrm{\Theta }(\epsilon ))\cdot n$. When peeling off all nodes of degree at most $(2+\epsilon )\beta$, we therefore get rid of a $\mathrm{\Theta }(\epsilon )$-fraction of all the nodes. Repeating this idea gives a decomposition of the graph into $O(\log (n)/\epsilon )$ layers so that the nodes in each layer have at most $(2+\epsilon )\beta$ neighbors in the same layer and higher layers. We are not aware of an algorithm to compute an independent set of weight close to $w(V)/(2\beta )$ that does not at least implicitly use an $H$-decomposition (which in most cases leads to a time complexity that is at least linear in the number of layers $\mathrm{\Theta }(\log (n)/\epsilon )$).

The highlevel idea of our approach is the following. We again use the framework of [2, 3, 14] to iteratively construct an independent set in the weighted setting. Because the nodes in the lowest layer are always the ones of bounded degree, we start our iterative construction at the lowest layer and work our way up the decomposition. Some of the main challenges with this approach already appear for the unweighted case and in the following highlevel discussion, we therefore focus on this case. Let $V_0$ be the nodes of the lowest layer of our decomposition. All nodes in $V_0$ have degree at most $(2+\epsilon )\beta$ and we can therefore compute an independent set $I_0\subseteq V_0$ of size close to $|V_0|/(2\beta )$ (or even close to the Caro-Wei bound (1) within $V_0$). However, even if the independent set $I_0$ is relatively large, it could consist of nodes that mostly have neighbors in $V\setminus V_0$ so that a lot of nodes in $V_0$ have no neighbor in $I_0$. When moving to the next layer, we can however not include any remaining nodes in $V_0$ because this might create some high degree nodes in the layer, we are considering. Our goal therefore should be to select an independent set $I_0$ in $V_0$ such that it removes most of the nodes in $V_0$. As an estimate of the number of removed nodes in $V_0$, we use ${\sum }_{v\in I_0}({\mathrm{deg}}_0(v)+1)$, where ${\mathrm{deg}}_0(v)$ is the degree of $v$ within $V_0$. If this sum is close to $|V_0|$, we are guaranteed to make sufficient progress (even if many nodes of $V_0$ remain because other nodes in $V_0$ have multiple neighbors in $I_0$). We can compute such an independent set $I_0$ as follows. We define a weight $\overline{w}(v):={\mathrm{deg}}_0(v)+1$ for each node $v\in V_0$. Note that for an independent set $I_0$, we have $\overline{w}(I_0)={\sum }_{v\in I_0}({\mathrm{deg}}_0(v)+1)$. By using Theorem 4, we can compute an independent set $I_0$ of total weight $\overline{w}(I_0)\approx {\sum }_{v\in V_0}\frac{\overline{w}(v)}{{\mathrm{deg}}_0(v)+1}=|V_0|$, which is exactly what we need.