# Faster Deterministic Distributed MIS and Approximate Matching

Mohsen Ghaffari
MIT
<EMAIL_ADDRESS>Christoph Grunau
ETH Zurich
<EMAIL_ADDRESS>
###### Abstract

We present an $\widetilde{O}(\log^{2}n)$ round deterministic distributed
algorithm for the maximal independent set problem. By known reductions, this
round complexity extends also to maximal matching, $\Delta+1$ vertex coloring,
and $2\Delta-1$ edge coloring. These four problems are among the most central
problems in distributed graph algorithms and have been studied extensively for
the past four decades. This improved round complexity comes closer to the
$\widetilde{\Omega}(\log n)$ lower bound of maximal independent set and
maximal matching [Balliu et al. FOCS ’19]. The previous best known
deterministic complexity for all of these problems was $\Theta(\log^{3}n)$.
Via the shattering technique, the improvement permeates also to the
corresponding randomized complexities, e.g., the new randomized complexity of
$\Delta+1$ vertex coloring is now $\widetilde{O}(\log^{2}\log n)$ rounds.

Our approach is a novel combination of the previously known (and seemingly
orthogonal) two methods for developing fast deterministic algorithms for these
problems, namely global derandomization via network decomposition (see e.g.,
[Rozhon, Ghaffari STOC’20; Ghaffari, Grunau, Rozhon SODA’21; Ghaffari et al.
SODA’23]) and local rounding of fractional solutions (see e.g., [Fischer
DISC’17; Harris FOCS’19; Fischer, Ghaffari, Kuhn FOCS’17; Ghaffari, Kuhn
FOCS’21; Faour et al. SODA’23]). We consider a relaxation of the classic
network decomposition concept, where instead of requiring the clusters in the
same block to be non-adjacent, we allow each node to have a small number of
neighboring clusters. We also show a deterministic algorithm that computes
this relaxed decomposition faster than standard decompositions. We then use
this relaxed decomposition to significantly improve the integrality of certain
fractional solutions, before handing them to the local rounding procedure that
now has to do fewer rounding steps.

###### Contents

  1. 1 Introduction
    1. 1.1 State of the Art
    2. 1.2 Our Results
    3. 1.3 Other Related Work
  2. 2 Our Approach
    1. 2.1 The previous methods and their barriers
    2. 2.2 Low-diameter low-degree clusterings
    3. 2.3 Interplay between global computations via clustering and local rounding
    4. 2.4 Construction of the clustering, and hitting set with pipelining
  3. 3 Preliminaries
    1. 3.1 Definitions and Basic Inequalities
    2. 3.2 The local rounding framework
    3. 3.3 The hitting set subroutines
  4. 4 Clustering
    1. 4.1 Clustering with Constant Fraction Good
    2. 4.2 Clustering with all Nodes Good
  5. 5 Matching and MIS
    1. 5.1 Approximate Matching
    2. 5.2 MIS
  6. A The deterministic hitting set algorithm of Lemma 3.4
    1. A.1 A basic hitting set algorithm
    2. A.2 The hitting set algorithm of Lemma 3.4

##  1 Introduction

In this paper, we present a faster deterministic distributed algorithm for the
Maximal Independent Set (MIS) problem, which is one of the most central
problems in distributed graph algorithms and has been studied extensively for
the past four decades. This improvement has implications for several other
problems. Our main novelty is a technique that combines the two previously
known general approaches, which seemed unrelated and incompatible hitherto. We
are hopeful that this new technique finds applications in a wider range of
problems. We next set up the context, and then discuss our results and
approach.

#### Distributed Model:

We work with the standard synchronous message-passing model of distributed
computing, often referred to as the $\mathsf{LOCAL}$ model, due to Linial
[Lin87]. The network is abstracted as an $n$-node undirected graph $G=(V,E)$,
where each node represents one processor and a link between two nodes
indicates that those two processors can communicate directly. Each processor
has a unique $b$-bit identifier, where we typically assume $b=O(\log n)$.
Initially, nodes do not know the topology of the network $G$, except for
potentially knowing some global parameters such as a polynomial upper bound on
$n$. Computations and communications take place in synchronous rounds. Per
round, after doing arbitrary computations on the data that it holds, each
process/node can send one message to each of its neighbors. In the
$\mathsf{LOCAL}$ model, the message sizes are not bounded. The model variant
where message sizes are limited to $O(\log n)$-bits is known as the
$\mathsf{CONGEST}$ model[Pel00]. The messages sent in a round are delivered
before the end of that round. At the end of the computation, each node should
know its own output, e.g., in the MIS problem, each node should know whether
it is in the computed maximal independent set or not.

###  1.1 State of the Art

#### Randomized algorithms, and the pursuit of deterministic algorithms.

In the 1980s, Luby[Lub86] and Alon, Babai, and Itai[ABI86] presented a simple
and elegant randomized distributed algorithm that computes an MIS in $O(\log
n)$ rounds, with high probability111As standard, the phrase with high
probability indicates that an event happens with probability at least
$1-1/n$.. Due to known reductions, this MIS algorithm led to $O(\log n)$ round
randomized algorithms for many other key graph problems, including maximal
matching, $\Delta+1$ vertex coloring, and $(2\Delta-1)$ edge coloring. These
problems are often listed as the four fundamental symmetry-breaking problems
in distributed graph algorithms and have a wide range of applications. The
$O(\log n)$-round randomized algorithm naturally led the researchers to seek a
deterministic distributed algorithm with the same round complexity. In his
celebrated work [Lin87, Lin92], Linial asked “can it [MIS] always be found in
polylogarithmic time [deterministically]?” He even added that “getting a
deterministic polylog-time algorithm for MIS seems hard.” Since then, this
became known as Linial’s MIS question and turned into one of the research foci
in distributed graph algorithms.

#### The two approaches of deterministic algorithms.

Linial’s MIS problem remained open for nearly three decades. During this time,
two different general approaches were developed and pursued. The first
approach relies on global computations/derandomization via network
decompositions. The second approach is based on local rounding of certain
fractional solutions. Over the past couple of years, both approaches came to
fruition and led to two completely independent polylogarithmic time
deterministic distributed algorithms for MIS [RG20, FGG+23]. The round
complexities are still $\widetilde{\Omega}(\log^{3}n)$, which is somewhat far
from the randomized $O(\log n)$ complexity [Lub86, ABI86]. We next discuss
each approach separately.

#### (I) Global computation/derandomization via network decomposition.

The first approach is based on the concept of network decomposition, which was
introduced by Awerbuch, Goldberg, Luby, and Plotkin [AGLP89] as the key tool
in developing deterministic distributed algorithms for MIS and other symmetry-
breaking problems. A $(c,d)$ network decomposition is a partition of the
vertex set into $c$ disjoint parts, each known as a block, such that in the
subgraph induced by the nodes in each block, each connected component has a
diameter of at most $d$. Said differently, each block consists of non-adjacent
clusters, each of diameter222If the diameter is measured in the induced
subgraph, this is known as a strong-diameter network decomposition. If the
distance is measured in the original graph, this is known as a weak-diameter
network decomposition. at most $d$. Given a $(c,d)$ network decomposition, it
is easy to compute an MIS in $O(cd)$ rounds: The rounds are organized in $c$
iterations, each consisting of $O(d)$ rounds. In iteration $i$, we add to the
output independent set an MIS of the nodes of block $i$, which can be computed
easily in $O(d)$ rounds as each cluster in the block has a diameter of at most
$d$. We then remove any node in any other block that has a neighbor in this
independent set and then move to the next iteration. Any $n$-node graph has a
$(c,d)$ network decomposition for $c=d=O(\log n)$ [Awe85]. Awerbuch et
al.[AGLP89] gave a deterministic distributed algorithm that computed a $(c,d)$
decomposition in $t$ rounds for $c=d=t=2^{O(\sqrt{\log n\log\log n})}$. These
bounds were improved to $2^{O(\sqrt{\log n})}$ by Panconesi and Srinivasan
[PS92]. By a technique of Awerbuch, Berger, Cowen, and Peleg [ABCP96], one can
transform any $t$-round $(c,d)$ decomposition algorithm to a
$(t+cd)\cdot\operatorname{\text{{\rm poly}}}(\log n)$-round $(\log n,\log n)$
network decomposition algorithm in the $\mathsf{LOCAL}$ model.

The $2^{O(\sqrt{\log n})}$ bounds of Panconesi and Srinivasan remained the
state of the art for over 25 years, until getting improved dramatically to
$\operatorname{\text{{\rm poly}}}(\log n)$ by a new decomposition algorithm of
Rozhon and Ghaffari [RG20]. That gave the first polylogarithmic-time
deterministic distributed algorithm for MIS, and thus the first positive
resolution to Linial’s MIS question. The algorithm was optimized in a follow-
up work of Ghaffari, Grunau, and Rozhon [GGR21], which brought down MIS’s
deterministic round complexity to $O(\log^{5}n)$. See also [CG21, EHRG22]
which obtain strong-diameter guarantees with small messages. In a very recent
work, Ghaffari, Grunau, Haeupler, Ilchi, and Rozhon [GGH+23] presented a
completely different and faster method for computing network decompositions.
Their algorithm computes a $(c,d)$ strong-diameter network decomposition for
$c=O(\log n)$ and $d=O(\log n\cdot\log\log\log n)$ in
$\widetilde{O}(\log^{3}n)$ rounds, using $O(\log n)$-bit messages. This is the
state of art decomposition in essentially all regards, and it provides an
$\widetilde{O}(\log^{3}n)$ round deterministic algorithm for MIS.

#### (II) Local rounding of fractional solutions.

The second approach is based on obtaining fractional solutions to certain
relaxations of the problem and then, locally and gradually rounding these
solutions into integral solutions. Unlike the network decomposition approach,
which was obviously applicable to all the symmetry-breaking problems from the
start, the applicability of the rounding approach appeared limited at first
and gradually increased. It started first with only the maximal matching
problem, then extended to $2\Delta-1$ edge coloring, then to $\Delta+1$ vertex
coloring, and finally to the hardest of all, the MIS problem.

The starting point is the work of Hanckowiak, Karonski, and Panconesi [HKP01]
who gave the first $\operatorname{\text{{\rm poly}}}\log n$-time deterministic
distributed algorithm for the maximal matching problem. Fischer[Fis20]
rephrased their approach in a rounding language and used this to improve the
maximal matching complexity to $O(\log^{2}\Delta\cdot\log n)$.

Fischer’s rounding was very specific to matching in graphs. Fischer, Ghaffari,
and Kuhn[FGK17] developed a different rounding method for matchings that
extended to low-rank hypergraphs. By a reduction that they provided from
$(2\Delta-1)$-edge coloring in graphs to maximal matching in hypergraphs of
rank $3$, this led to a $\operatorname{\text{{\rm poly}}}\log n$-time
deterministic algorithm for $(2\Delta-1)$-edge coloring, hence putting the
second problem in the $\operatorname{\text{{\rm poly}}}(\log n)$ regime.
Harris[Har19] improved the complexity to
$\widetilde{O}(\log^{2}\Delta\cdot\log n)$.

The above local rounding approaches appeared limited to matching in graphs or
hypergraphs, until a work of Ghaffari and Kuhn [GK21]. They developed an
efficient rounding method for $\Delta+1$ coloring (this was shortly after the
first polylogarithmic-time network decomposition result [RG20]). This was by
reexamining the analysis of the natural randomized coloring algorithm, seeing
it as a fractional/probabilistic assignment of colors to the nodes which has a
small bound on the expected number of monochromatic edges, and then gradually
rounding the fractional assignments while approximately maintaining the upper
bound on the expected number of monochromatic edges.

Finally, in a very recent work, Faour, Ghaffari, Grunau, Kuhn, and Rozhon
[FGG+23] found a significant generalization of the above local roundings. They
presented a unified method that can provide local rounding for any problem
whose randomized solution analysis relies on only pairwise independence. This
led to algorithms with round complexity $O(\log^{2}\Delta\log n)$ for MIS and
thus also for the other three problems mentioned above, and in a unified way.

###  1.2 Our Results

#### Unifying the two approaches and faster deterministic MIS.

As discussed above, prior to the present paper, the best known deterministic
complexity of MIS (and indeed any of the other three key symmetry breaking
problems) remained $\Omega(\log^{3}n)$[GGH+23, FGG+23]. This is somewhat far
from the randomized $O(\log n)$ round complexity [Lub86, ABI86]. Furthermore,
the two approaches seemed unrelated and incompatible. In this paper, we
present a method to combine the two general approaches, which allows us to
achieve a deterministic round complexity of $\widetilde{O}(\log^{2}n)$ for
MIS.

######  Theorem 1.1.

There is a deterministic distributed algorithm, in the $\mathsf{LOCAL}$ model,
that computes a maximal independent set (MIS) in $\widetilde{O}(\log^{2}n)$
rounds. This also implies that there are $\mathsf{LOCAL}$-model deterministic
distributed algorithms with $\widetilde{O}(\log^{2}n)$ rounds complexity also
for maximal matching, $(deg+1)$-list vertex coloring, and $(2deg-1)$-list edge
coloring333In the $(deg+1)$-list vertex coloring, each node $v$ having a
prescribed list $L_{v}$ of colors, of size $|L_{v}|\geq deg(v)+1$ from which
it should choose its color. In the $(2deg-1)$-list edge coloring, each edge
$e=\\{v,u\\}$ has a prescribed list $L_{e}$ of colors, of size $|L_{e}|\geq
deg(v)+deg(u)-1$ from which it should choose its color. Both problems reduce
to MIS by a reduction of Luby [Lub86, Lin92]..

This comes closer to the $\widetilde{\Omega}(\log n)$ lower bound, due to
Balliu et al.[BBH+19], which holds for deterministic distributed algorithms
that compute maximal independent set or maximal matching.

#### Faster approximate maximum matching.

Our method also leads to a faster deterministic algorithm for computing a
constant approximation of the maximum matching, in
$\widetilde{O}(\log^{4/3}n)$ rounds. By adding to this the approximation
booster of Fischer, Mitrovic, and Uitto [FMU22], we can improve the
approximation to $(1+\epsilon)$ for any desirably small constant $\epsilon>0$
with no asymptotic round complexity loss. The previous best round complexity
for constant approximation of the maximum matching was $O(\log^{2}\Delta)$
[Fis20, FGG+23].

######  Theorem 1.2.

There is a deterministic distributed algorithm, in the $\mathsf{LOCAL}$ model,
that computes a $\Theta(1)$-approximate maximum matching in
$\widetilde{O}(\log^{4/3}n)$ rounds. This can be boosted to an algorithm that
computes a $(1+\epsilon)$ approximation of maximum matching in
$\widetilde{O}(\log^{4/3}n)\cdot\operatorname{\text{{\rm poly}}}(1/\epsilon)$
rounds.

#### Corollaries for randomized coloring.

Our faster deterministic algorithm can be plugged in into the shattering
framework of randomized algorithms[Bar12, CLP18] and improves the randomized
complexity for $\Delta+1$ vertex coloring and $2\Delta-1$ edge coloring.

######  Corollary 1.3 (LABEL:{thm:mis}+[CLP18]).

There is a randomized distributed algorithm, in the $\mathsf{LOCAL}$ model,
that computes a $\Delta+1$ vertex coloring in $\widetilde{O}((\log\log
n)^{2})$ rounds. The same holds also for the $2\Delta-1$ edge coloring
problem.

###  1.3 Other Related Work

We discussed in Section 1.1 deterministic constructions for network
decomposition and the generic method of using network decomposition for
symmetry-breaking problems, e.g., MIS. Let us add here three side comments and
mention the related work.

(1) Better randomized constructions for network decomposition have been known.
In particular, the work of Linial and Saks [LS93] presented an $O(\log^{2}n)$
round randomized algorithm for computing decompositions with $O(\log n)$
colors and $O(\log n)$ weak diameter. Elkin and Neiman [EN16] imported a
parallel algorithm of Miller, Peng and Xu [MPX13] into the distributed setting
and obtained an $O(\log^{2}n)$ round randomized algorithm for computing
decompositions with $O(\log n)$ colors and $O(\log n)$ strong diameter.

(2) The deterministic MIS method described in Section 1.1 for using network
decompositions in computing symmetry-breaking problems such as MIS would
require large messages, as it gathers the topology of each cluster in a
center. For MIS, one can work with $O(\log n)$-bit messages, by using a
derandomization method of Censor-Hillel, Parter, and Schwartzman [CHPS20], and
that gives a deterministic algorithm with $O(\log n)$-bit messages and round
complexity $O(cd)\cdot\operatorname{\text{{\rm poly}}}(\log n)$. Similar
approaches have been presented for other problems, see e.g., Bamberger et al.
[BKM20] for results on $\Delta+1$ coloring.

(3) Ghaffari, Harris, and Kuhn [GHK18] and Ghaffari, Kuhn and Maus [GKM17]
showed that one can get a general derandomization method for the
$\mathsf{LOCAL}$ model using network decompositions. This method transforms
any $\operatorname{\text{{\rm poly}}}(\log n)$-round randomized algorithm for
any problem whose solution can be checked in $\operatorname{\text{{\rm
poly}}}(\log n)$ rounds into a deterministic algorithm with round complexity
$O(cd+t)\cdot\operatorname{\text{{\rm poly}}}(\log n)$, assuming we have a
deterministic $(c,d)$ network decomposition algorithm with round complexity
$t$.

##  2 Our Approach

To discuss our approach and put it in the context of prior work, let us use
the problem of maximal matching. This is a special case of the maximal
independent set problem (on line graphs), but it will suffice for explaining
most of the key ideas in our overall approach.

###  2.1 The previous methods and their barriers

As mentioned before, the previous two approaches for deterministic algorithms
both get stuck at a round complexity of $\widetilde{O}(\log^{3}n)$. Let us
briefly overview the approaches and their barriers here. This discussion will
help us explain how we obtain a faster algorithm.

#### Local rounding of fractional solutions.

For maximal matching, Fischer [Fis20] and Faour et al. [FGG+23] provide two
different local rounding algorithms, both achieving an $O(\log^{2}\Delta\log
n)$ complexity. Both round complexities are stuck at essentially the same
barrier, so we discuss only Fischer’s approach. It is easy to
deterministically obtain a constant-approximate fractional matching in
$O(\log\Delta)$ rounds444Start with a fractional assignment of
$x_{e}=1/\Delta$ to all edges. Then, we have $\log\Delta$ iterations. Per
iteration, for each edge $e$ such that each endpoint $v$ of it has
$\sum_{e^{\prime}\ni v}x_{e^{\prime}}\leq 1/2$, set $x_{e}\leftarrow 2x_{e}.$
[Fis20]. The real challenge for deterministic algorithms is in rounding this
fractional matching into an integral matching. Fischer [Fis20] gradually
improves the integrality of the fractional solution from $1/\Delta$ to $1$, in
$\log\Delta$ gradual rounding steps, each time doubling the minimum edge
value. Each doubling step in the algorithm takes
$\Theta(1/\varepsilon)=\Theta(\log\Delta)$ rounds, as we need to ensure that
there is a loss of at most $\epsilon=1/(2\log\Delta)$ fraction in the matching
size, so that the total loss over all the $\log\Delta$ iterations is at most a
constant. One can see that, for an arbitrary fractional matching, this
$\Theta(1/\varepsilon)$ complexity is the best possible555Here is an intuitive
and informal explanation: Consider a long path of edges, each with fractional
value $1/2$. We would like to raise some edge values to $1$ while dropping
others to $0$, and while ensuring that the total size is still a
$1-\varepsilon$ factor of the previous fractional size. Intuitively, starting
from one edge, the edges should be alternating in $0$ and $1$ value until we
go at least $1/\varepsilon$ far. Otherwise, we have had more than an
$\varepsilon$ relative loss in this part. This strict alternation for
$1/\varepsilon$ distance requires $\Omega(1/\varepsilon)$ rounds.. Considering
the $\log\Delta$ gradual rounding steps, this yields a constant-approximate
integral matching in $O(\log^{2}\Delta)$ rounds. We emphasize that this
runtime is quadratic in the number of rounding steps, as we need to ensure
that the relative loss per step is less than the inverse of the number of
steps. Via $O(\log n)$ repetitions of constant-approximate maximum matching,
each time on the subgraph induced by vertices that remained unmatched, one
gets a maximal matching with complexity $O(\log^{2}\Delta\cdot\log n)$.

#### Global computation via network decomposition.

The state-of-the-art network decomposition algorithm [GGH+23] computes a
decomposition with $O(\log n)$ vertex-disjoint blocks, where the subgraph
induced by each block consists of connected components of diameter
$\widetilde{O}(\log n)$, in $\widetilde{O}(\log^{3}n)$ rounds. Given this, it
is easy to compute maximal matching or MIS in $\widetilde{O}(\log^{2}n)$
rounds. But the construction time is the bottleneck in these applications.

Let us revisit this decomposition-based approach for the constant-approximate
maximum matching problem. This discussion will help us later to explain our
approach. As discussed above, $O(\log n)$ repetitions of constant-approximate
maximum matching give a maximal matching. Consider a constant-approximate
fractional maximum matching. As mentioned above, we know how to compute this
easily in $O(\log\Delta)$ rounds. The task is to turn this into an integral
matching of the same size, up to a constant factor. The network decomposition
algorithm [GGH+23] computes the blocks one by one, each in
$\widetilde{O}(\log^{2}n)$ rounds, such that each block clusters a constant
fraction of the remaining nodes into non-adjacent clusters, each of diameter
$\widetilde{O}(\log n)$. We can adjust the block construction in such a way
that, instead of a constant fraction of nodes getting clustered, we ensure
that at least a constant fraction of the weight of the fractional matching is
on the edges inside the clusters. It is easy to see that randomized rounding
can turn (each cluster’s) fractional matching into an integral matching of the
same size up to a constant factor. So, to deterministically do the rounding,
we can simply gather each cluster’s information (and constraints) into the
cluster center and compute the integral matching. This takes
$\widetilde{O}(\log n)$ rounds, as the cluster diameter is $\widetilde{O}(\log
n)$. It is worth noting that the current method for building each block of the
decomposition requires $\widetilde{O}(\log^{2}n)$ rounds, as it has
$\widetilde{O}(\log n)$ steps of randomness fixing, each involving
coordination along $\widetilde{O}(\log n)$-hop distances.

###  2.2 Low-diameter low-degree clusterings

In our approach, we work with a relaxed variant of the standard network
decompositions. In particular, we work with clusterings that have a lower
diameter than the standard $\Theta(\log n)$ bound. This opens the road for
faster deterministic constructions. However, it comes at the disadvantage that
we do not have only $\log n$ blocks, each consisting of non-adjacent clusters.
We instead maintain a small bound on the maximum number of clusters that are
adjacent to each particular node. To state the formal decomposition, let us
first present the formal definitions.

######  Definition 2.1.

[Cluster, Clustering, Partition, Cluster Degree of a Vertex, Diameter of a
Cluster] A subset $C\subseteq V$ is called a cluster. The (strong)-diameter of
a cluster is defined as $\max_{u,v\in C}d_{G[C]}(u,v)$. A clustering
$\mathcal{C}$ is a set of disjoint clusters. We refer to $\mathcal{C}$ as a
partition if $\bigcup_{C\in\mathcal{C}}C=V$. The diameter of a clustering
$\mathcal{C}$ is defined as the maximum diameter of all its clusters. For a
node $u\in V$ and a clustering $\mathcal{C}$, we define the degree of $u$ with
respect to $\mathcal{C}$ as $deg_{\mathcal{C}}(u)=|\\{C\in\mathcal{C}\colon
d(C,u)\leq 1\\}|$. We sometimes refer to $\max_{u\in V}\deg_{\mathcal{C}}(u)$
as the degree of this clustering.

We show an algorithm that computes $O(\alpha)$-diameter
$(2^{\widetilde{O}(\log n)/\alpha})$-degree clusterings in
$\widetilde{O}(\alpha^{2}\log n)$ rounds of the $\mathsf{LOCAL}$ model.

######  Theorem 2.1.

Let $\alpha\leq\log n$ be an arbitrary value. There exists a deterministic
distributed algorithm that in $\widetilde{O}(\alpha^{2}\log n)$ rounds of the
$\mathsf{LOCAL}$ model computes a partition $\mathcal{C}$ with

  1. 1.

diameter $O(\alpha)$ and

  2. 2.

$\max_{u\in V}\deg_{\mathcal{C}}(u)=2^{\widetilde{O}(\log n)/\alpha}$, i.e.,
each node has neighbors in at most $2^{\widetilde{O}(\log n)/\alpha}$
clusters.

We note that the existence of such a clustering/partition, and even efficient
randomized constructions for it, follow from known randomized methods [MPX13].
We provide an efficient deterministic distributed construction here, as we
outline in Section 2.4. Furthermore, we show that this relaxed notion is still
useful for applications in the maximal independent set and maximal matching
problems, as we next outline in Section 2.3.

As a side comment, we note that for some applications (e.g., approximate-
matching), it suffices to have a weaker version of Theorem 2.1 where only a
constant fraction of nodes (or a constant fraction of the weight of the nodes,
according to some given weights) is clustered. For that version, we have a
faster algorithm that runs in $\widetilde{O}(\alpha\log n)$ rounds of the
$\mathsf{LOCAL}$ model. The precise statement is as follows.

######  Theorem 2.2.

Let $\alpha\leq\log n$ be an arbitrary value and assume that each node $u\in
V$ is equipped with a value $x_{u}\in\left[\frac{1}{n},1\right]$. There exists
a deterministic distributed algorithm that in $\widetilde{O}(\alpha\log n)$
rounds of the $\mathsf{LOCAL}$ model computes a partition $\mathcal{C}$ with

  1. 1.

diameter $O(\alpha)$ and

  2. 2.

let $V^{good}=\\{u\in V\colon deg_{\mathcal{C}}(u)=2^{\widetilde{O}(\log
n)/\alpha}\\}$, then we have $\sum_{u\in V^{good}}x_{u}\geq 0.9\sum_{u\in
V}x_{u}$.

###  2.3 Interplay between global computations via clustering and local
rounding

Let us now revisit the maximal matching problem. Here, we provide an intuition
of how we solve this problem in $\widetilde{O}(\log^{2}n)$ rounds, by
combining the two approaches. First, we invoke Theorem 2.1 for
$\alpha=\sqrt{\log n}$ and compute a partition $\mathcal{C}$ into clusters of
diameter $O(\sqrt{\log n})$ such that each node has
$d=2^{\widetilde{O}(\sqrt{\log n})}$ neighboring clusters, in $O(\log^{2}n)$
rounds. This vertex partition also induces an edge partition
$E=\sqcup_{C\in\mathcal{C}}E_{C}$ where $E_{C}$ contains all edges whose
endpoint with the larger identifier is in $C$. Now, we use this clustering to
gradually compute the maximal matching in $O(\log n)$ iterations. In each
iteration, we first compute a constant-approximate fractional matching in the
graph induced by the unmatched vertices in $O(\log\Delta)=O(\log n)$ rounds
[Fis20]. Then, the key part of the iteration is to turn this into a constant-
approximate integral matching in $\widetilde{O}(\log n)$ additional rounds.
For that, we use the clustering to quickly perform a significant rounding of
the fractional matching. In particular, the value assigned to a given edge
$e\in E_{C}$ after the rounding is fully determined by the fractional values
assigned to the edges in $E_{C}$ before the rounding. Thus, this initial
rounding can be computed in just $O(\sqrt{\log n})$ rounds. Afterward, we will
resort to local rounding which now needs only $\widetilde{O}(\sqrt{\log n})$
doubling steps and thus can be performed in $\widetilde{O}(\log n)$ rounds.
Let us elaborate.

First, we divide all the fractional matching values by a $4$ factor, so that
now each node $v$ has $\sum_{e^{\prime}\ni v}x_{e^{\prime}}\leq 1/4$. Then,
for the rounding, for each node $v$ and cluster $C$, we allow the summation of
the edges in $E_{C}$ incident to $v$ to increase from the original value by a
multiplicative factor of $2$ and, on top of that, an additive increase of
$1/(2d)=1/2^{\widetilde{\Theta}(\sqrt{\log n})}$. Hence, the multiplicative
deviations bring the summation to at most $1/2$ and the additive deviations,
over all the $d$ neighboring clusters, raise the total sum to at most $1$.
Thus, this would still ensure that we have a valid fractional matching. How
does each cluster compute such a rounded fractional solution that satisfies
this constraint for all possible neighboring nodes $v$?

For each cluster $\mathcal{C}$, such a solution exists by a simple
probabilistic rounding argument. Let us provide an informal explanation.
Suppose we keep the fractional values that exceed $1/\Theta(d\log n)$ intact.
For any edge that has $x_{e}\leq 1/\Theta(d\log n)$, let us round it
probabilistically: with probability $p=x_{e}\cdot\Theta(d\log n)$, we set it
to $1/\Theta(d\log n)$, and with the rest of the probability, we set it to
zero. One can see by a standard Chernoff bound that, w.h.p., for the edges in
$E_{C}$ incident on node $v$, the new summation of fractional values is within
a $2$ factor of the old summation, modulo an additive error of at most
$1/(2d)$. With this rounding, now the smallest fractional value is at least
$1/\Theta(d\log n)=1/2^{\widetilde{\Theta}(\sqrt{\log n})}$. Furthermore, with
a reasonably high probability, the size of the fractional matching is
preserved up to a constant factor inside the cluster666We defer the precise
discussions of the details to Section 5.. To deterministically find the
solution proven to exist by this probabilistic argument, it suffices for the
cluster $\mathcal{C}$ to gather the current fractional values of the edges in
$E_{C}$. Then, it can find such a fractional solution in a centralized
fashion. Since the diameter of the cluster is $O(\sqrt{\log n})$, this can be
done easily in $O(\log n)$ rounds of the $\mathsf{LOCAL}$ model.

Once each cluster does this rounding (and note that all can be done in
parallel), we have computed a fractional matching with integrality
$1/2^{\widetilde{\Theta}(\sqrt{\log n})}$ whose size is at least a constant
fraction of the fractional matching with which we started. Hence, it suffices
to apply only $\widetilde{O}(\sqrt{\log n})$ steps of local rounding of
[Fis20] on this fractional matching, and that takes $\widetilde{O}(\sqrt{\log
n})^{2}=\widetilde{O}(\log n)$ rounds. Therefore, we now have a method to
compute a constant-approximate integral matching in $\widetilde{O}(\log n)$
rounds. This is after the initial $\widetilde{O}(\log^{2}n)$ time spent for
computing the clustering, but that clustering is computed only once. With
$O(\log n)$ repetitions of this constant-approximate integral matching in
$\widetilde{O}(\log n)$ rounds, each time removing the matched nodes from the
future matching computations, we get a maximal matching in
$\widetilde{O}(\log^{2}n)$ rounds.

###  2.4 Construction of the clustering, and hitting set with pipelining

Our low-diameter clustering algorithms are similar in spirit to Ghaffari et
al. [GGH+23]. We start by briefly overviewing their approach.

#### Review of the clustering algorithm of [GGH+23].

Recently, Ghaffari et al. [GGH+23] obtained a network decomposition with
$O(\log n)$ colors and diameter $O(\log n\log\log\log n)$. One key step
towards that result is an algorithm that, in $\widetilde{O}(\log^{2}n)$
rounds, computes a partition of diameter $O(\log n)$ such that a large
constant fraction of the vertices have a clustering degree of $O(\log\log n)$.
Their algorithm to compute such a partition can be seen as a derandomization
of the randomized algorithm of Miller, Peng and Xu [MPX13]. The randomized
algorithm of Miller, Peng and Xu computes a partition of diameter $O(\log n)$
by first assigning each vertex a (random) delay between $0$ and $O(\log n)$.
Then, each node $u$ gets clustered to the node $v$ minimizing $del(v)+d(v,u)$
where $del(v)$ is the delay assigned to node $v$. The delays assigned to all
of the vertices can be computed by repeatedly, for $\log n$ repetitions,
subsampling all the remaining active nodes with probability $1/2$. Here, all
the nodes would be active at the beginning, and in each repetition we keep
each previously active node with probability $1/2$. With high probability, no
active node remains after $O(\log n)$ subsampling steps. The deterministic
algorithm of Ghaffari et al. derandomizes each of the $O(\log n)$ subsampling
steps. To do so, they phrase each subsampling step as an instance of a certain
hitting set variant. They show that the randomized algorithm produces a
partition such that the expected cluster degree of each node is $O(\log\log
n)$. The hitting set viewpoint in each subsampling step lends itself to
pairwise analyses and opens the road for efficient derandomization, allowing
one to “sample” the vertices of each step in $\widetilde{O}(\log n)$ rounds in
a deterministic manner.

#### Our Clustering Algorithms.

For our weaker clustering result, namely Theorem 2.2 which clusters only a
constant fraction of the vertices (or their weights), we follow a similar
general approach. One can see that, for any $\alpha\leq\log n$, by a simple
parameter adjustment in [MPX13], their randomized construction produces a
partition with diameter $O(\alpha)$ and cluster degree $2^{O(\log
n/\alpha)}$–essentially, it suffices to have $\alpha$ subsampling steps, each
with probability $2^{-O(\log n/\alpha)}$. We can then follow a similar
derandomization approach as [GGH+23] to turn this into a deterministic
algorithm. Indeed, because of the parameter regime, we can work here with a
even slightly simpler hitting set analyses, as we describe in Section 4.1.
This leads to clustering a constant fraction of the nodes (or a constant
fraction of their weights) in $\widetilde{O}(\alpha\log n)$ rounds.
Intuitively, in contrast to the $\widetilde{O}(\log^{2}n)$ complexity of the
clustering of [GGH+23], the complexity here is $\widetilde{O}(\alpha\log n)$
because the distance in the hitting set problem (to coordinate between the
nodes to be hit and the active nodes) is reduced from $O(\log n)$ to
$O(\alpha)$.

For the stronger clustering algorithm that we have, namely Theorem 2.1, we
want to cluster all vertices. Doing this by repetitions of Theorem 2.2, which
clusters only a constant fraction of nodes (or their weights), would incur a
factor of $O(\log n)$ loss in the round complexity. That would bring the
complexity of our clustering to $\widetilde{O}(\alpha\log^{2}n)$. Theorem 2.1
however achieves a complexity of $\widetilde{O}(\alpha^{2}\log n)$. For that,
we present a novel pipelining idea in the hitting set framework, as we outline
next.

#### Efficient Hitting Set Derandomization with Pipelining

Recently, Faour et al. [FGG+23] gave a local rounding method that essentially
can derandomize pairwise analyses. Consider some random process where each
node gets sampled with probability $p$, pairwise independently. Then, assuming
the pairwise analyses looks at only pairs of nodes that are nearby, their
method allows one to derandomize the sampling in roughly $O(\log^{2}(1/p))$
rounds of the $\mathsf{LOCAL}$ model.

Let us provide a brief intuition: their algorithm views the probabilistic
solutions as a $p$-integral fractional assignment, and gradually rounds it to
an integral solution in $s=O(\log(1/p))$ doubling steps. The approach views
the objectives analyzed via pairwise analyses as its target function, which
should be approximately preserved. Each step uses a certain defective coloring
and then decides the rounding of the nodes of each color simultaneously. This
ensures that, with the exception of the small loss in the target function over
edges that are colored monochromatically, the rest of the target function is
preserved. The coloring is chosen such that the loss in each step is roughly a
$1/(2s)$ fraction of the overall target function, so that the total loss over
all $s=O(\log(1/p))$ steps is still below a constant fraction. This aspect of
the parameterization is similar to the basic rounding of Fischer [Fis20] for
matchings, as discussed before.

Now, let us illustrate our pipelining idea by considering a simplified setup.
Let $G=(U\sqcup V,E)$ be a bipartite graph. We assume that each node $u\in U$
has degree $\Delta$ and we define $n=|U|$. The goal is to compute a small
subset $V^{\prime}\subseteq V$ such that each node in $U$ is neighboring with
at least one node in $V^{\prime}$. Such a set $V^{\prime}$ is referred to as a
hitting set.

Consider the probabilistic approach where each node in $V$ joins $V^{\prime}$
independently with probability $p=O(\log(n)/\Delta)$. The expected size of
$V^{\prime}$ is $O\left(\frac{\log(n)|V|}{\Delta}\right)$. Moreover, each node
$u\in U$ is hit with probability $1-(1-p)^{\Delta}\geq 1-\frac{1}{n^{10}}$.
Unfortunately, this analysis completely breaks down if we only assume pairwise
independence.

A hitting set with the same guarantees can be computed using only pairwise
independence as follows: First, let each node in $V$ join $V^{\prime}$ with
probability $\frac{1}{10\Delta}$, pairwise independently. A simple pairwise
analysis shows that each node has one neighbor in $V^{\prime}$ with
probability at least $\frac{1}{100}$. Therefore, repeating this subsampling
step $O(\log n)$ times, and adding every node to $V^{\prime}$ that was sampled
at least once, results in each node being hit with high probability. Moreover,
the expected size of $V^{\prime}$ is $O(\frac{\log(n)|V|}{\Delta})$.

The method of Faour et al. [FGG+23] allows to directly derandomize the
pairwise analysis. In particular, it allows to compute in $O(\log^{2}\Delta)$
rounds a subset $V^{\prime}\subseteq V$ of size $O(|V|/\Delta)$ such that at
least $\frac{n}{100}$ vertices of $U$ have a neighbor in $V$. Hence, in
$O(\log n\log^{2}\Delta)$ rounds, one can deterministically compute a hitting
set of size $O(\log(n)|V|/\Delta)$. This is not efficient enough for us to
achieve Theorem 2.2, especially for large $\Delta\gg\log n$.

We give a method that, in just $\widetilde{O}(\log n)$ rounds,
deterministically computes a slightly larger hitting set of size
$O(|V|/\Delta^{1/\log\log n})$. Let $k=O(\log\Delta/\log\log n)$ be the
largest integer such that $(100\log n)^{k}\leq\Delta$. For $j\in[0,k]$, let
$\deg_{j}=(100\log n)^{k-j}$. The algorithm computes a sequence of sets
$V:=V_{0}\supseteq V_{1}\supseteq\ldots\supseteq V_{k}$ such that each node in
$U$ has at least $\deg_{j}$ neighbors in $V_{j}$. In particular, each node in
$U$ has at least $\deg_{k}\geq 1$ neighbors in $V_{k}$ and therefore $V_{k}$
is a hitting set. The algorithm also ensures that $|V_{j}|\leq|V|/2^{j}$ and
therefore $|V_{k}|=O(|V|/\Delta^{1/\log\log n})$, as promised. In the
randomized world, one could obtain $V_{j+1}$ from $V_{j}$ by subsampling each
vertex with probability $1/2$. Then, given that each node in $U$ neighbors at
least $deg_{j}$ nodes in $V_{j}$, one can show that with high probability each
node in $U$ neighbors at least $deg_{j+1}$ nodes in $V_{j+1}$. One can also
derandomize this with round complexity $\widetilde{O}(\log n)$, which then
would result in a round complexity of $\widetilde{O}(\log n\log\Delta)$. We
give a method that pipelines the computation of the sets, in the sense that it
starts the computation of $V_{j+1}$ before we have finished computing $V_{j}$.
The actual ingredients of this pipelining are more involved and are thus
deferred to the technical section. We hope that similar pipelining ideas might
find applications in other similar contexts.

##  3 Preliminaries

###  3.1 Definitions and Basic Inequalities

#### Notation and Basic Definitions.

We use $n$ to denote the number of nodes and $N$ to denote a polynomial upper
bound on the number of nodes. For two integers $a,b$ where $a\leq b$, we
define $[a,b]=\\{a,a+1,\dots,b\\}$. For an event $\mathcal{E}$, we define the
indicator variable $I(\mathcal{E})$ to be equal to $1$ if $\mathcal{E}$
happens and $0$ otherwise.

Given a graph $G=(V,E)$, a fractional matching is an assignment of a value
$x_{e}\in[0,1]$ to each $e\in E$ such that for every vertex $v\in V$, we have
$\sum_{e\ni v}x_{e}\leq 1$. The size of this fractional matching is
$\sum_{e}x_{e}$. We call the fractional matching $1/Q$-integral if each edge
$e$ satisfies either $x_{e}=0$ or $x_{e}\geq 1/Q$. We use this
$1/Q$-integrality term more generally also for other fractional assignments.

We next state some concentration inequalities that we will use throughout the
paper.

######  Theorem 3.1 (Chernoff Bound).

Let $X:=\sum_{i\in[1,n]}X_{i}$, where $X_{i}$, $i\in[1,n]$ are independently
distributed and $0\leq X_{i}\leq 1$. Then, for a given $\delta>0$, we have

$Pr[|X-\operatorname{\mathbb{E}}[X]|\geq\delta\operatorname{\mathbb{E}}[X]]\leq
2e^{-\frac{\min(\delta,\delta^{2})\operatorname{\mathbb{E}}[X]}{3}}.$

######  Corollary 3.2 (Chernoff Bound variant).

Let $Y:=\sum_{i\in[1,n]}Y_{i}$, where $Y_{i}$, $i\in[1,n]$ are independently
distributed and $0\leq Y_{i}\leq b$ for some $b>0$. Then, for a given $t\geq
0.5E[Y]$, it holds that

$Pr[|Y-\operatorname{\mathbb{E}}[Y]|\geq t]\leq 2e^{-\frac{t}{6b}}.$

###### Proof.

For every $i\in[1,n]$, let $X_{i}=Y_{i}/b$ and $X=\sum_{i=1}^{n}X_{i}$.
Moreover, let $\delta:=\frac{t}{\operatorname{\mathbb{E}}[Y]}\geq\frac{1}{2}$
Then, using Theorem 3.1, we get

$Pr[|Y-\operatorname{\mathbb{E}}[Y]|\geq
t]=Pr[|X-\operatorname{\mathbb{E}}[X]|\geq\delta\operatorname{\mathbb{E}}[X]]\leq
2e^{-\frac{\min(\delta,\delta^{2})\operatorname{\mathbb{E}}[X]}{3}}\leq
2e^{-\frac{\delta\operatorname{\mathbb{E}}[X]}{6}}=2e^{-\frac{t}{6b}}.$

∎

###  3.2 The local rounding framework

We use the local rounding framework of Faour et al. [FGG+23]. Their rounding
framework works via computing a particular weighted defective coloring of the
vertices, which allows the vertices of the same color to round their values
simultaneously, with a limited loss in some objective functions that can be
written as a summation of functions, each of which depends on only two nearby
nodes. Next, we provide a related definition and then state their black-box
local rounding lemma.

######  Definition 3.1.

[Pairwise Utility and Cost Functions] Let $G=(V_{G},E_{G})$ be a graph. For
any label assignment $\vec{x}:V_{G}\rightarrow\Sigma$, a pairwise utility
function is defined as $\sum_{u\in V_{G}}\mathbf{u}(u,\vec{x})+\sum_{e\in
E_{G}}\mathbf{u}(e,\vec{x})$, where for a vertex $u$, the function
$\mathbf{u}(u,\vec{x})$ is an arbitrary function that depends only on the
label of $u$, and for each edge $e=\\{u,v\\}$, the function
$\mathbf{u}(e,\vec{x})$ is an arbitrary function that depends only on the
labels of $v$ and $u$. These functions can be different for different vertices
$u$ and also for different edges $e$. A pairwise cost function is defined
similarly.

For a probabilistic/fractional assignment of labels to vertices $V_{G}$, where
vertex $v$ assumes each label in $\Sigma$ with a given probability, the
utility and costs are defined as the expected values of the utility and cost
functions, if we randomly draw integral labels for the vertices from their
corresponding distributions (and independently, though of course each term in
the summation depends only on the labels of two vertices and thus pairwise
independence suffices).

######  Lemma 3.3.

[cf. Lemma 2.5 of [FGG+23]] Let $G=(V_{G},E_{G})$ be a multigraph, which is
equipped with utility and cost functions $\mathbf{u}$ and $\mathbf{c}$ and
with a fractional label assignment $\lambda$ such that for every label
$\alpha\in\Sigma$ and every $v\in V_{G}$,
$\lambda_{\alpha}(v)\geq\lambda_{\min}$ for some given value
$\lambda_{\min}\in(0,1]$. Further assume that $G$ is equipped with a proper
$\zeta$-vertex coloring. If $\mathbf{u}(\lambda)-\mathbf{c}(\lambda)\geq
0.1\mathbf{u}(\lambda)$ and if each node knows the utility and cost functions
of its incident edges, there is a deterministic
$O\big{(}\log^{2}\big{(}\frac{1}{\lambda_{\min}}\big{)}+\log\big{(}\frac{1}{\lambda_{\min}}\big{)}\cdot\log^{*}\zeta\big{)}$-round
distributed message passing algorithm on $G$, in the $\mathsf{LOCAL}$ model,
that computes an integral label assignment $\ell$ for which

$\mathbf{u}(\ell)-\mathbf{c}(\ell)\geq
0.9\big{(}\mathbf{u}(\lambda)-\mathbf{c}(\lambda)\big{)}.$

###  3.3 The hitting set subroutines

We also make use of a deterministic distributed algorithm for computing a
certain hitting set. The formal statement is provided below.

######  Lemma 3.4.

There exists a deterministic distributed algorithm in the $\mathsf{LOCAL}$
model such that, for every $\Delta\in\mathbb{N}$, $b\in\mathbb{N}$,
$k\in[1,\Delta]$, $p=\Omega(1/k)$ and $Norm\geq 0$, it provides the following
guarantees: The input is a bipartite graph $H=(U_{H}\sqcup V_{H},E_{H})$ with
$deg_{H}(u)=\Delta$ for every $u\in U_{H}$. Initially, each node is equipped
with a unique $b$-bit identifier and each node $u$ is assigned a weight
$w_{u}\geq 0$. Each node also knows at the beginning to which side of the
bipartition it belongs. The algorithm computes a subset $V^{sub}\subseteq
V_{H}$ satisfying

$\sum_{u\in U_{H}\colon|N_{H}(u)\cap V^{sub}|\leq
0.5\lfloor\Delta/k\rfloor}w_{u}+Norm\cdot|V^{sub}|\leq
4\left(e^{-pk}\sum_{u\in U_{H}}w_{u}+Norm\cdot p\cdot|V_{H}|\right).$

The algorithm runs in $O(kp(\log^{2}(k)+\log(k)\log^{*}b))$ rounds.

Notice that a simple probabilistic scheme where we include each node of
$V_{H}$ in $V^{sub}$ independently with probability $p$ achieves the desired
properties in expectation (and indeed with even stronger guarantees). In
particular, let us even group the neighbors of each $u\in U_{H}$ into
$\lfloor\Delta/k\rfloor$ groups each of size $k$—we will rely on independence
only within each group and this simplifies the task for derandomization. The
probability that a group does not have a node in $V^{sub}$ is at most
$(1-p)^{k}\leq e^{-pk}$. If $u\in U_{H}\colon|N_{H}(u)\cap V^{sub}|\leq
0.5\lfloor\Delta/k\rfloor$, then half of its groups are not hit. However, we
expect only $e^{-pk}$ fraction of groups not to be hit (and the fraction can
be weighted, by taking the $w_{u}$ weights into account). So, roughly
speaking, the weighted fraction of nodes $u$ such that $u\in
U_{H}\colon|N_{H}(u)\cap V^{sub}|\leq 0.5\lfloor\Delta/k\rfloor$ is at most
$2e^{-pk}$. The lemma statement has another $2$ factor of slack beyond this
bound, which simplifies the argument and suffices for the applications. We
present a method to deterministically compute such a set $V^{sub}$. This is by
an adaptation of the method of Faour et al. [FGG+23], and statements somewhat
similar to this lemma were implicit in [FGG+23, GGH+23]. We provide a proof
for Lemma 3.4 in Appendix A.

##  4 Clustering

This section is devoted to proving our two clustering results, as restated
below. Please see Definition 2.1 for the related definitions.

See 2.1 See 2.2

Notice the first statement clusters all nodes and takes
$\widetilde{O}(\alpha^{2}\log n)$ rounds, while the second statement clusters
only a 0.9 fraction of the vertices, in a weighted sense, but runs faster in
$\widetilde{O}(\alpha\log n)$ rounds. Both algorithms can be seen as a
derandomization of the randomized clustering algorithm of Miller, Peng and Xu
[MPX13]. The high-level approach in all of the three algorithms is the same
and can be found in Algorithm 1. The idea is to first compute a delay
$del(v)\in\\{0,1,\ldots,50\alpha\\}$ for every $v\in V$. Then, these delays
define a partition as follows: First, each node starts to broadcast a token at
time $del(v)$. Then, in the following $O(\alpha)$ rounds, a node forwards all
the token it has received in the previous rounds to its neighbors. For a given
node $u$, let $c_{u}$ be the node whose token reaches $u$ first, breaking ties
by choosing the node with the smallest identifier. Then, $u$ joins the cluster
corresponding to the node $c_{u}$. Formally speaking, we define
$c_{u}:=\arg\min_{v\in V}(del(v)+d(v,u),ID(v))$ where pairs are compared
according to the lexicographic order and for a node $v$ we define the cluster
associated with $v$ as $C_{v}:=\\{u\in V\colon c_{u}=v\\}$. Finally, the
output clustering consists of all non-empty clusters $C_{v}$ for $v\in V$. To
compute the delay $del(v)$ for every node $v\in V$, all three algorithms
compute a sequence of sets $V^{active}_{0}:=V\supseteq
V^{active}_{1}\supseteq\ldots\supseteq V^{active}_{10\alpha}=\emptyset$. Then,
$i_{v}$ is defined as the largest index $i$ with $v\in V^{active}_{i}$ and the
delay of $v$ is defined as $del(v):=50\alpha-5i_{v}$. Our two clustering
algorithms and the randomized clustering of Miller, Peng, and Xu only differ
in the way $V_{i+1}^{active}$ is computed given the set $V^{active}_{i}$; the
randomized clustering algorithm simply obtains $V_{i+1}^{active}$ by including
each vertex in $V^{active}_{i}$ independently with probability
$p_{rand}=2^{-\log(n)/\alpha}$. Note that this implies
$V^{active}_{10\alpha}=\emptyset$ with high probability. Furthermore, since
$del(v)\in[0,50\alpha]$, the diameter of the output partition is $O(\alpha)$.

######  Claim 4.1.

Algorithm 1 produces a partition with diameter $O(\alpha)$.

###### Proof.

Consider some arbitrary $u\in V$. We have

$del(c_{u})+d(c_{u},u)\leq del(u)+d(u,u)\leq 50\alpha$

and therefore $d(c_{u},u)\leq 50\alpha$. Let $w$ be an arbitrary node on some
shortest path from $c_{u}$ to $u$. We show that $c_{w}=c_{u}$, which together
with $d(c_{u},u)\leq 50\alpha$ finishes the proof of the claim. Consider some
arbitrary node $v$. We have to show that

$(del(c_{u})+d(c_{u},w),ID(c_{u}))<del(v)+d(v,w),ID(v)).$

As $w$ is on a shortest path from $c_{u}$ to $u$, we have
$d(c_{u},u)=d(c_{u},w)+d(w,u)$. Therefore,

$\displaystyle(del(c_{u})+d(c_{u},w),ID(c_{u}))$
$\displaystyle=(del(c_{u})+d(c_{u},u)-d(w,u),ID(c_{u}))$
$\displaystyle<(del(v)+d(v,u)-d(w,u),ID(v))$
$\displaystyle\leq(del(v)+d(v,w),ID(v)).$

∎

Algorithm 1 Generic Partitioning Algorithm

Input: Parameter $\alpha\in\mathbb{N}$, Algorithm $\mathcal{A}$
Output: A partition $\mathcal{C}$ of the vertex set

1:procedure Partitioning

2: $\triangleright$ Delay Computation

3: $V_{0}^{active}\leftarrow V$

4: for $i\leftarrow 0,1,\ldots,10\alpha-1$ do

5: $V^{active}_{i+1}\leftarrow\mathcal{A}(V^{active}_{i},i,\alpha)$
$\triangleright$ $V^{active}_{i+1}\subseteq V^{active}_{i}$

6: $Assert:V^{active}_{10\alpha}=\emptyset$

7: For every $v\in V$, let $i_{v}$ be the largest index $i$ with $v\in
V^{active}_{i}$

8: For every $v\in V$, define $del(v)\leftarrow 50\alpha-5i_{v}$

9: $\triangleright$ Partitioning given the delays

10: $\forall u\in V\colon c_{u}\leftarrow\arg\min_{v\in
V}(del(v)+d(v,u),ID(v))$

11: $\forall v\in V\colon C_{v}\leftarrow\\{u\in V\colon c_{u}=v\\}$

12: return $\mathcal{C}=\\{C_{v}\colon v\in V,C_{v}\neq\emptyset\\}$

The next lemma will be used later on to upper bound the cluster degree of a
vertex. Before stating it, we introduce one more definition.

######  Definition 4.1 ($S_{i}(u)$).

For every $u\in V$ and $i\in[0,10\alpha-1]$, we define

$S_{i}(u)=V^{active}_{i}\cap B_{G}(u,d(u,\min(V^{active}_{i})+2,100\alpha)).$

Informally speaking, the set $S_{i}(u)$ contains those active nodes in
$V^{active}_{i}$ which are almost as close to $u$ as the closest active node
in $V^{active}_{i}$, unless the closest node in $V^{active}_{i}$ is far away.
The last part ensures that each node $u$ can compute the set $S_{i}(u)$ in
$O(\alpha)$ rounds, which will be important later on.

######  Lemma 4.2.

Let $u\in V$ be arbitrary, $\mathcal{C}$ the partition returned by Algorithm 1
and

$R_{u}:=\max_{i\in\\{0,1,\ldots,10\alpha-1\\}\colon S_{i}(u)\cap
V^{active}_{i+1}=\emptyset}|S_{i}(u)|.$

Then, it holds that $deg_{\mathcal{C}}(u)=O(\alpha R_{u})$.

#### Randomized Intuition

Before we prove Lemma 4.2, let’s get some intuition by applying it to the
randomized clustering algorithm. In particular, a simple hitting set argument
on top of Lemma 4.2 gives that $deg_{\mathcal{C}}(u)=O(\log n/p_{rand})$,
w.h.p. Recall that the randomized algorithm obtains $V^{active}_{i+1}$ by
including each vertex in $V^{active}_{i}$ with probability
$p_{rand}=2^{-\log(n)/\alpha}$. Consider an arbitrary
$i\in\\{0,1,\ldots,10\alpha-1\\}$ and assume that $|S_{i}(u)|\geq
10\log(n)/p_{rand}$. With high probability, at least one node in $S_{i}(u)$
will be sampled and added to $V^{active}_{i+1}$. Hence, with high probability
$R_{u}\leq 10\log(n)/p_{rand}$, in which case Lemma 4.2 gives
$\deg_{\mathcal{C}}(u)=O(\alpha\cdot\log(n)2^{log(n)/\alpha})$. We note that
this analysis is not tight. Using the memoryless property of the exponential
distribution, one can show that $\deg_{\mathcal{C}}(u)=O(2^{\log(n)/\alpha})$
with positive constant probability and
$\deg_{\mathcal{C}}(u)=O(\log(n)2^{\log(n)/\alpha})$ with high probability.
The latter bound improves our bound by a factor of $\alpha$, i.e., for
$\alpha=O(\log n)$ our proof gives that with high probability
$\deg_{\mathcal{C}}(u)=O(\log^{2}n)$ while a tighter analysis shows that
$\deg_{\mathcal{C}}(u)=O(\log n)$. However, this simple hitting set analysis
is sufficient to obtain our desired result.

###### Proof of Lemma 4.2.

Let $w$ be an arbitrary neighbor of $u$. Note that in order to prove Lemma
4.2, it suffices to show that

$c_{w}\in S_{u}:=\bigcup_{i\in\\{0,1,\ldots,10\alpha-1\\}\colon S_{i}(u)\cap
V^{active}_{i+1}=\emptyset}S_{i}(u),$

as $|S_{u}|\leq 10\alpha R_{u}$. In particular, we show below that $c_{w}\in
S_{i_{c_{w}}}(u)$ and $S_{i_{c_{w}}}(u)\cap
V^{active}_{i_{c_{w}}+1}=\emptyset$.

Let $v$ be an arbitrary node. As $u$ and $w$ are neighbors and the token of
$c_{w}$ arrives no later at $w$ than the token of $v$, we can conclude that
the token of $c_{w}$ arrives at $u$ at most two time units after the token of
$v$. More formally,

$del(c_{w})+d(c_{w},u)\leq del(c_{w})+d(c_{w},w)+1\leq del(v)+d(v,w)+1\leq
del(v)+d(v,u)+2.$

In particular,

$d(c_{w},u)\leq d(v,u)+\left(del(v)-del(c_{w})\right)+2\leq
d(v,u)+5(i_{c_{w}}-i_{v})+2,$ (1)

where the second inequality follows from $del(v):=50\alpha-5i_{v}$ and
$del(w):=50\alpha-5i_{c_{w}}$. If $v\in V^{active}_{i_{c_{w}}}$, then
$i_{v}\geq i_{c_{w}}$ and if $v\in V^{active}_{i_{c_{w}}+1}$, then
$i_{v}>i_{c_{w}}$. Therefore, Eq. 1 gives

  1. 1.

for every $v\in V^{active}_{i_{c_{w}}},d(c_{w},u)\leq d(v,u)+2$ and

  2. 2.

for every $v\in V^{active}_{i_{c_{w}}+1},d(v,u)\geq d(c_{w},u)+3$.

The first part together with $d(c_{w},u)\leq del(u)+d(u,u)+2\leq 50\alpha+2$
implies that $c_{w}\in S_{i_{c_{w}}}(u):=V^{active}_{i_{c_{w}}}\cap
B_{G}(u,\min(d(u,V^{active}_{i_{c_{w}}})+2,100\alpha))$. The second part
directly implies that for every $v\in V^{active}_{i_{c_{w}}+1}$ it holds that
$v\notin S_{i_{c_{w}}}(u)$ and therefore $S_{i_{c_{w}}}(u)\cap
V^{active}_{i_{c_{w}}+1}=\emptyset$. Together with the discussion above, this
finishes the proof. ∎

###  4.1 Clustering with Constant Fraction Good

This section is dedicated to proving Theorem 2.2. As a reminder, the goal is
to compute a partition with diameter $O(\alpha)$ such that at least 90 percent
of the vertices (in a weighted sense) have a cluster degree of
$2^{\widetilde{O}(\log n)/\alpha}$.

The algorithm follows the outline of Algorithm 1. The only missing part is to
specify how to compute $V^{active}_{i+1}$ given $V^{active}_{i}$ for every
$i\in[0,10\alpha-1]$.

In phase $i$, the goal is to compute $V^{active}_{i+1}$ in such a way that
almost all nodes $u$ with $|S_{i}(u)\cap
V^{active}_{i}|=2^{\widetilde{\Omega}(\log n)/\alpha}$ satisfy $S_{i}(u)\cap
V^{active}_{i+1}\neq\emptyset$. We refer to a node $u$ that does not satisfy
this condition as being bad in phase $i$. For a node $u$, if there does not
exist a phase $i$ in which $u$ is bad, Lemma 4.2 implies that the clustering
degree of $u$ is $2^{\widetilde{O}(\log n)/\alpha}$. Below, we give the formal
definition of being bad in phase $i$.

######  Definition 4.2 (Bad in phase $i$, $U^{bad}_{i}$).

For every $i\in[0,10\alpha-1]$, we refer to a node as bad in phase $i$ if
$|S_{i}(u)|\geq\lceil 1000\log\log(N)\rceil^{\log(N)/\alpha}$ and
$S_{i}(u)\cap V^{active}_{i+1}=\emptyset$. We denote by $U^{bad}_{i}$ the set
consisting of all bad nodes in phase $i$.

Recall, in the $\mathsf{LOCAL}$ model nodes don’t have access to the precise
number of vertices in the graph, but are only given a polynomial upper bound,
which we denote by $N$. Also note that $\lceil
1000\log\log(N)\rceil^{\log(N)/\alpha}=2^{\widetilde{O}(\log n)/\alpha}$.

Starting with $V^{active}_{i}$, we compute $V^{active}_{i+1}$ in
$\log(N)/\alpha$ steps. In step $j$, we start with a set $V^{active}_{i,j}$
and compute a subset $V^{active}_{i,j+1}\subseteq V^{active}_{i,j}$.
Initially, we define $V^{active}_{i,0}=V^{active}_{i}$ and after the last
step, we set $V^{active}_{i+1}=V^{active}_{i,\log(N)/\alpha}$. Note that we
can assume without loss of generality that $N$ is a sufficiently large
constant and that $\alpha$ divides $\log(N)$.

Before we explain in more detail what happens in each step, we first give two
more definitions. The first definition associates a degree threshold for each
step.

######  Definition 4.3 ($\deg_{j}$).

For every $j\in[0,\log(N)/\alpha]$, we define $\deg_{j}=\lceil
1000\log\log(N)\rceil^{\log(N)/\alpha-j}$.

If a node $u$ is bad in phase $i$, then $|S_{i}(u)\cap
V^{active}_{i}|\geq\deg_{0}$ and $|S_{i}(u)\cap
V^{active}_{i+1}|<\deg_{\log(N)/\alpha}$.

Next, we define what it means for a node to be bad during a step.

######  Definition 4.4 (Bad in step $j$ of phase $i$, $U^{bad}_{i,j}$).

For every $i\in[0,10\alpha-1]$ and $j\in[0,log(N)/\alpha-1]$ We say that a
node is bad in step $j$ of phase $i$ if $|S_{i}(u)\cap
V_{i,j}^{active}|\geq\deg_{j}$ and $|S_{i}(u)\cap
V_{i,j+1}^{active}|<\deg_{j+1}$. We denote by $V_{i,j}^{bad}$ the set of bad
nodes during step $j$ of phase $i$.

If a node $u$ is bad in phase $i$, then $|S_{i}(u)\cap
V^{active}_{i,0}|\geq\deg_{0}$ and $|S_{i}(u)\cap
V^{active}_{i,\log(N)/\alpha}|<\deg_{\log(N)/\alpha}$. Hence, there exists
some $j\in[0,\log(N)/\alpha-1]$ such that $|S_{i}(u)\cap
V^{active}_{i,j}|\geq\deg_{j}$ and $|S_{i}(u)\cap
V^{active}_{i,j+1}|<\deg_{j+1}$ and therefore $u$ is bad in at least one step
of phase $i$.

Fix some $i\in[0,10\alpha-1]$ and $j\in[0,\log(N)/\alpha-1]$. We compute
$V_{i,j+1}^{active}$ given $V_{i,j}^{active}$ by first defining a bipartite
graph $H$, then invoking the hitting set subroutine of Lemma 3.4 to deduce
that there exists an efficient $\mathsf{LOCAL}$ algorithm on the bipartite
graph which computes a subset of $V^{active}_{i,j}$ with the desired
properties, and finally use the fact that we can simulate the algorithm on the
bipartite graph on the original graph with an $O(\alpha)$-multiplicative
overhead.

Consider the bipartite graph $H=(U_{H}\sqcup V_{H},E_{H})$ with $U_{H}=\\{u\in
V\colon|S_{i}(u)\cap V^{active}_{i,j}|\geq\deg_{j}\\},V_{H}=V^{active}_{i,j}$
and where we connect each node $u\in U_{H}$ to $\deg_{j}$ nodes in
$S_{i}(u)\cap V^{active}_{i,j}$.

Using the fact that $S_{i}(u)\subseteq B_{G}(u,1000\alpha)$ for every $u\in
V$, it follows that each round in $H$ can be simulated in $O(\alpha)$ rounds
in the original graph. Moreover, as $H$ contains at most two copies of each
node in $G$, we can assign each node a unique $b$-bit identifier with
$b=O(\log N)$.

One of the parameters of Lemma 3.4 is a normalization constant, which we
define below.

######  Definition 4.5 (Normalization Constant).

For every $i\in[0,10\alpha-1]$ and $j\in[0,\log(N)/\alpha]$, we define
$Norm_{i,j}=\frac{2^{i\cdot\log(N)/\alpha+j}}{N^{2}}$.

We now invoke Lemma 3.4 with parameters $\Delta=\deg_{j}$, $k=\lceil
100\log\log(N)\rceil$ and $p=\frac{1}{16}$ to conclude that there exists a
$\mathsf{LOCAL}$ algorithm running in
$O(kp(\log^{2}(k)+\log(k)\log^{*}b))=\widetilde{O}(\log\log n)$ rounds on $H$,
and hence can be simulated in $\widetilde{O}(\log\log n)\alpha$ rounds in $G$,
which computes a set $V^{sub}\subseteq V_{H}$ satisfying

$\sum_{u\in U_{H}\colon|N_{H}(u)\cap V^{sub}|\leq
0.5\lfloor\Delta/k\rfloor}x_{u}+Norm_{i,j}\cdot|V^{sub}|\leq
4\left(e^{-pk}\sum_{u\in U_{H}}x_{u}+Norm_{i,j}\cdot p\cdot|V_{H}|\right).$

We then define $V^{active}_{i,j}=V^{sub}$. Consider some node $u$ that is bad
in step $j$ of phase $i$. By definition, $|S_{i}(u)\cap
V^{active}_{i,j}|\geq\deg_{j}$ and $|S_{i}(u)\cap
V^{active}_{i,j+1}|<\deg_{j+1}$. Therefore, $u\in U_{H}$ and

$|N_{H}(u)\cap V^{sub}|\leq|S_{i}(u)\cap
V^{active}_{i,j+1}|<\deg_{j+1}=\frac{\deg_{j}}{\lceil
1000\log\log(N)\rceil}\leq 0.5\lfloor\Delta/k\rfloor.$

Since $e^{-pk}=e^{-(100/16)\log\log N}\leq\frac{1}{800\log(N)}$, we can
conclude that

$\sum_{u\in
U^{bad}_{i,j}}x_{u}+Norm_{i,j}\cdot|V^{active}_{i,j+1}|\leq\frac{1}{200\log(N)}\sum_{u\in
V}x_{u}+\frac{Norm_{i,j}}{4}|V^{active}_{i,j}|.$

From this, we can deduce the following two claims:

######  Claim 4.3 (No active nodes in the end).

For every $i\in[0,10\alpha-1]$ and $j\in[0,\log(N)/\alpha]$, we have

$|V^{active}_{i,j}|\leq\frac{\sum_{u\in V}x_{u}}{50\log(N)Norm_{i,j}},$

which in particular also implies that $V^{active}_{10\alpha}=\emptyset$.

###### Proof.

First, note that

$|V^{active}_{0,0}|\leq n\leq\frac{1}{50\log(N)(1/N^{2})}\leq\frac{\sum_{u\in
V}x_{u}}{50\log(N)Norm_{0,0}}.$

Also, recall that for every $i\in[1,10\alpha-1]$,
$V^{active}_{i+1,0}:=V^{active}_{i+1}:=V^{active}_{i,\log(N)/\alpha}$.
Together with $Norm_{i+1,0}=Norm_{i,\log(N)/\alpha}$, we get that
$|V^{active}_{i,\log(N)/\alpha}|\leq\frac{\sum_{u\in
V}x_{u}}{50\log(N)Norm_{i,\log(N)/\alpha}}$ trivially implies that
$|V^{active}_{i+1,0}|\leq\frac{\sum_{u\in V}x_{u}}{50\log(N)Norm_{i+1,0}}$.

Now, assume that $|V^{active}_{i,j}|\leq\frac{\sum_{u\in
V}x_{u}}{50\log(N)Norm_{i,j}}$ for a given $i\in[0,10\alpha-1]$ and
$j\in[0,\log(N)/\alpha-1]$. This implies that

$|V^{active}_{i,j+1}|\leq\frac{\sum_{u\in
V}x_{u}}{200\log(N)Norm_{i,j}}+\frac{1}{4}|V^{active}_{i,j}|\leq\frac{\sum_{u\in
V}x_{u}}{100\log(N)Norm_{i,j}}=\frac{\sum_{u\in
V}x_{u}}{50\log(N)Norm_{i,j+1}}\sum_{u\in V}x_{u}.$

Thus, $|V^{active}_{i,j}|\leq\frac{\sum_{u\in V}x_{u}}{50\log(N)Norm_{i,j}}$,
as one can formalize by an induction. In particular,

$|V^{active}_{10\alpha-1,\log(N)/\alpha}|\leq\frac{\sum_{u\in
V}x_{u}}{50\log(N)Norm_{10\alpha-1,\log(N)/\alpha}}<1$

∎

and as $V^{active}_{10\alpha}:=V^{active}_{10\alpha-1,\log(N)/\alpha}$, we get
that $V^{active}_{10\alpha}=\emptyset$.

######  Claim 4.4 (Total number of bad nodes in step $j$ of phase $i$).

For every $i\in[0,10\alpha-1]$ and $j\in[0,\log(N)/\alpha-1]$, we have

$\sum_{u\in U^{bad}_{i,j}}x_{u}\leq\frac{1}{100\log(N)}\sum_{u\in V}x_{u}.$

###### Proof.

We have

$\sum_{u\in U^{bad}_{i,j}}x_{u}\leq\frac{1}{200\log(N)}\sum_{u\in
V}x_{u}+\frac{Norm_{i,j}}{4}|V^{active}_{i,j}|\leq\frac{\sum_{u\in
V}x_{u}}{100\log(N)}.$

∎

###### Proof of Theorem 2.2.

According to Claim 4.1, the diameter of the output partition is $O(\alpha)$.

Lemma 4.2 implies that
$V\setminus(\cup_{i=0}^{10\alpha-1}U^{bad}_{i})\subseteq\\{u\in
V\colon\deg_{\mathcal{C}}(u)=2^{\widetilde{O}(\log n)/\alpha}\\}$ and Claim
4.4 implies that
$\sum_{u\in\cup_{i=0}^{10\alpha-1}\cup_{j=0}^{\log(N)/\alpha}U^{bad}_{i,j}}x_{u}\leq
10\alpha\cdot(\log(N)/\alpha)\frac{\sum_{u\in
V}x_{u}}{100\log(N)}=\frac{\sum_{u\in V}x_{u}}{10}$. Together with
$U^{bad}_{i}\subseteq\cup_{j=0}^{\log(N)/\alpha}U^{bad}_{i,j}$ for every
$j\in[0,\log(N)/\alpha-1]$, we therefore get $\sum_{u\in
V\colon\deg_{\mathcal{C}}(u)=2^{\widetilde{O}(\log n)/\alpha}}x_{u}\geq
0.9\sum_{u\in V}x_{u}$, as needed.

We have argued that each step takes $\widetilde{O}(\log\log n\cdot\alpha)$
rounds. There are $O(\alpha)\cdot O(\log n/\alpha)$ steps in total, and thus
the total runtime to compute the delays is $\widetilde{O}(\alpha\log n)$.
Given the delays, the output partition can be computed in $O(\alpha)$
additional rounds. Hence, the algorithm runs in $\widetilde{O}(\alpha\log n)$
rounds.

∎

###  4.2 Clustering with all Nodes Good

This section is dedicated to proving Theorem 2.1. As a reminder, the goal is
to compute a partition with diameter $O(\alpha)$ such that _all_ vertices have
a cluster degree of $2^{\widetilde{O}(\log n)/\alpha}$.

As in the previous section, the algorithm follows the outline of Algorithm 1.
The only missing part is to specify how to compute $V^{active}_{i+1}$ given
$V^{active}_{i}$ for every $i\in[0,10\alpha-1]$.

In phase $i$, the goal is to compute $V^{active}_{i+1}$ in such a way that all
nodes $u$ with $|S_{i}(u)\cap V^{active}_{i}|=2^{\widetilde{\Omega}(\log
n)/\alpha}$, which we refer to as being important in phase $i$, satisfy
$S_{i}(u)\cap V^{active}_{i+1}\neq\emptyset$. By using Lemma 4.2, this is
sufficient to ensure that all vertices have a cluster degree of
$2^{\widetilde{O}(\log n)/\alpha}$. We start with the formal definition of
being important in phase $i$. Recall that we use $N$ to denote a polynomial
upper bound on the number of nodes, which is known to all the nodes.

######  Definition 4.6 (Important in phase $i$, $U^{important}_{i}$).

For every $i\in[0,10\alpha-1]$, we refer to a node as being important in phase
$i$ if $|S_{i}(u)|\geq(2000\log N)^{\log(N)/\alpha}$.

As before, phase $i$ consists of $\log(N)/\alpha$ steps and we compute a
sequence of sets $V^{active}_{i,0}:=V^{active}_{i}\supseteq
V^{active}_{i,1}\supseteq V^{active}_{i,2}\supseteq\ldots\supseteq
V^{active}_{i,\log(N)/\alpha}=:V^{active}_{i+1}$.

Compared to Section 4.1, one crucial difference is that the algorithm starts
computing $V^{active}_{i,j+1}$ before it has finished computing
$V^{active}_{i,j}$.

As before, we associate a degree threshold with each step. We remark that the
degree threshold is slightly larger compared to the one in Section 4.1.

######  Definition 4.7 ($\deg_{j}$).

For every $j\in[0,\log(N)/\alpha]$, we define $\deg_{j}=(2000\log
N)^{\log(N)/\alpha-j}$.

Note that $u$ is important in phase $i$ if $|S_{i}(u)|\geq\deg_{0}$ and that
$S_{i}(u)\cap V^{active}_{i+1}\neq\emptyset$ is equivalent to $|S_{i}(u)\cap
V^{active}_{i+1}|=|S_{i}(u)\cap
V^{active}_{i,\log(N)/\alpha}|\geq\deg_{\log(N)/\alpha}$. In general, each
node $u$ which is important in phase $i$ will satisfy $|S_{i}(u)\cap
V^{active}_{i,j}|\geq\deg_{j}$ for every $j\in[0,\log(N)/\alpha]$.

For each $i\in[0,10\alpha-1]$ and $j\in[1,\log(N)/\alpha]$, we compute
$V^{active}_{i,j}$ by computing a sequence of sets
$V^{active}_{i,j,0}:=\emptyset\subseteq
V^{active}_{i,j,1}\subseteq\ldots\subseteq
V^{active}_{i,j,4\log(N)}=:V^{active}_{i,j}$. To simplify notation, we also
define
$V^{active}_{i,0,0}=V^{active}_{i,0,1}=\ldots=V^{active}_{i,0,4\log(N)}=V^{active}_{i,0}:=V^{active}_{i}$
for every $i\in[0,10\alpha-1]$.

For every $j\in[0,\log(N)/\alpha]$ and $\ell\in[0,4\log(N)]$, we define a
partition $U^{important}_{i}=U^{good}_{i,j,\ell}\sqcup U^{bad}_{i,j,\ell}$.

######  Definition 4.8 ($U^{good}_{i,j,\ell}$, $U^{bad}_{i,j,\ell}$).

For every $i\in[0,10\alpha-1],j\in[0,\log(N)/\alpha],\ell\in[0,4\log(N)]$, we
define

$U^{good}_{i,j,\ell}=\\{u\in U^{important}_{i}\colon|S_{i}(u)\cap
V^{active}_{i,j,\ell}|\geq\deg_{j}\\}$

and

$U^{bad}_{i,j,\ell}=U^{important}_{i}\setminus U^{good}_{i,j,\ell}.$

#### Computing $V^{active}_{i,j,\ell}$ given $V^{active}_{i,j-1,\ell}$ and
$V^{active}_{i,j,\ell-1}$

Now, fix some $i\in[0,10\alpha-1]$, $j\in[1,\log(N)/\alpha]$ and
$\ell\in[1,4\log(N)]$. We compute $V^{active}_{i,j,\ell}$ given
$V^{active}_{i,j-1,\ell}$ and $V^{active}_{i,j,\ell-1}$ by first defining a
bipartite graph $H$, then invoking the hitting set subroutine of Lemma 3.4 to
deduce that there exists an efficient $\mathsf{LOCAL}$ algorithm on the
bipartite graph which computes a subset of $V^{active}_{i,j-1,\ell}$ with the
desired properties, and finally use the fact that we can simulate the
algorithm on the bipartite graph on the original graph with an
$O(\alpha)$-multiplicative overhead. Consider the bipartite graph
$H=(U_{H}\sqcup V_{H},E_{H})$ with $U_{H}=U^{good}_{i,j-1,\ell}\cap
U^{bad}_{i,j,\ell-1}$, $V_{H}=V^{active}_{i,j-1,\ell}$ and where we connect
each node $u\in U_{H}$ to $\deg_{j-1}$ nodes in $S_{i}(u)\cap
V^{active}_{i,j-1,\ell}$. Similar as in Section 4.1, each round in $H$ can be
simulated in $O(\alpha)$ rounds in the original graph and we can assume that
each node is assigned a unique $b$-bit identifier with $b=O(\log N)$. We also
define $Norm_{i,j}=2^{i\cdot\log(N)/\alpha+j}$ for every $i\in[0,10\alpha-1]$
and $j\in[0,\log(N)/\alpha]$.

We now invoke Lemma 3.4 with parameters $\Delta=\deg_{j-1}$, $k=500\log(N)$,
$p=\frac{1}{64\log N}$ and $Norm=Norm_{i,j}2^{j-\ell}$ to conclude that there
exists a $\mathsf{LOCAL}$ algorithm running in $O(\log^{2}\log n)$ rounds on
$H$, and hence can be simulated in $O(\alpha\log^{2}\log n)$ rounds in $G$,
which computes a set $V^{sub}_{i,j,\ell}\subseteq V_{H}$ satisfying

$|\\{u\in U_{H}\colon|N_{H}(u)\cap V^{sub}_{i,j,\ell}|\leq
0.5\lfloor\Delta/k\rfloor\\}|+2^{j-\ell}Norm_{i,j}\cdot|V^{sub}_{i,j,\ell}|\leq
4\left(e^{-pk}|U_{H}|+2^{j-\ell}Norm_{i,j}\cdot p\cdot|V_{H}|\right).$

We then define $V^{active}_{i,j,\ell}=V^{active}_{i,j,\ell-1}\cup
V^{sub}_{i,j,\ell}$.

Consider some $u\in U^{good}_{i,j-1,\ell}\cap U^{bad}_{i,j,\ell}$. As $u\in
U^{bad}_{i,j,\ell}$ implies $u\in U^{bad}_{i,j,\ell-1}$, we have $u\in
U^{good}_{i,j-1,\ell}\cap U^{bad}_{i,j,\ell-1}=:U_{H}$. Moreover,

$|N_{H}(u)\cap V^{sub}_{i,j,\ell}|\leq|S_{i}(u)\cap
V^{active}_{i,j,\ell}|<\deg_{j}=\frac{\deg_{j-1}}{2000\log(N)}\leq
0.5\lfloor\frac{\Delta}{k}\rfloor.$

Hence, using that $e^{-pk}\leq\frac{1}{32}$, we get

$2^{\ell-j}|U^{good}_{i,j-1,\ell}\cap
U^{bad}_{i,j,\ell}|+Norm_{i,j}\cdot|V^{sub}_{i,j,\ell}|\leq\frac{2^{\ell-j}}{8}|U^{bad}_{i,j,\ell-1}|+\frac{Norm_{i,j}}{16\log(N)}|V^{active}_{i,j-1,\ell}|.$

The claim below is the key claim in the analysis.

######  Claim 4.5.

For every $i\in[0,10\alpha-1],j\in[0,\log(N)/\alpha]$ and
$\ell\in[0,4\log(N)]$, it holds that

  1. 1.

$|V^{active}_{i,j}|\leq\frac{2\log(N)\cdot n}{Norm_{i,j}}$ and

  2. 2.

$|U^{bad}_{i,j,\ell}|\leq n\cdot 2^{j-\ell}$.

In particular, $V^{active}_{10\alpha}=\emptyset$ and $\\{u\in
U^{important}_{i}\colon S_{i}(u)\cap V^{active}_{i+1}=\emptyset\\}=\emptyset$
for every $i\in[0,10\alpha-1]$.

###### Proof.

First, consider some fixed $i\in[0,10\alpha-1]$ and $j\in[1,\log(N)/\alpha]$
and assume $|V^{active}_{i,j-1}|\leq\frac{2\log(N)\cdot n}{Norm_{i,j-1}}$ and
$|U^{bad}_{i,j-1,\ell}|\leq n\cdot 2^{(j-1)-\ell}$ for every
$\ell\in[0,4\log(N)]$. In particular, for every $\ell\in[0,4\log(N)-1]$,
$V^{active}_{i,j-1,\ell}\subseteq V^{active}_{i,j-1}$ directly gives

$\frac{Norm_{i,j}}{16\log(N)}|V^{active}_{i,j-1,\ell}|\leq\frac{Norm_{i,j}}{16\log(N)}\frac{2\log(N)\cdot
n}{Norm_{i,j-1}}=\frac{n}{4}.$

We first show by induction on $\ell$ that this implies
$|U^{bad}_{i,j,\ell}|\leq n\cdot 2^{j-\ell}$ for every $\ell\in[0,4\log(N)]$
and afterwards we show that $|V^{active}_{i,j}|\leq\frac{2\log(N)\cdot
n}{Norm_{i,j}}$.

The base case $\ell=0$ trivially holds as $|U^{bad}_{i,j,0}|\leq n\leq n\cdot
2^{j-0}$. Now, fix some $\ell\in[1,4\log(N)]$ and assume that
$|U^{bad}_{i,j,\ell-1}|\leq 2^{j-(\ell-1)}$. First, note that
$U^{bad}_{i,j,\ell}\subseteq V^{important}_{i}=U^{good}_{i,j-1,\ell}\sqcup
U^{bad}_{i,j-1,\ell}$ together with the initial assumption
$|U^{bad}_{i,j-1,\ell}|\leq 2^{(j-1)-\ell}$ implies

$|U^{bad}_{i,j,\ell}|\leq|U^{bad}_{i,j-1,\ell}|+|U^{good}_{i,j-1,\ell}\cap
U^{bad}_{i,j,\ell}|\leq\frac{n\cdot 2^{j-\ell}}{2}+|U^{good}_{i,j-1,\ell}\cap
U^{bad}_{i,j,\ell}|.$

Moreover, using induction, we get

$|U^{good}_{i,j-1,\ell}\cap
U^{bad}_{i,j,\ell}|\leq\frac{1}{8}|U^{bad}_{i,j,\ell-1}|+2^{j-\ell}\frac{Norm_{i,j}}{16\log(N)}|V^{active}_{i,j-1,\ell}|\leq\frac{n2^{j-(\ell-1)}}{8}+\frac{n\cdot
2^{j-\ell}}{4}\leq\frac{n\cdot 2^{j-\ell}}{2}$

and therefore $|U^{bad}_{i,j,\ell}|\leq n\cdot 2^{j-\ell}$, finishing the
induction. Now, consider some $\ell\in[1,4\log(N)]$. Using
$|U^{bad}_{i,j,\ell-1}|\leq n\cdot 2^{j-(\ell-1)}$, we get

$|V^{sub}_{i,j,\ell}|\leq\frac{1}{Norm_{i,j}}\left(\frac{2^{\ell-j}}{8}|U^{bad}_{i,j,\ell-1}|+\frac{Norm_{i,j}}{16\log(N)}|V^{active}_{i,j-1,\ell}|\right)\leq\frac{(n/4)+(n/4)}{Norm_{i,j}}=\frac{n}{2Norm_{i,j}}.$

As $V^{active}_{i,j}=\bigcup_{\ell=1}^{4\log(N)}V^{sub}_{i,j,\ell}$, we
conclude $|V^{active}_{i,j}|\leq\frac{2\log(N)\cdot n}{Norm_{i,j}}$.

Consider some fixed $i\in[0,10\alpha-1]$ and assume that
$|V^{active}_{i,0}|\leq\frac{2\log(N)\cdot n}{Norm_{i,0}}$. We use induction
on $j$ to conclude that $|V^{active}_{i,j}|\leq\frac{2\log(N)\cdot
n}{Norm_{i,j}}$ and $|U^{bad}_{i,j,\ell}|\leq n\cdot 2^{j-\ell}$ for every
$j\in[0,\log(N)/\alpha]$ and $\ell\in[0,4\log(N)]$. For the base case $j=0$,
note that $|V^{active}_{i,0}|\leq\frac{2\log(N)\cdot n}{Norm_{i,0}}$ is just
what we assumed and as $V^{active}_{i,0,\ell}:=V^{active}_{i}$ for every
$\ell\in[0,4\log(N)]$, we have $|U^{bad}_{i,0,\ell}|=0\leq n\cdot 2^{0-\ell}$.
We already did the induction step going from $j-1$ to $j$ above and therefore
we are done.

Finally, we prove Claim 4.5 by induction on $i$. For the base case $i=0$, note
that $|V^{active}_{0,0}|\leq n\leq\frac{2\log(N)\cdot n}{Norm_{0,0}}$. By
using the previous induction on $j$, this is enough to show that the bounds of
Claim 4.5 hold for $i=0$. Now, consider some $i\in[1,10\alpha-1]$ and assume
that the bounds hold for $i-1$. In particular,

$|V^{active}_{i,0}|=|V^{active}_{i-1,\log(N)/\alpha}|\leq\frac{2\log(N)\cdot
n}{Norm_{i-1,\log(N)/\alpha}}=\frac{2\log(N)\cdot n}{Norm_{i,0}}.$

Now, we can again use the previous induction on $j$ to finish the induction
step.

To conclude Claim 4.5, note that
$|V^{active}_{10\alpha-1,\log(N)/\alpha}|\leq\frac{2\log(N)\cdot
n}{Norm_{0,0}}<1$ and as
$V^{active}_{10\alpha}:=V^{active}_{10\alpha-1,\log(N)/\alpha}$, we get that
$V^{active}_{10\alpha}=\emptyset$. Consider some $i\in[0,10\alpha-1]$. Note
that $|U^{bad}_{i,\log(N)/\alpha,4\log(N)}|\leq n\cdot
2^{\log(N)/\alpha-4\log(N)}<1$ and therefore
$U^{bad}_{i,\log(N)/\alpha,4\log(N)}=\emptyset$. In particular, there does not
exist a node $u\in U^{important}_{i}$ with $|S_{i}(u)\cap
V^{active}_{i,\log(N)/\alpha,4\log(N)}|<\deg_{\log(N)/\alpha}=1$. As
$V^{active}_{i+1}:=V^{active}_{i,\log(N)/\alpha}:=V^{active}_{i,\log(N)/\alpha,4\log(N)}$,
we therefore get that there exists no node $u\in U^{important}_{i}$ with
$|S_{i}(u)\cap V^{active}_{i+1}=\emptyset$, as desired. ∎

###### Proof of Theorem 2.1.

According to Claim 4.1, the diameter of the output partition is $O(\alpha)$.
Moreover, combining Claim 4.5 with Lemma 4.2 shows that the clustering of each
node is $2^{\widetilde{O}(\log n)/\alpha}$. It remains to argue about the
round complexity of the algorithm. Fix some $i\in[0,10\alpha-1]$. Note that
given $V^{active}_{i}$, we can compute $V^{active}_{i,j,0}$ for every
$j\in[0,\log(N)/\alpha]$ and $V^{active}_{i,0,\ell}$ for every
$\ell\in[1,4\log(N)]$ without further communication. Moreover, we have seen
above that given $V^{active}_{i,j-1,\ell}$ and $V^{active}_{i,j,\ell-1}$, we
can compute $V^{active}_{i,j,\ell}$ in $O(\alpha\log^{2}\log n)$ rounds, for
every $j\in[1,\log(N)/\alpha]$ and $\ell\in[1,4\log(N)]$. Hence, a simple
induction shows that given $V^{active}_{i}$, we can compute
$V^{active}_{i,j,\ell}$ in $(j+\ell)O(\alpha\log^{2}\log n)$ rounds for every
$j\in[0,\log(N)/\alpha]$ and $\ell\in[0,4\log(N)]$ and therefore we can
compute $V^{active_{i+1}}$ in $(\log(N)/\alpha+4\log(N))\cdot
O(\alpha\log^{2}\log n)=\widetilde{O}(\alpha\log n)$ rounds. Hence, the
overall algorithm runs in $\widetilde{O}(\alpha^{2}\log n)$ rounds, as
desired. ∎

##  5 Matching and MIS

In this section, we use the low-diameter clustering results obtained in the
previous section in order to obtain faster deterministic algorithms for MIS
and $(1+\varepsilon)$-approximate maximum matching.

###  5.1 Approximate Matching

We start with the matching algorithm. In particular, this section is devoted
to proving the theorem below.

See 1.2

#### Notation

Let $E$ be an arbitrary set of edges and $v$ be an arbitrary node. We define
$E(v)=\\{e\in E\colon v\in e\\}$ as the set consisting of those edges in $E$
that are incident to $v$. As before, $N$ is a polynomial upper bound on the
number of vertices given to the algorithm.

#### Computing a Constant Approximate Fractional Matching

A fractional matching assigns each edge $e\in E$ a value
$x_{e}\in\mathbb{R}_{\geq 0}$ such that for every $v\in V$, $\sum_{e\in
E(v)}x_{e}\leq 1$. It is well-known how to compute a fractional matching in
$O(\log n)$ rounds such that $\sum_{e\in E}x_{e}\geq\frac{1}{5}|M^{*}|$, where
$M^{*}\subseteq E$ is a maximum matching of the input graph $G=(V,E)$.
Moreover, one can also ensure that $x_{e}\geq\frac{1}{n}$ for every edge $e\in
E$, which is a technicality needed later. See for example [Fis20].

#### Computing a Low-Diameter Clustering

For every $v\in V$, let $y_{v}:=\sum_{e\in E(v)}x_{e}$. Using Theorem 2.2 with
$\alpha=\log^{1/3}(N)$, we can conclude that there exists some function
$f(n)=2^{\widetilde{O}(\log^{2/3}(n))}$ and a $\mathsf{LOCAL}$ algorithm
running in $\widetilde{O}(\log^{4/3}n)$ rounds which computes a partition
$\mathcal{C}$ with diameter $O(\log^{1/3}n)$ such that a large constant
fraction of vertices, weighted by the $y_{v}$’s, has a cluster degree of at
most $f(n)$. More precisely, let $V^{good}:=\\{v\in
V\colon\deg_{\mathcal{C}}(v)\leq f(n)\\}$ be the set of nodes with cluster
degree at most $f(n)$, then it holds that $\sum_{v\in V^{good}}y_{v}\geq
0.9\sum_{v\in V}y_{v}$. Note that $y_{v}\geq\frac{1}{n}$ for every $v\in V$,
which is one of the assumptions of Theorem 2.2. This directly follows from
$x_{e}\geq\frac{1}{n}$ for every $e\in E$ and that we can assume without loss
of generality that the input graph does not have any isolated vertices.

Now, let $E^{good}$ be defined as the set of edges in $E$ with both endpoints
being contained in $V^{good}$. The following simple claim implies that we can
restrict our attention to edges where both endpoints have a small clustering
degree.

######  Claim 5.1.

It holds that $\sum_{e\in E^{good}}x_{e}\geq 0.8\sum_{e\in E}x_{e}$.

###### Proof.

We have

$\displaystyle\sum_{e\in E^{good}}x_{e}\geq\sum_{e\in E}x_{e}-\sum_{v\in
V\setminus V^{good}}y_{v}\geq\sum_{e\in E}x_{e}-0.1\sum_{v\in V}y_{v}$
$\displaystyle=\sum_{e\in E}x_{e}-0.2\sum_{e\in E}x_{e}=0.8\sum_{e\in
E}x_{e}.$

∎

#### Intra-Cluster Rounding

In the intra-cluster step, we start with the fractional matching $x$ and turn
it into a $\frac{1}{50000f(n)\log(n)}$-integral matching $x^{intra}$ supported
on $E^{good}$. Moreover, the total weight of the new fractional matching
$x^{intra}$ is at most a constant factor smaller compared to the weight of the
fractional matching $x$.

For every cluster $C\in\mathcal{C}$, let $E_{C}^{good}$ denote the set
consisting of those edges in $E^{good}$ whose endpoint with the larger
identifier is contained in $C$. A key property of the fractional matching
$x^{intra}$ computed in the intra-cluster step is the following: for every
edge $e\in E_{C}^{good}$, the fractional value $x^{intra}_{e}$ assigned to $e$
is merely a function of the fractional values assigned to the edges in
$E^{good}_{C}$ by the fractional matching $x$. As the $\mathsf{LOCAL}$ model
does not restrict message sizes and the diameter of each cluster $C$ is
$O(\log^{1/3}n)$, this property allows us to compute the fractional matching
$x^{intra}$ in $O(\log^{1/3}n)$ rounds.

Fix some cluster $C\in\mathcal{C}$. We use the probabilistic method to argue
that we can assign each edge $e\in E^{good}_{C}$ a value $x^{intra}_{e}$ such
that certain conditions are satisfied. These conditions only depend on the
fractional values assigned to the edges in $E^{good}_{C}$ by the fractional
matching $x$.

To that end, we introduce one random variable $X^{intra}_{e}$ for every edge
$e\in E^{good}_{C}$. If $x_{e}\geq\frac{1}{10000f(n)\log(n)}$, we simply set
$X^{intra}_{e}=\frac{x_{e}}{5}$. Otherwise, if
$x_{e}<\frac{1}{10000f(n)\log(n)}$, we set
$X^{intra}_{e}=\frac{1}{50000f(n)\log(n)}$ with probability
$10000f(n)\log(n)x_{e}$ and with the remaining probability we set
$X^{intra}_{e}=0$, fully independently. Note that
$\operatorname{\mathbb{E}}[X^{intra}_{e}]=\frac{x_{e}}{5}$ for every edge
$e\in E^{good}_{C}$. The following claim follows by a simple Chernoff bound.

######  Claim 5.2.

For any subset $E^{\prime}\subseteq E^{good}_{C}$, we have

$Pr\left[\sum_{e\in E^{\prime}}X^{intra}_{e}\leq\frac{1}{2}\sum_{e\in
E^{\prime}}x_{e}+\frac{1}{1000f(n)}\right]\geq 1-\frac{1}{n^{3}}\text{ and}$
$Pr\left[\sum_{e\in E^{\prime}}X^{intra}_{e}\geq\frac{1}{10}\sum_{e\in
E^{\prime}}x_{e}-\frac{1}{1000f(n)}\right]\geq 1-\frac{1}{n^{3}}.$

###### Proof.

Let $E^{\prime small}$ be the set of all edges $e\in E^{\prime}$ such that
$x_{e}<\frac{1}{10000f(n)\log(n)}$ and let $X:=\sum_{e\in E^{\prime
small}}X^{intra}_{e}$. Note that $X$ is the sum of independent random
variables taking values between $0$ and $b:=\frac{1}{50000f(n)\log(n)}$ and
$\operatorname{\mathbb{E}}[X]=\sum_{e\in E^{\prime small}}\frac{x_{e}}{5}$.
Let $t:=\frac{1}{10}\sum_{e\in E^{\prime small}}x_{e}+\frac{1}{1000f(n)}$. We
have $t\geq 0.5\operatorname{\mathbb{E}}[X]$ and therefore we can use the
Chernoff bound variant given in Corollary 3.2 to deduce

$Pr\left[|X-\operatorname{\mathbb{E}}[X]|\geq t\right]\leq
2e^{-\frac{t}{6b}}\leq n^{-3}.$

Now, assume that $|X-\operatorname{\mathbb{E}}[X]|\leq t$. Then,

$\sum_{e\in E^{\prime}}X^{intra}_{e}=\sum_{e\in E^{\prime}\setminus E^{\prime
small}}X^{intra}_{e}+X\leq\sum_{e\in E^{\prime}\setminus E^{\prime
small}}\frac{x_{e}}{5}+\operatorname{\mathbb{E}}[X]+t=\sum_{e\in
E^{\prime}}\frac{x_{e}}{5}+t\leq\sum_{e\in
E^{\prime}}\frac{x_{e}}{2}+\frac{1}{1000f(n)}.$

Similarly,

$\sum_{e\in E^{\prime}}X^{intra}_{e}\geq\sum_{e\in E^{\prime}\setminus
E^{\prime small}}X^{intra}_{e}+\operatorname{\mathbb{E}}[X]-t=\sum_{e\in
E^{\prime}}\frac{x_{e}}{5}-t\geq\sum_{e\in
E^{\prime}}\frac{x_{e}}{10}-\frac{1}{1000f(n)}.$

∎

Claim 5.2 together with a simple union bound implies that the following holds
with strictly positive probability: for every vertex $v\in V$,

$\frac{1}{10}\sum_{e\in E^{good}_{C}(v)}x_{e}-\frac{1}{1000f(n)}\leq\sum_{e\in
E^{good}_{C}(v)}X^{intra}_{e}\leq\frac{1}{2}\sum_{e\in
E^{good}_{C}(v)}x_{e}+\frac{1}{1000f(n)}.$

Therefore, using brute-force computation, each cluster $C$ can compute in
$O(\log^{1/3}(n))$ rounds a value
$x^{intra}_{e}\in\\{0\\}\cup\left[\frac{1}{50000f(n)\log(n)},1\right]$ for
every edge $e\in E^{good}_{C}$ such that for every vertex $v\in V$,

$\frac{1}{10}\sum_{e\in E^{good}_{C}(v)}x_{e}-\frac{1}{1000f(n)}\leq\sum_{e\in
E^{good}_{C}(v)}x^{intra}_{e}\leq\frac{1}{2}\sum_{e\in
E^{good}_{C}(v)}x_{e}+\frac{1}{1000f(n)}.$ (2)

We first use the upper bound in Eq. 2 together with the fact that each node
$v\in V^{good}$ has a clustering degree of at most $f(n)$ to deduce that
$x^{intra}$ is a valid fractional matching.

######  Claim 5.3.

For every vertex $v\in V^{good}$, we have $\sum_{e\in
E^{good}(v)}x^{intra}_{e}\leq 1$.

###### Proof.

Let $v\in V^{good}$ be arbitrary. We have

$\displaystyle\sum_{e\in E^{good}(v)}x^{intra}_{e}$
$\displaystyle=\sum_{C\in\mathcal{C}\colon
E^{good}_{C}(v)\neq\emptyset}\sum_{e\in E^{good}_{C}(v)}x^{intra}_{e}$
$\displaystyle\leq\sum_{C\in\mathcal{C}\colon
E^{good}_{C}(v)\neq\emptyset}\left(\frac{1}{2}\sum_{e\in
E^{good}_{C}(v)}x_{e}+\frac{1}{1000f(n)}\right)$
$\displaystyle\leq\frac{1}{2}\sum_{e\in
E^{good}(v)}x_{e}+\frac{\deg_{\mathcal{C}}(v)}{1000f(n)}$
$\displaystyle\leq\frac{1}{2}+\frac{1}{1000}\leq 1,$

as needed.

∎

Next, we use the lower bound of Eq. 2 together with the fact that $\sum_{e\in
E^{good}}x_{e}\geq 0.8\frac{1}{5}|M^{*}|\geq\frac{1}{10}|M^{*}|$ to deduce
that $\sum_{e\in E^{good}}x^{intra}_{e}\geq\frac{1}{40000}|M^{*}|$.

######  Claim 5.4.

We have $\sum_{e\in E^{good}}x^{intra}_{e}\geq\frac{1}{40000}|M^{*}|$.

###### Proof.

Consider some arbitrary vertex $v\in V^{good}$ with $y^{good}_{v}:=\sum_{e\in
E^{good}(v)}x_{e}\geq\frac{1}{50}$. We have

$\displaystyle y^{intra}_{v}$ $\displaystyle:=\sum_{e\in
E^{good}(v)}x^{intra}_{e}=\sum_{C\in\mathcal{C}\colon
E^{good}_{C}(v)\neq\emptyset}\sum_{e\in E^{good}_{C}(v)}x^{intra}_{e}$
$\displaystyle\geq\sum_{C\in\mathcal{C}\colon
E^{good}_{C}(v)\neq\emptyset}\left(\frac{1}{10}\sum_{e\in
E^{good}_{C}(v)}x_{e}-\frac{1}{1000f(n)}\right)$
$\displaystyle\geq\frac{1}{10}\sum_{e\in
E^{good}(v)}x_{e}-\frac{\deg_{\mathcal{C}}(v)}{1000f(n)}$
$\displaystyle\geq\frac{1}{500}-\frac{1}{1000}=\frac{1}{1000}.$

Therefore,

$\sum_{e\in E^{good}}x^{intra}_{e}=\frac{1}{2}\sum_{v\in
V^{good}}y^{intra}_{v}\geq\frac{1}{2}\sum_{v\in V^{good}\colon
y^{good}_{v}\geq\frac{1}{50}}y^{intra}_{v}\geq\frac{1}{2000}|v\in
V^{good}\colon y^{good}_{v}\geq\frac{1}{50}|.$

Let $E^{loose}$ consists of all edges $\\{u,v\\}$ in $E^{good}$ with
$\max(y^{good}_{u},y^{good}_{v})<\frac{1}{50}$. Note that multiplying the
fractional value $x_{e}$ assigned to each edge $e$ in $E^{loose}$ by a factor
of $50$ would still result in a valid fractional matching. The value of the
fractional matching would be at least $\sum_{e\in E^{loose}}50x_{e}$. On the
other hand, it is well-known that the value of any fractional matching is at
most by a $(3/2)$-factor larger than the size of the maximum matching.
Therefore, we get

$\sum_{e\in E^{loose}}50x_{e}\leq(3/2)|M^{*}|.$

Thus,

$|v\in V^{good}\colon y^{good}_{v}\geq\frac{1}{50}|\geq\sum_{v\in
V^{good}\colon y^{good}_{v}\geq\frac{1}{50}}y_{v}\geq\sum_{e\in
E^{good}}x_{e}-\sum_{e\in
E^{loose}}x_{e}\geq\frac{|M^{*}|}{10}-\frac{(3/2)|M^{*}|}{50}.$

Hence, we can conclude that

$\sum_{e\in E^{good}}x^{intra}_{e}\geq\frac{1}{2000}|v\in V^{good}\colon
y^{good}_{v}\geq\frac{1}{50}|\geq\frac{1}{2000}\left(\frac{|M^{*}|}{10}-\frac{(3/2)|M^{*}|}{50}\right)\geq\frac{|M^{*}|}{40000}.$

∎

#### Local Rounding

Let $E^{\prime}$ consists of all edges $e$ in $E^{good}$ with
$x^{intra}_{e}>0$, let $G^{\prime}:=(V,E^{\prime})$ and $\Delta^{\prime}$ the
maximum degree of $G^{\prime}$. Note that
$x^{intra}_{e}\geq\frac{1}{50000f(n)\log(n)}$ for every $e\in E^{\prime}$
together with $\sum_{e\in E^{\prime}(v)}x^{intra}_{e}\leq 1$ for every $v\in
V$ directly implies that $\Delta^{\prime}\leq
50000f(n)\log(n)=2^{\widetilde{O}\log^{2/3}(n)}$. Therefore, in
$O(\log^{2}(\Delta^{\prime})+\log^{*}n)=\widetilde{O}(\log^{4/3}n)$ rounds we
can compute a $3$-approximate maximum matching $M^{\prime}$ in $G^{\prime}$
using the algorithm of Fischer [Fis20]. Using the fact that the weight of any
fractional matching is at most a factor of $(3/2)$ larger compared to the size
of the largest integral matching, we get

$|M^{\prime}|\geq\frac{1}{3}\left((2/3)\sum_{e\in
E^{\prime}}x^{intra}_{e}\right)=\frac{2}{9}\sum_{e\in
E^{good}}x^{intra}_{e}\geq\frac{1}{100000}|M^{*}|.$

Therefore, $M^{\prime}$ is a constant approximate matching of $G$, which
finishes the proof of Theorem 1.2.

###  5.2 MIS

In this section, we describe a deterministic distributed algorithm that
computes an MIS in $\widetilde{O}(\log^{2}n)$ rounds of the $\mathsf{LOCAL}$
model.

See 1.1

The rest of the section is devoted to the proof of Theorem 1.1. We first
recall Luby’s classic algorithm[Lub86], which in each iteration chooses an
independent set of nodes such that, when we add them to the output and remove
them from the graph along with their neighbors, in expectation a constant
fraction of the edges of the graph are removed.

#### Luby’s Randomized MIS Algorithm.

The starting point is to recall Luby’s classic randomized algorithm from
[Lub93]. Each iteration of it works as follows. We mark each node $u$ with
probability $1/(10\deg(u))$. Then, for each edge $\\{u,v\\}$, let us orient
the edge as $u\rightarrow v$ if and only if $\deg(u)<\deg(v)$ or
$\deg(u)=\deg(v)$ and $ID(u)<ID(v)$. For each marked node $u$, we add $u$ to
the independent set if and only if $v$ does not have a marked out-neighbor.
Finally, as a clean-up step at the end of this iteration, we remove all nodes
that have been added to the independent set along with their neighbors. We
then proceed to the next iteration.

#### Derandomizing Luby via Rounding.

It is well-known that in each iteration of Luby’s algorithm a constant
fraction of the edges of the remaining graph gets removed, in expectation.
Hence, the process terminates in $O(\log n)$ iterations with probability
$1-1/\operatorname{\text{{\rm poly}}}(n)$. We explain how to derandomize each
iteration of the algorithm in $\widetilde{O}(\log n)$ rounds, such that we
still remove a constant fraction of the edges per iteration. For the rest of
this proof, we focus on an arbitrary iteration, and we assume that
$H=(V_{H},E_{H})$ is the graph induced by the remaining vertices at the
beginning of this iteration. Let $\vec{x}\in\\{0,1\\}^{V_{H}}$ be the
indicator vector of whether different nodes are marked, that is, we have
$x_{v}=1$ if $v$ is marked and $x_{v}=0$ otherwise. Let $R_{v}(\vec{x})$ be
the indicator variable of the event that $v$ gets removed, for the marking
vector $\vec{x}$. Let $Z(\vec{x})$ be the corresponding number of removed
edges. Luby’s algorithm determines the markings $\vec{x}$ randomly. Our task
is to derandomize this and select the marked nodes in a deterministic way such
that when we remove nodes added to the independent set (those marked nodes
that do not have a marked out-neighbor) and their neighbors, along with all
the edges incident on these nodes, at least a constant fraction of edges $E$
get removed.

Below, we give a pairwise analysis which shows that the expected number of
removed edges is $\Omega(|E_{H}|)$. The rounding framework of Faour et al.
[FGG+23] would then allow us to select the marked nodes in a deterministic way
while retaining the guarantee that $\Omega(|E_{H}|)$ edges are removed. The
rounding procedure runs in $O(\log^{2}(1/p_{min}))=O(\log^{2}\Delta)$ rounds
where $p_{min}$ is the smallest marking probability. In fact, this is how
Faour et al. [FGG+23] obtained an MIS algorithm running in $O(\log
n\log^{2}\Delta)$ rounds. We derandomize the marking process in
$\widetilde{O}(\log n)$ rounds. To do so, we first perform an intra-cluster
rounding step and only then apply the rounding framework of Faour et al.
[FGG+23]. In the intra-cluster rounding step, we compute for each node a
marking probability which is either $0$ or $1/2^{\widetilde{O}(\sqrt{\log
n})}$ and such that the expected number of removed edges is still
$\Omega(|E_{H}|)$. Then, we apply the rounding framework of Faour et al. to
the same pairwise analysis as before, but this time with the new marking
probabilities. As all non-zero marking probabilities are
$1/2^{\widetilde{O}(\sqrt{\log n})}$, the rounding procedure runs in just
$\left(\log(2^{\widetilde{O}(\sqrt{\log n})})\right)^{2}=\widetilde{O}(\log
n)$ rounds, as desired.

#### Good and bad nodes and prevalence of edges incident on good nodes.

We call any node $v\in V_{H}$ _good_ if and only if it has at least
$\deg(v)/3$ incoming edges. A node $v$ that is not good is called bad. It can
be proven [Lub93] that

$\displaystyle\sum_{\textit{good vertex\;}v}\deg(v)\geq|E_{H}|/2.$ (3)

Even though the reader may skip this paragraph, for completeness we include
the reason as it is a simple and intuitive charging argument. Recall that by
definition any bad node has less than $1/3$ of its edges incoming. Thus any
edge incoming to a bad node $v$ can be charged to two unique edges going out
of $v$, in such a manner that each edge of the graph is charged at most once.
Hence, the number of edges incoming to bad nodes is at most $|E_{H}|/2$. Thus,
the number of edges that have at least one good endpoint is at least
$|E_{H}|/2$, which implies the desired bound $\sum_{\textit{good
vertex\;}v}\deg(v)\geq|E_{H}|/2$.

#### Lower bounding removed edges.

We can lower bound the number of removed edges as

$Z(\vec{x})\geq\sum_{\textit{good vertex\;}v}\deg(v)\cdot R_{v}(\vec{x})/2.$

The $2$ factor in the denominator is because for an edge, both endpoints might
be good nodes. Since $\sum_{\textit{good vertex\;}v}\deg(v)\geq|E_{H}|/2$, to
prove that $\mathbb{E}[Z(\vec{x})]=\Omega(|E_{H}|)$, it suffices to show that
each good vertex $v$ has $Pr[R_{v}(\vec{x})]=\Omega(1)$. This fact can be
proven via elementary probability calculations. Next, we discuss how to prove
it using only pairwise independence in the analysis.

#### Pessimistic estimator of removed edges via pairwise-independent analysis.

Let us use $IN(u)$ and $OUT(u)$ to denote in-neighbors and out-neighbors of a
vertex $u$. Consider a good node $v$ and consider all its incoming neighbors
$u$, i.e., neighbors $u$ such that $(\deg(u),ID(u))<(\deg(v),ID(v))$. Since
$v$ is good, it has at least $\deg(v)/3$ such neighbors. Hence, we have

$\sum_{\textit{incoming neighbor}\;u}\frac{1}{\deg(u)}\geq 1/3.$

Choose a subset $IN^{*}(v)\subseteq IN(v)$ of incoming neighbors such that

$\displaystyle\sum_{u\in IN^{*}(v)}\frac{1}{\deg(u)}\in[1/3,4/3].$ (4)

Notice that such a subset $IN^{*}(v)$ exists since the summation over all
incoming neighbors is at least $1/3$ and each neighbor contributes at most $1$
to the summation. On the other hand, notice that for any node $u$, we have

$\displaystyle\sum_{w\in OUT(u)}\frac{1}{\deg(w)}\leq 1.$ (5)

This is because $|OUT(u)|\leq\deg(u)$ and for each ${w}\in OUT(u)$, we have
$(\deg({w}),ID({w}))>(\deg(u),ID(u))$.

A sufficient event $\mathcal{E}(v,u)$ that causes $v$ to be removed is if some
$u\in IN^{*}(v)$ is marked and no other node in $IN^{*}(v)\cup OUT(u)$ is
marked. By union bound, this event’s indicator is lower bounded by

$x_{u}-\sum_{u^{\prime}\in IN^{*}(v),u\neq u^{\prime}}x_{u}\cdot
x_{u^{\prime}}-\sum_{w\in OUT(u)}x_{u}\cdot x_{w}.$

Furthermore, the events
$\mathcal{E}(v,u_{1}),\mathcal{E}(v,u_{2}),\dots,\mathcal{E}(v,u_{|IN^{*}(v)|})$
are mutually disjoint for different $u_{1},u_{2},\dots,$ $u_{|IN^{*}(v)|}\in
IN^{*}(v)$. Hence, we can sum over these events for different $u\in IN^{*}(v)$
and conclude that

$\displaystyle R_{v}(\vec{x})\geq\sum_{u\in
IN^{*}(v)}\bigg{(}x_{u}-\sum_{u^{\prime}\in IN^{*}(v),u\neq
u^{\prime}}x_{u}\cdot x_{u^{\prime}}-\sum_{w\in OUT(u)}x_{u}\cdot
x_{w}\bigg{)}$ $\displaystyle=\sum_{u\in IN^{*}(v)}x_{u}-\sum_{u,u^{\prime}\in
IN^{*}(v)}x_{u}\cdot x_{u^{\prime}}-\sum_{u\in IN^{*}(v)}\sum_{w\in
OUT(u)}x_{u}\cdot x_{w}$

Therefore, our overall pessimistic estimator for the number of removed edges
gives that

$\displaystyle Z(\vec{x})\geq$ $\displaystyle\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot R_{v}(\vec{x})$ $\displaystyle\geq$
$\displaystyle\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\bigg{(}\sum_{u\in IN^{*}(v)}x_{u}-\sum_{u,u^{\prime}\in
IN^{*}(v)}x_{u}\cdot x_{u^{\prime}}-\sum_{u\in IN^{*}(v)}\sum_{w\in
OUT(u)}x_{u}\cdot x_{w}\bigg{)}.$

#### Intra-Cluster Rounding

For the intra-cluster rounding step, we assume that we are given a partition
$\mathcal{C}_{G}$ of the input graph $G$ with diameter $O(\sqrt{\log n})$ and
such that $\deg_{\mathcal{C}_{G}}(u)\leq f(n)$ for every $u\in V$ and for some
function $f(n)=2^{\widetilde{O}(\sqrt{\log n})}$.

Indeed, invoking Theorem 2.1 with $\alpha=\sqrt{\log(N)}$, we can compute such
a partition $\mathcal{C}_{G}$ at the very beginning in
$\widetilde{O}(\log^{2}n)$ rounds. Also, we denote by
$\mathcal{C}_{H}=\\{C\cap V_{H}\colon C\in\mathcal{C}_{G}\\}$ the partition of
$H$ that we obtain from the partition $\mathcal{C}_{G}$ by removing from each
cluster the vertices not contained in $V_{H}$.

Now, consider that we relax the label assignment such that it also allows for
a fractional assignment $\vec{x}\in[0,1]^{V_{H}}$. Then, $Z(\vec{x})$ is a
pessimistic estimator on the expected number of edges removed if we mark each
vertex $u$ fully independently (or pairwise independent) with probability
$x_{u}$. In Luby’s algorithm, one marks each node $u\in V_{H}$ with
probability $x_{u}:=\frac{1}{20\deg(u)}$, and a simple calculation shows that
for this marking probability we get $Z(\vec{x})=\Omega(|E_{H}|)$. In the
intra-cluster rounding step, the goal is to compute a
$\frac{1}{10000f(n)\log(n)}$-integral assignment
$\vec{x}^{intra}\in[0,1]^{V_{H}}$ such that we have
$Z(\vec{x}^{intra})=\Omega(|E_{H}|)$.

Consider some fixed cluster $C\in\mathcal{C}_{H}$. For any $u\in C$, we define
$\vec{x}^{intra}$ in such a way that we can compute $x^{intra}_{u}$ by only
knowing the cluster $C$ (together with the $k$-hop neighborhood around $C$ for
some $k=O(1)$). As the weak-diameter of $C$ in the original input graph is
$O(\sqrt{\log n})$, we can compute $x^{intra}_{u}$ in $O(\sqrt{\log n})$
rounds. Similar as in the intra-cluster rounding step for constant approximate
matching, we will use the probabilistic method to show that a fractional
assignment with certain desirable properties exist.

To that end, we introduce one random variable $X^{intra}_{u}$ for every vertex
$u\in C$. If $\deg(u)\leq 1000f(n)\log(n)$, we simply set
$X^{intra}_{u}=\frac{1}{10\deg(u)}$. Otherwise, if $\deg(u)>1000f(n)\log(n)$,
we set $X^{intra}_{u}=\frac{1}{10000f(n)\log(n)}$ with probability
$\frac{1000f(n)\log(n)}{\deg(u)}$ and with the remaining probability we set
$X^{intra}_{u}=0$, fully independently. Note that for every $u\in C$,
$\operatorname{\mathbb{E}}[X_{u}]=\frac{1}{10\deg(u)}$.

The following claim follows by a simple Chernoff bound.

######  Claim 5.5.

For any subset $S\subseteq C$, we have

$Pr\left[\sum_{u\in S}X^{intra}_{u}\leq\frac{1}{5}\sum_{u\in
S}\frac{1}{\deg(u)}+\frac{1}{100f(n)}\right]\geq 1-\frac{1}{n^{10}}\text{
and}$ $Pr\left[\sum_{u\in S}X^{intra}_{u}\geq\frac{1}{20}\sum_{u\in
S}\frac{1}{\deg(u)}-\frac{1}{100f(n)}\right]\geq 1-\frac{1}{n^{10}}.$

###### Proof.

Let $S^{large}$ consists of all nodes $u\in S$ with $\deg(u)>1000f(n)\log(n)$
and let $X:=\sum_{u\in S^{large}}X^{intra}_{u}$. Note that $X$ is the sum of
independent random variables taking values between $0$ and
$b:=\frac{1}{10000f(n)\log(n)}$ and $\operatorname{\mathbb{E}}[X]=\sum_{u\in
S^{large}}\frac{1}{10\deg(u)}$. Let $t:=\frac{1}{20}\sum_{u\in
S^{large}}\frac{1}{\deg(u)}+\frac{1}{100f(n)}$. We have $t\geq
0.5\operatorname{\mathbb{E}}[X]$ and therefore we can use the Chernoff bound
variant given in Corollary 3.2 to deduce

$Pr\left[|X-\operatorname{\mathbb{E}}[X]|\geq t\right]\leq
2e^{-\frac{t}{6b}}\leq n^{-10}.$

Now, assume that $|X-\operatorname{\mathbb{E}}[X]|\leq t$. Then,

$\sum_{u\in S}X^{intra}_{u}=\sum_{u\in S\setminus
S^{large}}X^{intra}_{u}+X\leq\sum_{u\in S\setminus
S^{large}}\frac{1}{10\deg(u)}+\operatorname{\mathbb{E}}[X]+t=\sum_{u\in
S}\frac{1}{10\deg(u)}+t\leq\sum_{u\in S}\frac{1}{5\deg(u)}+\frac{1}{100f(n)}.$

Similarly,

$\sum_{u\in S}X^{intra}_{u}\geq\sum_{u\in S\setminus
S^{large}}\frac{1}{10\deg(u)}+\operatorname{\mathbb{E}}[X]-t=\sum_{u\in
S}\frac{1}{10\deg(u)}-t\geq\sum_{u\in
S}\frac{1}{20\deg(u)}-\frac{1}{100f(n)}.$

∎

Claim 5.5 together with a simple union bound implies that the following holds
with strictly positive probability: for every good vertex $v$,

$\frac{1}{20}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}-\frac{1}{100f(n)}\leq\sum_{u\in IN^{*}(v)\cap
C}X^{intra}_{u}\leq\frac{1}{5}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}+\frac{1}{100f(n)}$

and for every vertex $u\in V_{H}$,

$\sum_{w\in OUT(u)\cap C}X^{intra}_{w}\leq\frac{1}{5}\sum_{w\in OUT(u)\cap
C}\frac{1}{\deg(w)}+\frac{1}{100f(n)}.$

Therefore, each cluster $C$ can compute in $O(\sqrt{\log n})$ rounds a value
$x^{intra}_{u}\in\\{0\\}\cup\left[\frac{1}{10000f(n)\log(n)},1\right]$ for
every node $u\in C$ such that for every good vertex $v$,

$\frac{1}{20}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}-\frac{1}{100f(n)}\leq\sum_{u\in IN^{*}(v)\cap
C}x^{intra}_{u}\leq\frac{1}{5}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}+\frac{1}{100f(n)}$

and for every vertex $u\in V_{H}$,

$\sum_{w\in OUT(u)\cap C}x^{intra}_{w}\leq\frac{1}{5}\sum_{w\in OUT(u)\cap
C}\frac{1}{\deg(w)}+\frac{1}{100f(n)}.$

We use these properties together with the fact that the degree of the
clustering $\mathcal{C}_{H}$ is at most $f(n)$ to prove the claim below.

######  Claim 5.6.

For every good vertex $v$, we have

$1/1000\leq\sum_{u\in IN^{*}(v)}x^{intra}_{u}\leq 1/3.$

For every $u\in V_{H}$, we have $\sum_{w\in OUT(u)}x^{intra}_{w}\leq 1/4$.

###### Proof.

Let $v$ be an arbitrary good vertex. We have

$\displaystyle\sum_{u\in IN^{*}(v)}x^{intra}_{u}$
$\displaystyle=\sum_{C\in\mathcal{C}_{H}\colon IN^{*}(v)\cap
C\neq\emptyset}\sum_{u\in IN^{*}(v)\cap C}x^{intra}_{u}$
$\displaystyle\leq\sum_{C\in\mathcal{C}_{H}\colon IN^{*}(v)\cap
C\neq\emptyset}\left(\frac{1}{5}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}+\frac{1}{100f(n)}\right)$
$\displaystyle\leq\frac{1}{5}\sum_{u\in
IN^{*}(v)}\frac{1}{\deg(u)}+\frac{\deg_{\mathcal{C}_{H}}(v)}{100f(n)}$
$\displaystyle\leq\frac{1}{5}\frac{4}{3}+\frac{1}{100}$ $\displaystyle\leq
1/3,$

where we used Eq. 4.

Similarly,

$\displaystyle\sum_{u\in IN^{*}(v)}x^{intra}_{u}$
$\displaystyle=\sum_{C\in\mathcal{C}_{H}\colon IN^{*}(v)\cap
C\neq\emptyset}\sum_{u\in IN^{*}(v)\cap C}x^{intra}_{u}$
$\displaystyle\geq\sum_{C\in\mathcal{C}_{H}\colon IN^{*}(v)\cap
C\neq\emptyset}\left(\frac{1}{20}\sum_{u\in IN^{*}(v)\cap
C}\frac{1}{\deg(u)}-\frac{1}{100f(n)}\right)$
$\displaystyle\geq\frac{1}{20}\sum_{u\in
IN^{*}(v)}\frac{1}{\deg(u)}-\frac{\deg_{\mathcal{C}_{H}}(v)}{100f(n)}$
$\displaystyle\geq\frac{1}{20}\frac{1}{3}-\frac{1}{100}$ $\displaystyle\geq
1/1000,$

where we used Eq. 4.

Next, consider an arbitrary $u\in V_{H}$. In a similar fashion as above, we
have

$\displaystyle\sum_{w\in OUT(u)}x^{intra}_{w}$
$\displaystyle=\sum_{C\in\mathcal{C}_{H}\colon OUT(u)\cap
C\neq\emptyset}\sum_{w\in OUT(u)\cap C}x^{intra}_{w}$
$\displaystyle\leq\sum_{C\in\mathcal{C}_{H}\colon OUT(u)\cap
C\neq\emptyset}\left(\frac{1}{5}\sum_{w\in OUT(u)\cap
C}\frac{1}{\deg(w)}+\frac{1}{100f(n)}\right)$
$\displaystyle\leq\frac{1}{5}\sum_{w\in
OUT(u)}\frac{1}{\deg(w)}+\frac{\deg_{\mathcal{C}_{H}}(u)}{100f(n)}$
$\displaystyle\leq\frac{1}{5}+\frac{1}{100}$ $\displaystyle\leq 1/4,$

where we used Eq. 5. ∎

#### Local Rounding

We next round the fractional solution $\vec{x}^{intra}$ to an integral
solution $\vec{y}$ using the rounding framework of Faour et al. [FGG+23], as
discussed in Section 3.2.

For a given label assignment $\vec{x}\in\\{0,1\\}^{V_{H}}$, we define the
utility function as

$\mathbf{u}(\vec{x})=\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\big{(}\sum_{u\in IN^{*}(v)}x_{u}\big{)},$

and the cost function as

$\mathbf{c}(\vec{x})=\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\bigg{(}\sum_{u,u^{\prime}\in IN^{*}(v)}x_{u}\cdot
x_{u^{\prime}}+\sum_{u\in IN^{*}(v)}\sum_{w\in OUT(u)}x_{u}\cdot
x_{w}\bigg{)}.$

If the label assignment is relaxed to be a fractional assignment
$\vec{x}\in[0,1]^{V_{H}}$, where intuitively now $x_{u}$ is the probability of
$u$ being marked, the same definitions apply for the utility and cost of this
fractional assignment.

Let $H^{2}$ denote the graph where any two nodes of distance at most $2$ in
$H$ are connected by an edge. Note that $\mathbf{u}(\vec{x})$ is a utility
function in the graph $H^{2}$ and similarly $\mathbf{c}(\vec{x})$ is a cost
function in the graph $H^{2}$. We next argue that the utility and cost
function also satisfy the key requirement of Lemma 3.3:

######  Claim 5.7.

For the fractional label assignment $\vec{x}^{intra}\in[0,1]^{V_{H}}$ computed
during the intra-cluster rounding step we have
$\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra})\geq\mathbf{u}(\vec{x}^{intra})/3$.

###### Proof.

We have

$\displaystyle\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra})$
$\displaystyle=$ $\displaystyle\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\bigg{(}\sum_{u\in
IN^{*}(v)}x^{intra}_{u}-\sum_{u,u^{\prime}\in IN^{*}(v)}x^{intra}_{u}\cdot
x^{intra}_{u^{\prime}}-\sum_{u\in IN^{*}(v)}\sum_{w\in
OUT(u)}x^{intra}_{u}\cdot x^{intra}_{w}\bigg{)}$ $\displaystyle=$
$\displaystyle\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\bigg{(}\sum_{u\in
IN^{*}(v)}x^{intra}_{u}\cdot\big{(}1-\sum_{u^{\prime}\in
IN^{*}(v)}x^{intra}_{u^{\prime}}-\sum_{w\in
OUT(u)}x^{intra}_{w}\big{)}\bigg{)}$ $\displaystyle\geq$
$\displaystyle\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot\bigg{(}\sum_{u\in
IN^{*}(v)}x^{intra}_{u}\big{(}1-1/3-1/3\big{)}\bigg{)}$ $\displaystyle\geq$
$\displaystyle\sum_{\textit{good vertex \,}v}(\deg(v)/2)\cdot\big{(}\sum_{u\in
IN^{*}(v)}x^{intra}_{u}/3\big{)}=\mathbf{u}(\vec{x})/3,$

where we used Claim 5.6. ∎

Hence, we can apply Lemma 3.3 on these fractional assignments with
$\lambda_{min}=\frac{1}{100f(n)\log(n)}=1/2^{\widetilde{O}(\sqrt{\log n})}$.
The algorithm runs in
$O(\log^{2}(1/\lambda_{min})+\log(1/\lambda_{min})\log^{*}n)=\widetilde{O}(\log
n)$ rounds in $H^{2}$, and hence can be simulated with no asymptotic overhead
in $H$, and as a result we get an integral label assignment
$\vec{y}\in\\{0,1\\}^{V_{H}}$ which satisfies
$\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})\geq
0.5(\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra}))$. We know that
$Z(\vec{y})=\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})\geq(1/2)\cdot(\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra})).$
Next, we argue that this implies $Z(\vec{y})\geq|E_{H}|/24000$.

######  Claim 5.8.

For the fractional label assignment $\vec{x}^{intra}\in[0,1]^{V_{H}}$ computed
during the intra-cluster rounding step we have
$Z(\vec{x}^{intra})=\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra})\geq|E_{H}|/12000$.
Hence, for the integral marking assignment $\vec{y}$ we obtain from rounding
$\vec{x}$ by invoking Lemma 3.3, we have
$Z(\vec{y})=\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})\geq(1/2)\cdot(\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x}))\geq|E_{H}|/24000$.

###### Proof.

From Claim 5.7, we have
$Z(\vec{x}^{intra})=\mathbf{u}(\vec{x}^{intra})-\mathbf{c}(\vec{x}^{intra})\geq\mathbf{u}(\vec{x}^{intra})/3$.
Hence,

$\displaystyle Z(\vec{x}^{intra})\geq\mathbf{u}(\vec{x}^{intra})/3$
$\displaystyle=\sum_{\textit{good vertex \,}v}(\deg(v)/2)\bigg{(}\sum_{u\in
IN^{*}(v)}x^{intra}_{u}/3\bigg{)}$ $\displaystyle\geq\sum_{\textit{good vertex
\,}v}(\deg(v)/2)\cdot(1/3000)\geq|E_{H}|/12000,$

where we first used Claim 5.6 that says that $\sum_{u\in
IN^{*}(v)}x^{intra}_{u}\geq 1/1000$ and then we used Eq. 3 that bounds
$\sum_{\textit{good vertex \,}v}\deg(v)\geq|E_{H}|/2$.

Since
$Z(\vec{y})=\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})\geq(1/2)\cdot(\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x}))$,
the claim follows. ∎

#### Putting Everything Together

From the rounding procedure described above, which runs in $\widetilde{O}(\log
n)$ rounds of the $\mathsf{LOCAL}$ model, we get an integral marking
assignment $\vec{y}$ with the following guarantee: if we add marked nodes $u$
that have no marked out-neighbor to the independent set and remove them along
with their neighbors, we remove at least a $1/24000$ fraction of the remaining
edges. Hence, $O(\log n)$ such iterations suffice to complete the computation
and have a maximal independent set, for a total round complexity of
$\widetilde{O}(\log^{2}n)$. Note that the low-diameter partition only has to
be computed once in the beginning, which takes $\widetilde{O}(\log^{2}n)$
rounds. Thus, we can indeed compute an MIS in $\widetilde{O}(\log^{2}n)$
rounds of the $\mathsf{LOCAL}$ model.

## References

  * [ABCP96] Barcuh Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg.  Fast network decompositions and covers.  J. of Parallel and Distributed Computing, 39(2):105–114, 1996\.
  * [ABI86] Noga Alon, Lazlo Babai, and Alon Itai.  A fast and simple randomized parallel algorithm for the maximal independent set problem.  Journal of Algorithms, 7(4):567–583, 1986.
  * [AGLP89] B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin.  Network decomposition and locality in distributed computation.  In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS), pages 364–369, 1989.
  * [Awe85] Baruch Awerbuch.  Complexity of network synchronization.  Journal of the ACM, 32(4):804–823, 1985.
  * [Bar12] Leonid Barenboim.  On the locality of some NP-complete problems.  In Proc. 39th Coll. on Automata, Languages, and Programming (ICALP), pages 403–415, 2012.
  * [BBH+19] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela.  Lower bounds for maximal matchings and maximal independent sets.  In Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2019.
  * [BKM20] Philipp Bamberger, Fabian Kuhn, and Yannic Maus.  Efficient deterministic distributed coloring with small bandwidth.  In ACM Symp. on Principles of Distributed Computing (PODC), pages 243–252, 2020.
  * [CG21] Yi-Jun Chang and Mohsen Ghaffari.  Strong-diameter network decomposition.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 273–281, 2021.
  * [CHPS20] Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman.  Derandomizing local distributed algorithms under bandwidth restrictions.  Distributed Comput., 33(3-4):349–366, 2020.
  * [CLP18] Yi-Jun Chang, Wenzheng Li, and Seth Pettie.  An optimal distributed $(\Delta+1)$-coloring algorithm?  In ACM Symp. on Theory of Computing (STOC), 2018.
  * [EHRG22] Michael Elkin, Bernhard Haeupler, Václav Rozhoň, and Christoph Grunau.  Deterministic low-diameter decompositions for weighted graphs and distributed and parallel applications.  In IEEE Symposium on Foundations of Computer Science (FOCS), pages to appear, arXiv:2204.08254, 2022.
  * [EN16] Michael Elkin and Ofer Neiman.  Distributed strong diameter network decomposition.  In ACM Symp. on Principles of Distributed Computing (PODC), pages 211–216, 2016.
  * [FGG+23] Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and Václav Rozhoň.  Local distributed rounding: Generalized to MIS, matching, set cover, and beyond.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages to appear, arXiv:2209.11651, 2023.
  * [FGK17] Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn.  Deterministic distributed edge-coloring via hypergraph maximal matching.  In IEEE Symp. on Foundations of Computer Science (FOCS), 2017.
  * [Fis20] Manuela Fischer.  Improved deterministic distributed matching via rounding.  Distributed Computing, 33(3):279–291, 2020.
  * [FMU22] Manuela Fischer, Slobodan Mitrović, and Jara Uitto.  Deterministic (1+ $\epsilon$)-approximate maximum matching with poly(1/$\epsilon$) passes in the semi-streaming model and beyond.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 248–260, 2022.
  * [GGH+23] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň.  Improved distributed network decomposition, hitting sets, and spanners, via derandomization.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages to appear, arXiv:2209.11669, 2023.
  * [GGR21] Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon.  Improved deterministic network decomposition.  In ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 2904–2923, 2021.
  * [GHK18] Mohsen Ghaffari, David Harris, and Fabian Kuhn.  On derandomizing local distributed algorithms.  In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 662–673, 2018.
  * [GK21] Mohsen Ghaffari and Fabian Kuhn.  Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition.  In Proc. 62nd IEEE Symp. on Foundations of Computer Science (FOCS), pages 1009–1020, 2021.
  * [GKM17] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus.  On the complexity of local distributed graph problems.  In Proc. 49th ACM Symp. on Theory of Computing (STOC), pages 784–797, 2017.
  * [Har19] David G. Harris.  Distributed local approximation algorithms for maximum matching in graphs and hypergraphs.  In Proc. 60th IEEE Symp. on Foundations of Computer Science (FOCS), pages 700–724, 2019.
  * [HKP01] Michal Hańćkowiak, Michal Karoński, and Alessandro Panconesi.  On the distributed complexity of computing maximal matchings.  SIAM Journal on Discrete Math., 15(1):41–57, 2001.
  * [Lin87] Nati Linial.  Distributive graph algorithms – global solutions from local data.  In Proc. 28th IEEE Symp. on Foundations of Computer Science (FOCS), pages 331–335, 1987.
  * [Lin92] Nati Linial.  Locality in distributed graph algorithms.  SIAM Journal on Computing, 21(1):193–201, 1992.
  * [LS93] Nati Linial and Michael Saks.  Low diameter graph decompositions.  Combinatorica, 13(4):441–454, 1993.
  * [Lub86] Michael Luby.  A simple parallel algorithm for the maximal independent set problem.  SIAM Journal on Computing, 15:1036–1053, 1986.
  * [Lub93] Michael Luby.  Removing randomness in parallel computation without a processor penalty.  J. of Computer and System Sciences, 47(2):250–286, 1993.
  * [MPX13] Gary L Miller, Richard Peng, and Shen Chen Xu.  Parallel graph decompositions using random shifts.  In ACM symposium on Parallelism in algorithms and architectures (SPAA), pages 196–203, 2013.
  * [Pel00] David Peleg.  Distributed Computing: A Locality-Sensitive Approach.  SIAM, 2000.
  * [PS92] Alessandro Panconesi and Aravind Srinivasan.  Improved distributed algorithms for coloring and network decomposition problems.  In Proc. 24th ACM Symp. on Theory of Computing (STOC), pages 581–592, 1992.
  * [RG20] Vaclav Rozhoň and Mohsen Ghaffari.  Polylogarithmic-time deterministic network decomposition and distributed derandomization.  In Proc. 52nd ACM Symp. on Theory of Computing (STOC), pages 350–363, 2020.

##  Appendix A The deterministic hitting set algorithm of Lemma 3.4

In this section, we present the proof of Lemma 3.4. This is the deterministic
hitting set subroutine used in our clustering results. For that, in Section
A.1, we first develop a more basic variant of the hitting set result. Then, in
Section A.2, we explain how to go from this to Lemma 3.4.

###  A.1 A basic hitting set algorithm

######  Lemma A.1.

There is a deterministic distributed algorithm in the $\mathsf{LOCAL}$ model
that, for every $\Delta\in\mathbb{N}$, $b\in\mathbb{N}$, $p=\Omega(1/\Delta)$
and $Norm\geq 0$, it provides the following guarantees: The input is a
bipartite graph $H=(U_{H}\sqcup V_{H},E_{H})$ with $\deg_{H}(u)=\Delta$ for
every $u\in U_{H}$. Initially, each node in $H$ is equipped with a unique
$b$-bit identifier and each node $u\in U_{H}$ is assigned a weight $w_{u}\geq
0$. Each node also knows at the beginning to which side of the bipartition it
belongs. The algorithm computes a subset $V^{sub}\subseteq V_{H}$ satisfying

$\sum_{u\in U_{H}\colon N_{H}(u)\cap
V^{sub}=\emptyset}w_{u}+Norm\cdot|V^{sub}|\leq e^{-p\Delta}\sum_{u\in
U_{H}}w_{u}+Norm\cdot 4p\cdot|V_{H}|.$

The algorithm runs in $O(\Delta p(\log^{2}(\Delta)+\log(\Delta)\log^{*}b))$
rounds.

The rest of this subsection is dedicated to proving Section A.1.

The algorithm runs in $T:=\lceil 10p\Delta\rceil$ steps. For $i\in[1,T]$, the
algorithm computes a set $S_{i}\subseteq V_{H}$. For $i\in[0,T]$, we define
$W_{i}=\cup_{j\in[1,i]}S_{j}$ and $U^{unhit}_{i}=\\{u\in U_{H}\colon
N_{H}(u)\cap W_{i}=\emptyset\\}$. In the end, the algorithm outputs
$V^{sub}:=W_{T}$. For $i\in[0,T]$, we define

$\Phi_{i}=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i}}w_{u}+Norm\cdot|W_{i}|+\frac{T-i}{T}Norm\cdot 4p\cdot|V_{H}|.$

Note that

$\Phi_{0}=e^{-p\Delta}\sum_{u\in U^{unhit}_{0}}w_{u}+Norm\cdot
4p\cdot|V_{H}|=e^{-p\Delta}\sum_{u\in U_{H}}w_{u}+Norm\cdot 4p\cdot|V_{H}|$

and

$\Phi_{T}=\sum_{u\in U^{unhit}_{T}}w_{u}+Norm\cdot|W_{T}|=\sum_{u\in
U_{H}\colon N_{H}(u)\cap V^{sub}=\emptyset}w_{u}+Norm\cdot|V^{sub}|.$

Therefore, it suffices to ensure that $\Phi_{T}\leq\Phi_{0}$. In fact, the
algorithm computes each $S_{i}$ in a way that ensures $\Phi_{i}\leq\Phi_{i-1}$
for every $i\in[1,T]$. We first introduce the notion of a good set $S_{i}$. On
one hand, a good set $S_{i}$ indeed ensure that $\Phi_{i}\leq\Phi_{i-1}$. On
the other hand, it is defined in such a way that one can apply the local
rounding framework of Faour et al. [FGG+23] in a straightforward manner to
efficiently compute a good set.

######  Definition A.1 (Good Set $S_{i}$ in Step $i$).

Let $i\in[1,T]$ be arbitrary. For a set $S_{i}\subseteq V_{H}$ and $u\in
U_{H}$, let

$Y_{i}(u)=1-|N_{H}(u)\cap S_{i}|+\binom{|N_{H}(u)\cap S_{i}|}{2}.$

We refer to $S_{i}$ as good in step $i$ if

$e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}Y_{i}(u)w_{u}+Norm\cdot|S_{i}|\leq
e^{-\frac{T-(i-1)}{T}p\Delta}\sum_{u\in U^{unhit}_{i-1}}w_{u}+\frac{Norm\cdot
4p}{T}\cdot|V_{H}|.$

Note that $Y_{i}(u)\geq I(N_{H}(u)\cap S_{i}=\emptyset)$. Recall that for an
event $\mathcal{E}$, we define the indicator variable $I(\mathcal{E})$ to be
equal to $1$ if $\mathcal{E}$ happens and $0$ otherwise.

######  Claim A.2.

For $i\in[1,T]$, if $S_{i}$ is a good set in step $i$, then
$\Phi_{i}\leq\Phi_{i-1}$.

###### Proof.

We have

$\displaystyle\Phi_{i}$ $\displaystyle=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i}}w_{u}+Norm\cdot|W_{i}|+\frac{T-i}{T}Norm\cdot 4p\cdot|V_{H}|$
$\displaystyle\leq e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}Y_{i}(u)w_{u}+Norm\cdot|S_{i}|+Norm\cdot|W_{i-1}|+\frac{T-i}{T}Norm\cdot
4p\cdot|V_{H}|$ $\displaystyle\leq e^{-\frac{T-(i-1)}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}+\frac{Norm\cdot
p}{T}\cdot|V_{H}|+Norm\cdot|W_{i-1}|+\frac{T-i}{T}Norm\cdot 4p\cdot|V_{H}|$
$\displaystyle=\Phi_{i-1},$

as needed. ∎

######  Lemma A.3.

For a fixed $i\in[1,T]$, we can compute a good set $S_{i}$ in step $i$ in
$O(\log^{2}\Delta+\log(\Delta)\log^{*}b)$ rounds.

###### Proof.

We make use of the local rounding framework of Faour et al. [FGG+23] as
outlined in Section 3.2 to compute a good set $S_{i}$. To help readability,
let us recall the related definition and restate their main rounding lemma.

See 3.1

See 3.3

#### Our Local Derandomization.

The labeling space is whether each node in $V_{H}$ is contained in $S_{i}$ or
not, i.e., each node in $V_{H}$ takes simply one of two possible labels
$\Sigma=\\{0,1\\}$ where $1$ indicates that the node is in $S_{i}$. For a
given label assignment $\vec{x}\in\\{0,1\\}^{V_{H}}$, we define the utility
function

$\mathbf{u}(\vec{x})=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}\sum_{v\in N_{H}(u)}x_{v}+\frac{Norm\cdot
4p}{T}\cdot|V_{H}|,$

and the cost

$\mathbf{c}(\vec{x})=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}\sum_{v\neq v^{\prime}\in
N_{H}(u)}x_{v}x_{v^{\prime}}+Norm\cdot\sum_{v\in V_{H}}x_{v}.$

If the label assignment is relaxed to be a fractional assignment
$\vec{x}\in[0,1]^{V_{H}}$, where intuitively now $x_{v}$ is the probability of
$v$ being contained in $S_{i}$, the same definitions apply for the utility and
cost of this fractional assignment.

Let $G=(V_{G},E_{G})$ be the graph with $V_{G}=V_{H}$ and where any two
vertices $v\neq v^{\prime}\in V_{H}$ are connected by an edge if $v$ and
$v^{\prime}$ have a common neighbor in $U_{H}$.

Note that $\mathbf{u}(\vec{x})$ is a utility function in the graph $G$ and
similarly $\mathbf{c}(\vec{x})$ is a cost function in the graph $G$.

We next argue that the fractional assignment where $x_{v}=\frac{2p}{T}$ for
each $v\in V_{H}$ satisfies the conditions of Lemma 3.3. For the given
fractional assignment, utility minus cost is at least a constant factor of
utility.

######  Claim A.4.

Let $\vec{x}\in[0,1]^{V_{H}}$ with $x_{v}=\frac{2p}{T}$ for every $v\in
V_{H}$. Then,
$\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x})\geq\mathbf{u}(\vec{x})/2$.

###### Proof.

Note that for every $u\in U_{H}$, we have

$\sum_{v\in N_{H}(u)}x_{v}=\Delta\cdot\frac{2p}{T}\leq 0.2.$

Therefore,

$\displaystyle\mathbf{u}(\vec{x})$
$\displaystyle=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}\sum_{v\in N_{H}(u)}x_{v}+\frac{Norm\cdot
4p}{T}\cdot|V_{H}|$ $\displaystyle\geq
2\left(e^{-\frac{T-i}{T}p\Delta}\sum_{u\in U^{unhit}_{i-1}}w_{u}\sum_{v\neq
v^{\prime}\in N_{H}(u)}x_{v}x_{v^{\prime}}+Norm\cdot\sum_{v\in
V_{H}}x_{v}\right)$ $\displaystyle\geq 2\mathbf{c}(\vec{x})$

and thus indeed
$\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x})\geq\mathbf{u}(\vec{x})/2$. ∎

Hence, we can apply Lemma 3.3 on these fractional assignments with
$\lambda_{min}=\frac{2p}{T}=\Omega(1/\Delta)$. The algorithm runs in
$O(\log^{2}\Delta+\log(\Delta)\log^{*}b)$ rounds and as a result we get an
integral label assignment $\vec{y}\in\\{0,1\\}^{V_{H}}$ which satisfies
$\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})\geq
0.9(\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x}))$. We can then conclude

$\displaystyle\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})$ $\displaystyle\geq
0.9(\mathbf{u}(\vec{x})-\mathbf{c}(\vec{x}))$ $\displaystyle\geq
0.9\left(e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}\left(\Delta\cdot\frac{2p}{T}-\binom{\Delta}{2}\left(\frac{2p}{T}\right)^{2}\right)+\frac{Norm\cdot
4p}{T}\cdot|V_{H}|-\frac{Norm\cdot 2p}{T}|V_{H}|\right)$ $\displaystyle\geq
e^{-\frac{T-i}{T}p\Delta}\sum_{u\in U^{unhit}_{i-1}}w_{u}\frac{\Delta\cdot
p}{T}.$

This integral label assignment directly gives us $S_{i}$. In particular, let
$S_{i}=\\{v\in V_{H}\colon y_{v}=1\\}$. Note that

$\displaystyle\mathbf{u}(\vec{y})-\mathbf{c}(\vec{y})=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}\left(|N_{H}(u)\cap S_{i,j}|-\binom{|N_{H}(u)\cap
S_{i,j}|}{2}\right)w_{u}+\frac{Norm\cdot 4p}{T}|V_{H}|-Norm|S_{i}|$

and therefore

$\displaystyle e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}Y_{i}(u)w_{u}+Norm\cdot|S_{i}|$
$\displaystyle=e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}-\mathbf{u}(\vec{y})+\mathbf{c}(\vec{y})+\frac{Norm\cdot
4p}{T}|V_{H}|$ $\displaystyle\leq e^{-\frac{T-i}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}\left(1-\frac{\Delta\cdot p}{T}\right)w_{u}+\frac{Norm\cdot
4p}{T}|V_{H}|$ $\displaystyle\leq e^{-\frac{T-(i-1)}{T}p\Delta}\sum_{u\in
U^{unhit}_{i-1}}w_{u}+\frac{Norm\cdot 4p}{T}|V_{H}|$

which shows that $S_{i}$ is indeed a good set in step $i$ according to
Definition A.1. ∎

###  A.2 The hitting set algorithm of Lemma 3.4

We are now ready to prove Lemma 3.4. To help readability, we first restate the
lemma. See 3.4

###### Proof of Lemma 3.4.

Let $H^{\prime}=(U_{H^{\prime}}\sqcup V_{H^{\prime}},E_{H^{\prime}})$ be the
bipartite graph we obtain from $H$ by replacing each vertex $u\in U_{H}$ with
$\lfloor\frac{\Delta}{k}\rfloor$ copies of it and connecting each copy of $u$
to $k$ neighbors of $u$ in $H$ in such a way that no two copies are connected
to the same neighbor. Note that given the unique $b$-bit identifiers in $H$,
it is easy to assign unique $(2+\lceil\log_{2}(\Delta)\rceil)=O(b)$-bit
identifiers to nodes in $H^{\prime}$.

According to Lemma A.1, there exists a $\mathsf{LOCAL}$ algorithm, running in
$O(kp(\log^{2}(k)+\log(k)\log^{*}b))$ rounds, which computes a set
$V^{sub}\subseteq V_{H^{\prime}}=V_{H}$ satisfying

$\displaystyle\sum_{u^{\prime}\in U_{H^{\prime}}\colon
N_{H^{\prime}}(u^{\prime})\cap
V^{sub}=\emptyset}\frac{2w_{u^{\prime}}}{\lfloor\Delta/k\rfloor}+Norm\cdot|V^{sub}|$
$\displaystyle\leq e^{-pk}\sum_{u^{\prime}\in
U_{H^{\prime}}}\frac{2w_{u^{\prime}}}{\lfloor\Delta/k\rfloor}+Norm\cdot
4p\cdot|V_{H}|$ $\displaystyle\leq 4\left(e^{-pk}\sum_{u\in
U_{H}}w_{u}+Norm\cdot p\cdot|V_{H}|\right),$

where for each copy $u^{\prime}$ of $u$, we set $w_{u^{\prime}}:=w_{u}$.

For every node $u\in U_{H}$ with $|N_{H}(u)\cap V^{sub}|\leq
0.5\lfloor\Delta/k\rfloor$, there exist at least $0.5\lfloor\Delta/k\rfloor$
copies $u^{\prime}$ of $u$ with $N_{H^{\prime}}(u^{\prime})\cap
V^{sub}=\emptyset$. Therefore,

$\sum_{u\in U_{H}\colon|N_{H}(u)\cap V^{sub}|\leq
0.5\lfloor\Delta/k\rfloor}w_{u}\leq\sum_{u^{\prime}\in U_{H^{\prime}}\colon
N_{H^{\prime}}(u^{\prime})\cap
V^{sub}=\emptyset}\frac{2w_{u^{\prime}}}{\lfloor\Delta/k\rfloor},$

which together with the previous calculation shows that $V^{sub}$ fulfills the
condition of Lemma 3.4. ∎