Adapting Local Sequential Algorithms to the Distributed Setting
Ken-Ichi Kawarabayashi∗

Gregory Schwartzman∗

arXiv:1711.10155v2 [cs.DC] 19 Feb 2018

Abstract
It is a well known fact that sequential algorithms which exhibit a strong ”local” nature can
be adapted to the distributed setting given a legal graph coloring. The running time of the
distributed algorithm will then be at least the number of colors. Surprisingly, this well known
idea was never formally stated as a unified framework. In this paper we aim to define a robust
family of local sequential algorithms which can be easily adapted to the distributed setting. We
then develop new tools to further enhance these algorithms, achieving state of the art results
for fundamental problems.
We define a simple class of greedy-like algorithms which we call orderless-local algorithms.
We show that given a legal c-coloring of the graph, every algorithm in this family can be
converted into a distributed algorithm running in O(c) communication rounds in the CONGEST
model. We show that this family is indeed robust as both the method of conditional expectations
and the unconstrained submodular maximization algorithm of Buchbinder et al. [BFNS15] can
be expressed as orderless-local algorithms for local utility functions — Utility functions which
have a strong local nature to them.
We use the above algorithms as a base for new distributed approximation algorithms for
the weighted variants of some fundamental problems: Max k-Cut, Max-DiCut, Max 2-SAT and
correlation clustering. We develop algorithms which have the same approximation guarantees
as their sequential counterparts, up to a constant additive ǫ factor, while achieving an O(log ∗ n)
running time for deterministic algorithms and O(ǫ−1 ) running time for randomized ones. This
improves exponentially upon the currently best known algorithms.

National Institute of Informatics, Tokyo, Japan. {k keniti, greg}@nii.ac.jp
This work was supported by JST ERATO Grant Number JPMJER1201, Japan.
∗

1
1.1

Introduction
Definitions and motivation

A large part of research in the distributed environment aims to develop fast distributed algorithms
for problems which have already been studied in the sequential setting. Ideally, we would like to use
the power of the distributed environment to achieve a substantial improvement in the running time
over the sequential algorithm, and indeed, for many problems distributed algorithms achieve an exponential improvement over the sequential case. One approach to designing distributed algorithms
is using the sequential algorithm as natural staring point [CLS17, BCS17, BCGS17, GHS83, BS07],
then certain adjustments are made for the distributed environment in order to achieve a faster
running time.
In this paper we focus our attention on approximation algorithms for unconstrained optimization
problems on graphs. We are given some graph G(V, E), where each vertex v is assigned a variable Xv
taking values in some set A. We aim to maximize some utility function f over these variables (For
a formal definition see Section 2). Our distributed model is the CONGEST model of distributed
computation, where the network is represented by a graph, s.t nodes are computational units and
edges are communication links. Nodes communicate in synchronous communication rounds, where
at each round a node sends and receives messages from all of its neighbors. In the CONGEST
model the size of messages sent between nodes is limited to O(log n) bits. This is more restrictive
than the LOCAL model, where message size is unbounded. Our complexity measure is the number
of communication rounds of the algorithm.
Adapting a sequential algorithm of the type we describe above to the distributed setting, means
we wish each node v in the communication graph to output an assignment to Xv such that the
approximation guarantee is close to that of the sequential algorithm, while minimizing the number
of communication rounds of the distributed algorithm. Our goal is to formally define a family of
sequential algorithms which can be easily converted to distributed algorithms, and then develop
tools to allow these algorithms to run exponentially faster, while achieving almost the same approximation ratio up. To achieve this we focus our attention on a family of sequential algorithms
which exhibit a very strong local nature.
Finally, we apply our techniques to the weighted variants of the classical problems of Max k-Cut,
Max-DiCut, Max 2-SAT and correlation clustering, achieving an exponential improvement over the
current state of the art distributed algorithms [CLS17], while losing only an additive ǫ-factor in the
approximation ratio.

1.2

Tools and results

We define a family of utility functions, which we call local utility functions (Formally defined in
Section 2). We say that a utility function f is a local utility function, if the change to the value of
the function upon setting one variable Xv can be computed locally. Intuitively, while optimizing a
general utility function in the distributed setting might be difficult for global functions, the local
nature of the family of local utility functions makes it a perfect candidate.
We focus on adapting a large family of, potentially randomized, local algorithms to the distributed setting. We consider orderless-local algorithms - algorithms that can traverse the variables
in any order and in each iteration apply some local function to decide the value of the variable. By
local we mean that the decision only depends on the local environment of the node in the graph,
the variables of nodes adjacent to that variable and some randomness only used by that node. This

1

is similar to the family of Priority algorithms first defined in [BNR02]. The goal of [BNR02] was to
formally define the notion of a greedy algorithm, and then to explore the limits of these algorithms.
Our definition is similar (and can be expressed as a special case of priority algorithms), but the
goal is different. While [BNR02] aims to prove lower bounds, we provide some sufficient conditions
that allow us to easily transform local sequential algorithms into fast distributed algorithms.
Our definitions are also similar to the S-LOCAL model [GKM17], which also shows that sequential algorithms which traverse the graph vertices in any order and make local decisions can be
adapted to the distributed LOCAL model in poly logarithmic rounds using randomization. While
the results of [GKM17] are much more broad, our transformation does not require any randomization and works in the CONGEST model. Finally, we should also mention the field of local
computation algorithms [RTVX11] whose aim is developing efficient local sequential algorithms.
We refer the reader to an excellent survey by Levi and Medina [LM17].
One might expect that due to the locality of this family of algorithms it can be distributed if
the graph is provided with a legal coloring. The distributed algorithm goes over the color classes
one after another and executes all nodes in the color class simultaneously. This solves any conflicts
that may occur form executing two neighboring nodes, while the orderless property guarantees that
this execution is valid. In a sense this argument was already used for specific algorithm (Coloring
to MIS [Lin92], MaxIS of [BCGS17], Max-Cut of [CLS17]). We provide a more general result,
using this classical argument. Specifically, we show that given a legal c-coloring, any orderless-local
algorithm can be distributed in O(c)-communication rounds in the CONGEST model.
To show that this definition is indeed robust, we show two general applications. The first is
adapting the method of conditional expectations (Formally defined in Section 2) to the distributed
setting. This method is inherently sequential, but we show that if the utility function optimized is
a local utility function, then the algorithm is an orderless-local algorithm. A classical application
of this technique is for Max k-cut, where an (1 − 1/k)-approximation is achieved when every
node chooses a cut side at random. This can be derandomized using the method of conditional
expectations, and adapted to the distributed setting, as the cut function is a local utility function.
We note that the same exact approach results in a (1/2−ǫ)-approximation for max-agree correlation
clustering on general graphs (see Section 2 for a definition). Because the tools used for Max-Cut
directly translate to correlation clustering, we focus on Max-Cut for the rest of the paper, and only
mention correlation clustering at the very end.
The second application is the unconstrained submodular maximization algorithms of [BFNS15],
where a deterministic 1/3-approximation and a randomized expected 1/2-approximation algorithms
are presented. We show that both are orderless-local algorithms when provided with a local utility
function. This can be applied to the problem of Max-DiCut, as it is an unconstrained submodular
function, and also a local utility function. The algorithms of [BFNS15] were already adapted to the
distributed setting for the specific problem of Max-DiCut by [CLS17] using similar ideas. The main
benefit of our definition is the convenience and generality of adapting these algorithms without the
need to consider their analysis or reprove correctness. We conclude that the family of orderless-local
algorithms indeed contains robust algorithms for fundamental problems, and especially the method
of conditional expectations, which has no analogue in the distributed environment to the best of
our knowledge.
Next, we wish to consider the running time of these algorithms. Recall that we expressed the
running time of orderless local algorithms in terms of the colors of some legal coloring for the graph.
For a general graph, we cannot hope for a legal coloring using less than ∆ + 1, where ∆ is the
maximum degree in the graph. This means that using the distributed version of an orderless-local

2

algorithm as is will have a running time linear in ∆. We show how to overcome this obstacle for
Max k-Cut and Max-DiCut. The general idea is to compute a defective coloring of the graph which
uses few colors, drop all monochromatic edges, and call the algorithm for the new graph which now
has a legal coloring.
A key tool in our algorithms is a new type of defective coloring we call a weighted ǫ-defective
coloring. The classical defective coloring allows each vertex to have at most d monochromatic edges,
for some defect parameter d. We consider positively edge weighted graphs and require a weighted
fractional defect - for every vertex the total weight of monochromatic edges is at most an ǫ-fraction
of the total weight of all edges. We show that a weighted ǫ-defective coloring using O(ǫ−2 ) colors can
be computed deterministically in O(log∗ n) rounds using the defective coloring algorithm of [Kuh09].
The classical algorithm of Kuhn was found useful in the adaptation of sequential algorithms to the
distributed setting [FGK17, GKM17], thus its effectiveness for weighted ǫ-defective coloring might
be of further use.
Although we cannot guarantee a legal coloring with a small number of colors for any graph
G(V, E, w), we may remove some subset of E which will result in a new graph G′ with a low
chromatic number. We wish to do so while not decreasing the total sum of edge weights in G′ ,
which we prove guarantees the approximation will only be mildly affected for our cut problems.
Formally, we show that if we only decrease the total edge weight by an ǫ-fraction, we will incur an
additive ǫ-loss in the approximation ratio of the cut algorithms for G. For the randomized algorithm
this is easy, simply color each vertex randomly with a color in [⌈ǫ−1 ⌉] and drop all monochromatic
edges. For the deterministic case, we execute our weighted ǫ-defective coloring algorithm, and then
remove all monochromatic edges. We then execute the relevant cut algorithm on the resulting
graph G′ which now has a legal coloring, using a small number of colors. The above results in
extremely fast approximation algorithms for weighted Max k-Cut and weighted Max-DiCut, while
having almost the same approximation ratio as their sequential counterpart.
Finally, our techniques can also be applied to the problem of weighted Max 2-SAT. To do so
we may use the randomized expected 3/4-approximation algorithm presented in [PSWvZ17]. It is
based on the algorithm of [BFNS15], and thus is almost identical to the unconstrained submodular
maximization algorithm. Because the techniques we use are very similar to the above, we defer the
entire proof to the appendix (Section C). We state our results in Table 1.
Problem
Weighted
Weighted
Weighted
Weighted
Weighted

Our Approx. Our Time Prev Approx.
Correlation-Clustering*
Max k-Cut
Max-Dicut
Max-Dicut
Max 2-SAT

Prev Time

Notes

∗

1/2 − ǫ
1 − 1/k − ǫ
1/3 − ǫ
1/2 − ǫ
3/4 − ǫ

O(log n)
det.
∗
∗
†
O(log n) 1/2 [CLS17] Õ(∆ + log n)
det.
O(log∗ n) 1/3 [CLS17]† Õ(∆ + log∗ n)
det.
O(ǫ−1 )
1/2 [CLS17]† Õ(∆ + log∗ n) rand.
−1
O(ǫ )
rand.

Table 1: Summary of our results for the CONGEST model (Õ hides factors polylogarithmic in ∆).
(*) General graphs, max-agree (†) Unweighted graphs, only Max-Cut (k = 2).

1.3

Previous research

Cut problems: An excellent overview of the Max-Cut and Max-DiCut problems appears in
[CLS17], which we follow in this section. Computing Max-Cut exactly is NP-hard as shown by Karp
3

[Kar72] for the weighted version, and by [GJS76] for the unweighted case. As for approximations,
it is impossible to improve upon a 16/17-approximation for Max-Cut and a 12/13-approximation
for Max-DiCut unless P = N P [TSSW00, Hås01]. If every node chooses a cut side randomly, an
expected 1/2-approximation for Max-Cut, a 1/4-approximation for Max-DiCut and a (1 − 1/k)approximation is achieved. This can be derandomized using the method of conditional expectations.
In the breakthrough paper of Goemans and Williamson [GW95] a 0.878-approximation is achieved
using semidefinite programming. This is optimal under the unique games conjecture [KKMO07].
In the same paper a 0.796-approximation for Max-DiCut was presented. This was later improved
to 0.863 in [MatuuraM01]. Other results using different techniques are presented in [KS11, Tre12].
In the distributed setting the problem has not received much attention. A node may choose a cut
side at random, achieving the same guarantees as above in constant time. In [HRSS14]
a distributed
√
algorithm for d-regular triangle free graphs which achieves a (1/2 + 0.28125/ d)-approximation
ratio in a single communication round is presented. The only results for general graphs in the
distributed setting is due to [CLS17]. In the CONGEST model they present a deterministic 1/2approximation for Max-Cut, a deterministic 1/3-approximation for Max-DiCut, and a randomized
expected 1/2 approximation for Max-DiCut running in Õ(∆ + log∗ n) communication rounds. The
results for Max-DiCut follow from adapting the unconstrained submodular maximization algorithm
of [BFNS15] to the distributed setting. Better results are presented for the LOCAL model; we refer
the reader to [CLS17] for the full details.
Max 2-SAT: The decision version of Max 2-SAT is NP-complete [GJS76], and there exist several
approximation algorithms [GW95,FG95,LLZ02,MM01], of which currently the best known approximation ratio is 0.9401 [LLZ02]. In [Aus07] it is shown that assuming the unique games conjecture,
the approximation factor of [LLZ02] cannot be improved. Assuming only that P 6= N P it cannot
be approximated to within a 21/22-factor [Hås01]. To the best of our knowledge the problem of
Max 2-SAT (or Max-SAT) was not studied in the distributed model.
Correlation clustering: An excellent overview of correlation clustering (see Section 2 for a definition) appears in [ACG+ 15], which we follow in this section. Correlation clustering was first defined
by [BBC02]. Solving the problem exactly is NP-Hard, thus we are left with designing approximation algorithms for the problem, here one can try to approximate max-agree or min-disagree. If the
graph is a clique, there exists a PTAS for max-agree [BBC02, GG06], and a 2.06-approximation for
max-disagree [CMSY15]. For general (even weighted) graphs there exists a 0.7666-approximation
for max-agree [CGW05,Swa04], and a O(log n)-approximation for min-disagree [DEFI06]. A trivial
1/2-approximation for max-agree on general graphs can be achieved by considering putting every
node in a separate cluster, then considering putting all nodes in a single cluster, and taking the
more profitable of the two.
In the distributed setting little is known about correlation clustering. In [CHK16] a dynamic
distributed MIS algorithm is provided, it is stated that this achieves a 3-approximation for mindisagree correlation clustering as it simulates the classical algorithm of Ailon et al. [ACN08]. We
note that the algorithm of Ailon et al. assumes the graph to be a clique, thus the above result
is limited to complete graphs where the edges of the communication graph are taken to be the
positive edges, and the non-edges are taken as the negative edges (as indeed for general graphs, the
problem is APX-Hard, and difficult to approximate better than Θ(log n) [DEFI06]). We also note
that using only two clusters, where each node chooses a cluster at random, guarantees an expected
1/2-approximation for max-agree on weighted general graphs. We derandomize this approach in
this paper.

4

2

Preliminaries

Sequential algorithms: The main goal of this paper is converting (local) sequential graph algorithms for unconstrained maximization (or minimization) to distributed graph algorithms. Let
us first define formally this family of algorithms. The sequential algorithm receives as input a
graph G = (V, E), we associate each vertex v ∈ V with a variable Xv taking values in some finite
set A. The algorithm outputs a set of assignments X = {Xv = αv }. The goal of the algorithms
is to maximize some utility function f (G, X) taking in a graph and the set of assignments and
outputting some value in R. For simplicity we assume that the order of the variables in X does
not affect f , so we use a set notation instead of a vector notation. We somewhat abuse notation,
and when assigning a variable we write X ∪ {Xv = α}, meaning that any other assignment to Xv
is removed from the set X. We also omit G as a parameter when it is clear from context.
When considering randomized algorithms we assume the algorithm takes in a vector of random
bits denoted by ~r. This way of representing random algorithms is identical to having the algorithm
generate the random coins, and we use these two definitions interchangeably. The randomized
algorithm aims to maximize the expectation of f , where the expectation is taken over the random
bits of the algorithm.
Max k-Cut, Max-DiCut: In this paper we provide fast distributed approximation algorithms
to some fundamental problems, which we now define formally. In the Max k-Cut problem we wish
to divide the vertices into k disjoint sets, such that the weight of edges between different sets is
maximized. In the Max-DiCut problem the edges are directed and we wish to divide the edges into
two disjoint sets, denoted A, B, such that the weight of edges directed from A to B is maximized.
Max 2-SAT: In the Max 2-SAT problem we are given a set of unique weighted clauses over some
set of variables, where each clause contains at most two literals. Our goal is to maximize the weight
of satisfied clauses. This problem is more general than the cut problems, so we must define what
it means in the distributed context. First, the variables will be node variables as defined before.
Second, each node knows all of the clauses it appears in as a literal.
Correlation clustering:
We are given an edge weighted graph G(V, E, w), such that each
edge is also assigned a value from {+, −} (referred to positive and negative edges). Given some
partition, C, of the graph into disjoint clusters, we say that an edge agrees with C if it is positive
and both endpoints are in the same cluster, or it is negative, and its endpoints are in different
clusters. Otherwise we say it disagrees with C. We aim to find a partition C, using any number of
clusters, such that the weight of edges that agree with C (agreements) is maximized (max-agree),
or equivalently the weight of edges that disagree with C is minimized (min-disagree).
The problem is usually expressed as an LP using edge variables, where each variable indicates
whether the nodes are in the same cluster. This allows a solution to use any number of clusters.
In this paper we only aim to achieve a (1/2 − ǫ)-approximation for the problem. This can be done
rather simply without employing the full power of correlation clustering. Specifically, two clusters
are enough for our case as we show that we can deterministically achieve (1/2 − ǫ) |E| agreements
which results in the desired approximation ratio.
Local utility functions: We are interested in a type of utility function which we call a local
utility function. Before we continue with the definition let us define an operator on assignments
X, we define Lv [X] = {Xu = αu } ∈ X | u ∈ N (v) . For convenience, when we pass Lv [X] as
parameter to a function, we assume that the function also receives the local topology of v which we
do not write explicitly. We say that a utility function f , as defined above, is a local utility function
if for every v there exists a function gv s.t f (X ∪ {Xv = α}) − f (X ∪ {Xv = α′ }) = gv (Lv [X], α, α′ ).
5

That is, to compute the change in the utility function which is caused by changing Xv from α′ to
α, we only need to know the local topology of v, and the assignment to neighboring node variables.
We note that for the cut problems considered in this paper the utility functions are indeed local
utility functions. This is proven in the following Lemma (proof deferred to the appendix):
Lemma 1. The utility functions for Max k-Cut, Max-DiCut and max-agree correlation clustering
with 2 clusters are local utility functions.
Submodular functions: A family of functions that will be of interest in this paper is the family
of submodular functions. A function f : 0, 1Ω → R is called set function, with ground set Ω. It
is said to be submodular if for every S, T ⊆ Ω it holds that f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ).
The functions we are interested in have V as their ground set, thus we remain with our original
notation, setting A = {0, 1} and having f take in a set of binary assignments X as a parameter.
The method of conditional expectations:
Next, we consider the method of conditional
n
expectations. Let f : A → R, and let X = (X1 , ..., Xn ) be a vector of random variables taking
values in A. We wish to be consistent with the previous notation, thus we treat X as a set of
assignments. If E[f (X)] ≥ β, then there is an assignment of values Z = {Xi = αi }ni=1 such that
f (Z) ≥ β. We describe how to find
P the vector Z. We first note that from the law of total
expectation it holds that E[f (X)] = α∈A E[f (X) | X1 = α]P r[X1 = α], and therefore for at least
some α ∈ A it holds that E[f (X) | X1 = α] ≥ β. We set this value to be α1 . We then repeat this
process for the rest of the values in X, which results in the set Z. In order for this method to work
we need it to be possible to compute the conditional expectation of f (X).
Graph coloring: A c-coloring for G(V, E) is defined as a function ϕ : V → C. For simplicity we
treat any set C of size c with some ordering as the set of integers [c]. This simplifies things as we
can always consider ϕ(v) ± 1, which is very convenient. We say that a coloring is a legal coloring if
∀v, u s.t (v, u) ∈ E it holds that ϕ(v) 6= ϕ(u). An important tool in this paper is defective coloring.
Let us fix some c-coloring function ϕ : V → [c]. We define the defect of a vertex to be the number of
monochromatic edges it has. Formally, def ect(v) = size{u ∈ N (v) | ϕ(v) = ϕ(u)}. We call ϕ a ccoloring with defect d if it holds that ∀v ∈ V, def ect(v) ≤ d. A classic result by Kuhn [Kuh09] states
that for all d ∈ {1, 2, ..., ∆} an O(∆2 /d2 )-coloring with defect d can be computed deterministically
in O(log∗ n) rounds in the CONGEST model.
In this paper we define a new kind of defective coloring which we call a weighted ǫ-defective
coloring. Given a positively edge weighted graph and any coloring, for every P
vertex we denote by
Em (v) its monochromatic edges. Define its weighted defect as def ectw (v) = e=(u,v)∈Em (v) w(e).
P
We aim to find a coloring s.t the defect for every v is below ǫw(v) = ǫ v∈e w(e). We show that
the algorithm of Kuhn actually computes a weighted ǫ-defective O(ǫ−2 )-coloring. We state the
following theorem (As the analysis is rather similar to the original analysis of Kuhn, the proof is
deferred to Section A in the Appendix):
Theorem 2. For any constant ǫ ∈ (0, 1/e) a weighted ǫ-defective O(ǫ−2 )-coloring can be computed
deterministically in O(log∗ n) rounds in the CONGEST model.

3

Orderless-local algorithms

Next we turn our attention to a large family of (potentially randomized) greedy algorithms. We
limit ourselves to graph algorithms s.t every node v has a variable Xv taking values in some set A.
We aim to maximize some global utility function f (X). We focus on a class of algorithms we call
6

orderless-local algorithms. These are greedy-like algorithms which may traverse the vertices in any
order, and at each step decide upon a value for Xv . This decision is local, meaning that it only
depends on the 1-hop topology of v and the values of neighboring variables. The decision may be
random, but each variable has its own random bits, keeping the decision process local.
The code for a generic algorithm of this family is given in Algorithm 1. The algorithm first
initiates the vertex variables. Next it traverses the variables in some order π : V → [n]. Each
Xvi is assigned a value according to some function decide, which only depends on Lv [X] and some
random bits ~ri which are only used to set the value for that variable. Finally the assignment to
the variables is returned. We are guaranteed that the expected value of f is at least β(G) for any
ordering π of the variables. Formally, E~r [f (OL(G, ~r, π))] ≥ β(G).
Algorithm 1: OL(G, ~r, π)
1
2
3
4

∀v ∈ V, Xv = init(Lv [X])
Order the variables according to π: v1 , v2 ..., vn
for i from 1 to n do Xvi = decide(Lv [X], ri )
Return X

We show that this family of algorithms can be easily distributed using coloring, s.t the running
time of the distributed version depends on the number of colors. The distributed version, OLDist,
is presented as Algorithm 4 in the appendix. The variables are all initiated as in the sequential
version, and then the color classes are executed sequentially, while in each color class the nodes
execute decide simultaneously, and send the newly assigned value to all neighbors. Decide does not
communicate with the neighbors, so the algorithm finishes in O(c) rounds.
It is easy to see that given the same randomness both the sequential and distributed algorithms
output the same result, this is because all decisions of the distributed algorithm only depend on
the 1-hop environment of a vertex, and we are provided with a legal coloring. Thus, one round of
the distributed algorithm is equivalent to many steps of the sequential algorithm. We prove the
following lemma (the proof is deferred to the appendix):
Lemma 3. For any graph G with a legal coloring ϕ, there exists an order π on the variables s.t it
holds that OL(G, ~r, π) = OLDist(G, ~r, π) for any ~r.
Finally we show that for any graph G with a legal coloring ϕ, it holds that E~r [f (OLDist(G, ~r, ϕ))] ≥
β(G). We know from Lemma 3 that for any coloring ϕ there exists an ordering π s.t OL(G, ~r, π) =
OLDist(G, ~r, ϕ) for any ~r. TheP
proof is direct from here: E~r [f (OLDist(G, ~r, ϕ))] =
P
P
r[~
r
]f
(OLDist(G,
~
r
,
ϕ))
=
r ]f (OL(G, ~r, π)) = E~r [f (OL(G, ~r, π))] ≥ β(G).
~
r
~
r P r[~
We conclude that any orderless-local algorithm can be distributed, achieving the same performance guarantee on f , and requiring O(c) communication rounds to finish, given a legal c-coloring.
We state the following theorem:
Theorem 4. Given some utility function f , any sequential orderless-local algorithm for which it
holds that E~r [f (OL(G, ~r, π))] ≥ β(G), can be converted into a distributed algorithm for which it
holds that E~r [f (OLDist(G, ~r, ϕ))] ≥ β(G), where ϕ is a legal c-coloring of the graph. The running
time of the distributed algorithm is O(c) communication rounds.

7

3.1

Distributed derandomization

We consider the method of conditional expectations in the distributed case for some local utility
function f (G, X), as defined in the preliminaries. Assume that the value of every Xv is set independently at random according to some distribution on A which depends only on the local topology of
v. We are guaranteed that ∀G, E[f (G, X)] ≥ β(G). Thus in the sequential setting we may use the
method of conditional expectations to compute a deterministic assignment to the variables with
the same guarantee. We show that because f is a local utility function, the method of conditional
expectations applied on f is an orderless-local algorithm, and thus can be distributed.
Initially all variables are initiated to some value ∅ ∈
/ A, meaning the variable is unassigned.
Let Y = {Xu = αu | u ∈ U ⊆ V } be some partial assignment to the variables. The method of
conditional expectations goes over the variables in any order,
 and in each iteration sets Xvi =
argmaxα E[f (X) | Y, Xvi = α]. This is equivalent to argmaxα E[f (X) | Y, Xvi = α] − E[f (X) | Y ] ,
as the subtracted term is just a constant. With this in mind, we present the pseudo code for the
method of conditional expectations in Algorithm 2.
Algorithm 2: CondExpSeq(G)
1
2
3
4

∀v ∈ V, Xv = ∅
Order the variables according to any order: v1 , v2 ..., vn
for i from 1 to n do Xvi = argmaxα E[f (X) | Y, Xvi = αv ] − E[f (X) | Y ]
Return X

To show that Algorithm 2 is an orderless-local algorithm we only need to show that argmaxα E[f (X) |
Y, Xv = αv ] − E[f (X) | Y ] can be computed locally for any v. We state the following lemma (proof
deferred to the appendix), followed by the main theorem for this section.
Lemma 5. The value argmaxα E[f (X) | Y, Xv = αv ] − E[f (X) | Y ] can be computed locally.
Theorem 6. Let G be any graph and f a local utility function for which it holds that E[f (X)] ≥ β,
where the random assignments to the variables are independent of each other, and depend only on
the local topology of the node. There exists a distributed algorithm achieving the same expected value
for f , running in O(c) communication rounds in the CONGEST model, given a legal c-coloring.

3.2

Submodular Maximization

In this section we consider both the deterministic and randomized algorithms of [BFNS15], achieving
1/3 and 1/2 approximation ratios for unconstrained submodular maximization. We show that both
can be expressed as orderless-local algorithms for any local utility function. As the deterministic and
randomized algorithms of [BFNS15] are almost identical, we focus on the randomized algorithm
achieving a 1/2-approximation in expectation (Algorithm 3), as it is a bit more involved (The
deterministic algorithm appears as Algorithm 5 in the appendix). The algorithms of [BFNS15] are
defined for any submodular function, but as we are interested only in the case where the ground
set is V , we will present it as such.
The algorithm maintains two variable assignment Zi , Yi , initially Z0 = {Xv = 0 | v ∈ V }, Y0 =
{Xv = 1 | v ∈ V }. It iterates over the variables in any order, at each iteration it considers two
nonnegative quantities ai , bi . These quantities represent the gain of either setting Xvi = 1 in Zi−1
or setting Xvi = 0 in Yi−1 . Next a coin is flipped with probability p = ai /(ai + bi ), if ai = bi = 0
8

we set p = 1. If we get heads we set Xvi = 1 in Zi and otherwise we set it to 0 in Yi . When
the algorithm ends it holds that Zn = Yn , and this is our solution. The deterministic algorithm is
almost identical, only that it allows ai , bi to take negative values, and instead of flipping a coin it
makes the decision greedily by comparing ai , bi .
Algorithm 3: rand-usm(f )
1
2
3
4
5
6
7
8
9

Z0 = {Xv = 0 | v ∈ V }, Y0 = {Xv = 1 | v ∈ V }
Order the variables in any order v1 , ..., vn
for i from 1 to n do
ai = max {f (Zi−1 ∪ {Xvi = 1}) − f (Zi−1 ), 0}
bi = max {f (Yi−1 ∪ {Xvi = 0}) − f (Yi−1 ), 0}
if ai + bi = 0 then p = 1 else p = ai /(ai + bi )
Yi = Yi−1 , Zi = Zi−1
Flip a coin with probability p, if heads Zi = Zi ∪ {Xvi = 1}, else Yi = Yi ∪ {Xvi = 0}
return Zn

We first note that the algorithm does not directly fit into our mold, as each vertex has two
variables. We can overcome this, by taking Xv to be a binary tuple, the first coordinate stores its
value for Zi , and the other for Yi . Initially it holds that ∀v ∈ V, Xv = (0, 1), and our final goal
function will only take the first coordinate of the variable. We note that because f is a local utility
function the values ai , bi can be computed locally, this results directly from the definition of a local
utility function, as we are interested in the change in f caused by flipping a single variable. Now we
may rewrite the algorithm as an orderless-local algorithm, the pseudocode appears in the appendix
as Algorithm 6. Using Theorem 4 we state our main result:
Theorem 7. For any graph G and a local unconstrained submodular function f with V as its
ground set, there exists a randomized distributed 1/2-approximation, and a deterministic 1/3approximation algorithms running in O(c) communication rounds in the CONGEST model, given
a legal c-coloring.

3.3

Fast approximations for cut functions

Using the results of the previous sections we can provide fast and simple approximation algorithms
for Max-DiCut and Max k-Cut. Lemma 1 guarantees that the utility functions for these problems
are indeed local utility functions. For Max-DiCut we use the algorithms of Buchbinder et al., as this
is an unconstrained submodular function. For Max k-Cut each node choosing a side uniformly at
random achieves a (1 − 1/k) approximation, thus we use the results of Section 3.1. Theorem 7 and
Theorem 6 immediately guarantee distributed algorithms, running in O(c) communication rounds
given a legal c-coloring.
Denote by Cut(G, ϕ) one of the cut algorithms guaranteed by Theorem 7 or Theorem 6. We
present two algorithms, approxCutDet, a deterministic algorithm to be used when Cut(G, ϕ) is
deterministic (Algorithm 8 in the appendix), and, approxCutRand, a randomized algorithm (Algorithm 9 in the appendix) for the case when Cut(G, ϕ) is randomized. approxCutDet works by
coloring the graph G using a weighted ǫ-defective coloring and then defining a new graph G′ by
dropping all of the monochromatic edges. This means that the coloring is a legal coloring for G′ .

9

Finally we call one of the deterministic cut functions. approxCutRand is identical, apart from the
fact that nodes choose a color uniformly at random from [⌈ǫ−1 ⌉].
For approxCutDet, the running time of the coloring is O(log∗ n) rounds, returning a weighted
ǫ-defective O(ǫ−2 )-coloring. The running time of the cut algorithms is the number of colors, thus
the total running time of the algorithm is O(ǫ−2 + log∗ n) rounds. Using the same reasoning, the
running time of approxCutRand is O(ǫ−1 ). It is only left to prove the approximation ratio. We
prove the following lemma:
Lemma 8. Let G(V, E, w) be any graph, and let G′ (V,PE ′ , w) be a graph resulting from removing
any subset of edges from G of total weight at most ǫ e∈E w(e). Then for any constant p, any
p-approximation for Max-DiCut or Max k-Cut for G′ is a p(1 − 4ǫ)-approximation for G.

Proof.
Let OP T, OP T ′ be the size of optimal solutions for G, G′ . It holds that OP T ′ P
≥ OP T −
P
ǫ e∈E w(e), as any solution for G is also a solution for G′ whose value differs by at most ǫ e∈E w(e)
(the weight of discarded
P edges). Assigning every node a cut side uniformly at random the expected
cut weight is at least e∈E
P w(e)/4 for Max-DiCut and Max k-Cut. Using the probabilistic method
this implies that OP T ≥ e∈E w(e)/4. Using all of the above P
we can say that given a p-approximate
solution for OP T ′ it holds that: p · OP T ′ ≥ p(OP T − ǫ e∈E w(e)) ≥ p(OP T − 4ǫOP T ) =
p(1 − 4ǫ)OP T
Lemma 8 immediately guarantees the approximation ratio for the deterministic algorithm. As
for the randomized algorithm, let the random variable δ be the fraction of edges removed, let p be
the approximation ratio guaranteed by one of the cut algorithms and let ρ be the approximation
ratio achieved by approxCutRand. We know that Eρ [ρ | δ] = p(1 − 4δ). Applying the law of total
expectations we get that E[ρ] = Eδ [Eρ [ρ | δ]] = Eδ [p(1 − 4δ)] = p(1 − 4ǫ). We state our main
theorems for this section.
Theorem 9. There exists a deterministic (1 − 1/k − ǫ)-approximation algorithms for Weighted
Max k-Cut running in O(log∗ n) communication rounds in the CONGEST model.
Theorem 10. There exists a deterministic (1/3 − ǫ)-approximation algorithm for Weighted MaxDiCut running in O(log∗ n) communication rounds in the CONGEST model.
Theorem 11. There exists a randomized distributed expected (1/2−ǫ)-approximation for Weighted
Max-DiCut running in O(ǫ−1 ) communication rounds in the CONGEST model.
Correlation clustering We note the the same techniques used for Max-Cut work directly for
max-agree correlation clustering on general graphs. Specifically, if we divide the nodes into two
clusters, s.t each node selectes a cluster uniformly at random, each edge hasPexactly probability
1/2 to agree with the clustering, thus the expected value of the clustering is e∈E w(e)/2, which
is a 1/2-approximation. The above can be derandomized exactly in the same manner as Max-Cut,
meaning this is an orderless local algorithm. Finally, we apply the weighted ǫ-defective coloring
algorithm twice (note that we ignore the sign of the edge), discard all monochromatic edges and
execute the deterministic algorithm guaranteed from Theorem
6 with a legal coloring. Because there
P
must exists a clustering which has a value at least e∈E w(e)/2, a lemma identical to Lemma 8
can be proved and hence we are done. We state the following theorem:
Theorem 12. There exists a deterministic (1/2 − ǫ)-approximation algorithms for weighted maxagree correlation clustering on general graphs, running in O(log∗ n) communication rounds in the
CONGEST model.
10

Acknowledgments: We would like to thank Ami Paz and Seri Khoury for many fruitful discussions and useful advice.

References
[ACG+ 15]

Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony
Wirth. Correlation clustering in data streams. In ICML, volume 37 of JMLR Workshop
and Conference Proceedings, pages 2237–2246. JMLR.org, 2015.

[ACN08]

Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1–23:27, 2008.

[Aus07]

Per Austrin. Balanced max 2-sat might not be the hardest. In STOC, pages 189–197.
ACM, 2007.

[BBC02]

Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. In FOCS,
page 238. IEEE Computer Society, 2002.

[BCGS17]

Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In PODC, pages 165–174. ACM, 2017.

[BCS17]

Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed
(2 + ǫ)-approximation for vertex cover in o(log ∆ / ǫ log log ∆) rounds. J. ACM,
64(3):23:1–23:11, 2017.

[BFNS15]

Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time
(1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput.,
44(5):1384–1402, 2015.

[BNR02]

Allan Borodin, Morten N. Nielsen, and Charles Rackoff. (incremental) priority algorithms. In SODA, pages 752–761. ACM/SIAM, 2002.

[BS07]

Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms,
30(4):532–563, 2007.

[CGW05]

Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360–383, 2005.

[CHK16]

Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In PODC, pages 217–226. ACM, 2016.

[CLS17]

Keren Censor-Hillel, Rina Levy, and Hadas Shachnai. Fast distributed approximation
for max-cut. 10718:41–56, 2017.

[CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev.
Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In STOC, pages 219–228. ACM, 2015.

11

[DEFI06]

Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation
clustering in general weighted graphs. Theor. Comput. Sci., 361(2-3):172–187, 2006.

[FG95]

Uriel Feige and Michel X. Goemans. Aproximating the value of two prover proof
systems, with applications to MAX 2sat and MAX DICUT. In ISTCS, pages 182–189.
IEEE Computer Society, 1995.

[FGK17]

Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edgecoloring via hypergraph maximal matching. In FOCS, pages 180–191. IEEE Computer
Society, 2017.

[GG06]

Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number
of clusters. Theory of Computing, 2(13):249–266, 2006.

[GHS83]

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm
for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(1):66–77,
1983.

[GJS76]

M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified np-complete
graph problems. Theor. Comput. Sci., 1(3):237–267, 1976.

[GKM17]

Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In STOC, pages 784–797. ACM, 2017.

[GW95]

Michel X. Goemans and David P. Williamson. Improved approximation algorithms for
maximum cut and satisfiability problems using semidefinite programming. J. ACM,
42(6):1115–1145, 1995.

[Hås01]

Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001.

[HRSS14]

Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large cuts with
local algorithms on triangle-free graphs. CoRR, abs/1402.2543, 2014.

[Kar72]

Richard M. Karp. Reducibility among combinatorial problems. In Complexity of
Computer Computations, The IBM Research Symposia Series, pages 85–103. Plenum
Press, New York, 1972.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput.,
37(1):319–357, 2007.
[KS11]

Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut
using random walks. In ICS, pages 367–388. Tsinghua University Press, 2011.

[Kuh09]

Fabian Kuhn. Weak graph colorings: distributed algorithms and applications. In
SPAA, pages 138–144. ACM, 2009.

[Lin92]

Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–
201, 1992.

12

[LLZ02]

Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the
MAX 2-sat and MAX DI-CUT problems. In IPCO, volume 2337 of Lecture Notes in
Computer Science, pages 67–82. Springer, 2002.

[LM17]

Reut Levi and Moti Medina. A (centralized) local guide. Bulletin of EATCS, 2(122),
2017.

[MM01]

Shiro Matuura and Tomomi Matsui. 0.863-approximation algorithm for MAX DICUT.
In RANDOM-APPROX, volume 2129 of Lecture Notes in Computer Science, pages
138–146. Springer, 2001.

[PSWvZ17] Matthias Poloczek, Georg Schnitger, David P. Williamson, and Anke van Zuylen.
Greedy algorithms for the maximum satisfiability problem: Simple algorithms and
inapproximability bounds. SIAM J. Comput., 46(3):1029–1061, 2017.
[RTVX11]

Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In ICS, pages 223–238. Tsinghua University Press, 2011.

[Swa04]

Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite
programming. In SODA, pages 526–527. SIAM, 2004.

[Tre12]

Luca Trevisan. Max cut and the smallest eigenvalue. SIAM J. Comput., 41(6):1769–
1786, 2012.

[TSSW00]

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets,
approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000.

13

A

Extending Kuhn’s algorithm for ǫ-defective coloring

We aim to extend the algorithm of Kuhn [Kuh09] to the case of a weighted ǫ-defective coloring. Given a positively edge weighted graph and any coloring, for every vertex we denote by
Em (v), Eb (v) its
Pmonochromatic and bi-chromatic edges respectively. Define its weighted defect as
def ectw (v) = e=(u,v)∈Em (v) w(e). We aim to find a coloring s.t the defect for every v is below
P
ǫw(v) = ǫ v∈e w(e).
We show that Kuhn’s algorithm can be adapted to this problem.
The algorithm (Algorithm 1) : Given some coloring [M ] of the graph, each iteration of Kuhn’s
algorithm consists of assigning some unique function φx : A → B to every color x ∈ [M ] (We abuse
notation and also
Prefer by φv the function assigned to v). Then every node iterates over all α ∈ A
and picks α s.t v∈e,φv (α)=φu (α) w(e) is minimized. We note that the family of functions used is
the family of polynomials degree at most k over some field. Finally the vertex is assigned the color
(α, φv (α)).
Analysis: We state a lemma analogous to Lemma 4.1 in [Kuh09]. We
P show that it is possible to
assign a color to v s.t the defect of the vertex increases by at most ǫ e∈Eb (v) w(e).
Lemma 13. Assume we are given an M -coloring of G. For a value k > 0 let the functions assigned
to the colors be such that for any two colors x, y ∈ [M ], the functions φx , φy intersect for at most k
values and s.t that |A| > kǫ−1 then the increase P
in the weighted defect of every vertex v of the new
coloring computed by the algorithm is at most ǫ e∈Eb (v) w(e).
Proof. We note that in the proof of Lemma 4.1 in [Kuh09], it is shown that if there two neighboring
nodes u, v with different colors that choose values αu , αv s.t φv (αv ) 6= φu (αu ) then after applying
Algorithm 1, the edge will be bi-chromatic.
We show that P
for every node v there exists some value α ∈ A s.t the increase in the weighted
defect is at most ǫ e∈Eb (v) w(e). Fix some node v and assume by contradiction that this is not the
case, thus
P for every α ∈ A it holds that the increase in weight of monochromatic edges is greater
than ǫ e∈Eb (v) w(e). Let us count the total weight of monochromatic edges for all values of α in
two different ways:
X
X
X
k
w(e) ≥
w(e) · χφv (α)=φu (α)
e∈Eb (v)

=

X

X

α∈A e=(u,v)∈Eb (v)

e=(u,v)∈Eb (v) α∈A

w(e) · χφv (α)=φu (α) > |A| ǫ

X

w(e)

e∈Eb (v)

Thus, we get that |A| < ǫ−1 k which is a contradiction.
Next the construction of such a family of functions remains the same using polynomials. Specifically, restating Theorem 4.6 in [Kuh09] using our parameters we get that:
Theorem 14. Assume we are given an M coloring of the graph. There are an explicit function
φx for x ∈ [M ] and a constant CD > 0 s.t Algorithm 1 computes a CD ǫ−2 log21/ǫ M coloring s.t the
weighted defect of every vertex v increases by at most ǫw(v).
14

Finally we prove a theorem equivalent to Theorem 4.9 in [Kuh09] using our parameters. The
proof is almost identical to the original one, and we present it here for completeness.
Theorem 2 For any constant ǫ ∈ (0, 1/e) a weighted ǫ-defective O(ǫ−2 )-coloring can be computed
deterministically in O(log∗ n) rounds in the CONGEST model.
Proof. Let M = [n] be the coloring induced by the unique identifiers of the√vertices. Define
ǫi = ǫ0 /2T −i , ǫ0 = ǫ/2, where T is the smallest positive integer s.t ln(T ) M ≤ 8 CD /ǫ0 . We run
Algorithm 1 T times with parameters ǫi in the i-th iteration.
For all values of i this implies that:
p
p
T −i
8 CD /ǫi = 8 CD ǫ−1
≤ 2T −i ln(T −1) M ≤ ln(i−1) M,
(1)
0 2
where the first inequality is due to the definition of T (that is, for T − 1 the inequality holds in the
other direction), and the second is due to the fact that for all x > 0 it holds that 2 ln x < x.
Using induction we show that for all i ≤ T we have that
(i)
2
Mi ≤ 16CD (ǫ−1
i ln M ) .

For i = 1 the claim holds by Theorem 14 (and because ǫ−1
0 > e). For the remaining values of i,
2
due to Theorem 14 it holds that Mi ≤ CD (ǫ−1
·
log
M
i−1 ) . Thus, it is enough to show that
1/ǫi
i
log1/ǫi Mi−1 ≤ 4 ln(i) M . It holds that
log1/ǫi Mi−1 ≤(1) ln Mi−1

(i−1)
(i−1)
≤ ln 16CD (ǫ−1
M )2 = ln 16CD (2ǫ−1
M )2
i−1 ln
i ln

≤(2) ln (ln(i−1) M )4 ≤ 4 ln(i) M,

where the first inequality is due to the fact that ǫ−1
to inequality (1).
0 ≥ e and the third is due
√
−1 (T )
Finally plugging in i = T we get that: MT ≤ 16CD ǫ0 ln M ≤ 16CD /ǫ0 · 8 CD /ǫ0 = O(ǫ−2 ).
P
As the the weighted ǫ-defect for every vertex v is bounded by w(v) Ti=0 ǫi ≤ ǫw(v), this completes
the proof.

B

Omitted Pseudocodes and Proofs

Algorithm 4 is the pseudo code for the distributed version of an orderless-local algorithm. Algorithm 5 is the deterministic 1/3-approximation for unconstrained submodular maximization
of [BFNS15]. Algorithm 6 and Algorithm 7 are the psedocode the randomized 1/2-approximation
algorithm of [BFNS15] expressed as an orderless local algorithm. Algorithm 8 and Algorithm 9 are
the deterministic and randomized approximation algorithms for the cut functions.

15

Algorithm 4: OLDist(G, ~r, ϕ)
1
2
3
4
5
6

∀v ∈ V, Xv = init(Lv [X])
for i from 1 to c do
foreach v s.t ϕ(v) = i simultaneously do
Xvi = decide(Lv [X], ri )
Send Xvi to neighbors
return X

Algorithm 5: det-usm(f )
1
2
3
4
5
6
7
8
9
10
11

Z0 = {Xv = 0 | v ∈ V }, Y0 = {Xv = 1 | v ∈ V }
for i from 1 to n do
ai = f (Zi−1 ∪ {Xvi = 1}) − f (Zi−1 )
bi = f (Yi−1 ∪ {Xvi = 0}) − f (Yi−1 )
if ai ≥ bi then
Zi = Zi−1 ∪ {Xvi = 1}
Yi = Yi−1
else
Zi = Zi−1
Yi = Yi−1 ∪ {Xvi = 0}
return Zn

Algorithm 6: rand-usm(G, ~r, π)

4

∀v ∈ V, Xv = (0, 1)
Order the vertices according to π
for i from 1 to n do
Xu = decide(Lv [X], ~ri )

5

return Xn

1
2
3

16

Algorithm 7: decide(Lv [X], r)

1 Z = Xu = αu,1 | {Xu = (αu,1 , αu,2 )} ∈ Lv [X]

2 Y = Xu = αu,2 | {Xu = (αu,1 , αu,2 )} ∈ Lv [X]
3 a = max {gv (Z, 0, 1), 0}
4 b = max {gv (Z, 1, 0), 0}
5 if a + b = 0 then
6
p=1
7
8
9
10
11
12
13

else
p = a/(a + b)
Flip coin with probability p
if heads then
return (1,1)
else
return (0,0)

Algorithm 8: approxCutDet(G, ǫ)
1
2
3

ϕ = epsilonColor(G, ǫ)
Let G′ = (V, E ′ = {(v, u) ∈ E | ϕ(v) 6= ϕ(u)})
Cut(G′ , ϕ)

Algorithm 9: approxCutRand(G, ǫ)
1
2
3

Each vertex v chooses ϕ(v) uniformly at random from [⌈ǫ−1 ⌉]
Let G′ = (V, E ′ = {(v, u) ∈ E | ϕ(v) 6= ϕ(u)})
Cut(G′ , ϕ)

17

Lemma 1 The utility functions for Max k-Cut, Max-DiCut and max-agree correlation clustering
with 2 clusters are local utility functions.
P
Proof. The utility functions for Max k-Cut is given by f (X) = e=(w,u)∈E w(e) · Xw ⊕ Xu where
Xw ⊕ Xu = 0 if Xw = Xu and 1 otherwise. Thus, if we fix some v it holds that

f (X ∪ Xv = α′ ) − f (X ∪ {Xv = α})
X
X
=
w(e) · α′ ⊕ Xu −
w(e) · α ⊕ Xu
e=(v,u)∈E

=

X
e=(v,u)∈E

e=(v,u)∈E

′

w(e) · (α ⊕ Xu − α ⊕ Xu ) = gv (Lv [X], α′ , α)

Note that the sum now only depends on vertices u ∈ N (v), and we are P
done.
For the problem of Max-DiCut the utility functions is given by f (X) = e=(v→u)∈E w(e) · Xv ∧
(1 − Xu ),Pand for max-agree correlation clustering
with 2 clusters the utility function is given by
P
f (X) = e=(v,u)∈E + w(e) · (1 − Xv ⊕ Xu ) + e=(v,u)∈E − w(e) · Xv ⊕ Xu (E + , E − are the positive
and negative edges, respectively), and the proof is exactly the same.
Lemma 3 For any graph G with a legal coloring ϕ, there exists an order π on the variables s.t it
holds that OL(G, ~r, π) = OLDist(G, ~r, π) for any ~r.
Proof. We prove the claim by induction on the executions of color classes by the distributed algorithm. We note that the execution of the distributed algorithm defines an order on the variables.

k
Let us consider the i-th color class. Let us denote these variables as Xvj j=1 , assigning some
arbitrary order within the class. The ordering we analyze for the sequential algorithm would be
π(vj ) = (ϕ(v), j). Now both the distributed and sequential algorithms follow the same order of
color classes, thus we allow ourselves to talk about the sequential algorithm finishing an execution
of a color class.
Let Yi be the assignments to all variables of the distributed algorithm after the i-th color class
finishes execution. And let Yi′ be the assignments made by the sequential algorithm following π until
all variable in the i-th color class are assigned. Both algorithms initiate the variables identically,
′ . The coloring is legal, so for any
so it holds that Y0 = Y0′ . Assume that it holds that Yi−1 = Yi−1
Xu , Xv , s.t ϕ(u) = ϕ(v) = i it holds that N (v) ∩ u = ∅. Thus, when assigning v, its neighborhood
is not affected by any other assignments done in the color class, so the randomness is identical for
both algorithms, and using the induction hypothesis all assignments up until this color class were
identical. Thus, for all variables in this color class decide will be executed with the same parameters
for both the distributed and sequential algorithms, and all assignments will be identical.
Lemma 5 The value argmaxα E[f (X) | Y, Xv = αv ] − E[f (X) | Y ] can be computed locally.
Proof. It holds that:
E[f (X) | Y, Xv = αv ] − E[f (X) | Y ]
X
X
E[f (X) | Y, Xv = α]P r[Xv = α]
=
E[f (X) | Y, Xv = αv ]P r[Xv = α] −
α∈A

α∈A

=

X
α∈A

P r[Xv = α](E[f (X) | Y, Xv = αv ] − E[f (X) | Y, Xv = α])
18

P
Where the first equality is due to the law of total expectation and the fact that α∈A P r[Xv =
α] = 1. The probability of assigning Xv to some value can be computed locally, so we are only left
with the difference between the expectations. To show that this is indeed a local quantity we use
the definition of expectation as a weighted summation over all possible assignments to unassigned
variables. Let Uv be the set of all possible assignments to unassigned variables in N (v) and let U
be the set of all possible assignments to the rest of the unassigned variables. It holds that:
E[f (X) | Y, Xv = αv ] − E[f (X) | Y, Xv = α]
X X
P r[Zv ]P r[Z]f (X ∪ Zv ∪ Z ∪ {Xv = αv }) − f (X ∪ Zv ∪ Z ∪ {Xv = α})
=
Zv ∈Uv Z∈U

=

X X
Zv ∈Uv Z∈U

=

X
Zv ∈Uv

P r[Zv ]P r[Z]gv (Lv [X ∪ Zv ∪ Z], α, αv ) =

X X
Zv ∈Uv Z∈U

P r[Zv ]P r[Z]gv (Lv [X ∪ Zv ], α, αv )

P r[Zv ]gv (Lv [X ∪ Zv ], α, αv ),

where in the first equality we use the definition of expectations and the fact that the variables
are set independently of each other. Then we use the definition of a local utility function, and
finally the dependence on U disappears due to the law of total probability. The final sum can be
computed locally, as the probabilities for assigning variables in Zv are known and gv is local.

C

Max 2-SAT

In this section we consider the problem of Max 2-SAT. We are given a set of weighted clauses
C over the set of node variables, such that each clause contains at most two literals. We wish
to find an assignment maximizing the weight of satisfied clauses. As before, we are interested in
adapting a sequential algorithm to the distributed setting. The algorithm we shall adapt is the
sequential algorithm presented in [PSWvZ17] which achieves a 3/4-approximation in expectation
for the problem of weighted Max-SAT. It is based on the results of [BFNS15], thus it is almost
identical to Algorithm 3. Before presenting the algorithm we need some preliminary definitions.
We allow the node variables to take on values in {0, 1, ∅} where Xv = ∅ means that the value
to Xv has not yet been assigned. We define two utility functions, the first, fT counts the weight
of clauses satisfied given the assignment, and the second fF counts the weight of clauses that
are unsatisfied given the assignment (all literals are false). We note that until now our functions
depended on the node variables and the topology of the graph (which we omitted as a parameter),
and now they also depend on the clauses. As with the topology, when we pass X as a parameter
we assume we also pass all of the clauses, while when we pass Lv [X] as a parameter, we assume we
also pass all of the clauses that contain Xv as a literal.
For every C ∈ C we define two values, CT (X), CF (X), where CT (X) = w(C) if the clause is
satisfied by X (and 0 otherwise) while CP
is falsified by the assignment
F (X) = w(C) if the clause P
(and 0 otherwise). It holds that fT (X) = C∈C CT (X) and fF (X) = C∈C CF (X). Both functions
are local utility functions. We prove the following lemma.
Lemma 15. Both fT and fF are local utility functions.
Proof. Let us assign each clause C to one of the variables which appears in it as a literal (perhaps
there is only a single one). Denote for each variable by Cv the set of clauses assigned to it. Because
this is a 2-SAT instance, it holds that if C ∈ Cv then CT (X) = CT (Lv [X]) and CF (X) = CF (Lv [X]).
19

It holds that fT (X) =

P

v∈V

P

C∈Cv

CT (Lv [X]). Thus it holds that:


fT (X ∪ Xv = α′ ) − fT (X ∪ {Xv = α})
X X

CT (Lu [X] ∪ Xv = α′ ) − CT (Lu [X] ∪ {Xv = α})
=
u∈N (v) C∈Cu

=

X

X

u∈N (v) C∈Cu


CT (Lv [X] ∪ Xv = α′ ) − CT (Lv [X] ∪ {Xv = α}) = gv (Lv [X, α′ , α]),

where the first equality is because all clauses that do not contain Xv as a literal immediately get
removed from the sum, and the final equality is because the clauses are of size at most two, thus
every clause that is affected by an assignment to Xv only depends on Xv and Xu s.t u ∈ N (v).
This finishes the proof for fT . The proof for fF is identical.
Now we describe the algorithm of [PSWvZ17] (Algorithm 10) for the special case of weighted
Max 2-SAT on graphs. Initially all variables are unassigned. The algorithm iterates over the
variables in any order. Our aim in each iteration is to maximize the difference between the weight of
the satisfied clauses and that of the unsatisfied clauses given the partial assignment. The algorithm
calculates two quantities ti , fi , which correspond to this difference if we set the current variable to
0 or 1, given the current partial assignment. Finally, we flip a coin and set the variable to each
value with a probability proportional to its benefit. If the benefit is negative, this probability is 0.
Algorithm 10: rand-MaxSAT(G, C)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

X = {Xv = ∅ | v ∈ V }
Define any order over the variables: Xv1 , ..., Xvn for i from 1 to n do
ti = (fT (X ∪ {Xvi = 1}) − fT (X)) − (fF (X ∪ {Xvi = 1}) − fF (X))
fi = (fT (X ∪ {Xvi = 0}) − fT (X)) − (fF (X ∪ {Xvi = 0}) − fF (X))
if fi ≤ 0 then
p=1
else if ti ≤ 0 then
p=0
else
p = ti /(ti + fi )
Flip a coin with probability p
if heads then
Xvi = 1
else
Xvi = 0
return X

Due to Lemma 15 we see that calculating ti , fi can be done locally, and thus Algorithm 10 is
an orderless-local algorithm. Thus we can immidiatly state the following theorem:
Theorem 16. For any graph G and a Weighted Max 2-SAT instance, there exists a randomized
distributed expected 3/4-approximation algorithm running in O(c) communication rounds in the
20

CONGEST model, given a legal c-coloring.
We now show that the same technique used for the Max-DiCut problem can be applied here.
We consider the distributed algorithm guaranteed from Theorem 16. We note that in order to
compute ti , fi for some node v we only need to know the variables in the 1-hop environment that
share a clause with v. Thus, if there is an edge (u, v) ∈ E but no clause depends on both Xv , Xu we
may drop that edge. Formally, if we define by H(V, EH ) the graph resulting from G by dropping
all said edges, the execution of the algorithm for H is identical to that of G. And now we may use
the same method as before of coloring the vertices at random with colors from [⌈ǫ−1 ⌉].
Let us ignore nodes in H which have no edges. These nodes may only contain unit clauses
(clauses with a single literal), and the solution achieved by the greedy algorithm for that subset of
clauses is optimal. This is because if a node only contains a single literal, the algorithm will satisfy
that literal. If it contains two literals which contradict each other, any assignment satisfies one of
them, which is optimal.
Let us now assign every clause containing two literals to the edge between the two nodes, and any
unit clause to one of the node’s edges, denote this set
for every edge eP∈ EH . Next
P of clauses by Ce P
we define for every e ∈ EH its weight to be w(e) = C∈Ce w(C), thus e∈EH w(e) = C∈C w(c) =
w(C).
From here the proof follows the lines of Section 3.3. Let H ′ be the graph resulting from H after
removing all monochromatic edges and all clauses associated with those edges. This results in a
an expected decrease of ǫw(C) in total clause weight. We prove a lemma equivalent to Lemma 8 in
Section 3.3.
′ ) be a graph resulting from removing any subset of edges from H of
Lemma 17. Let H ′ (V, EH
weight at most ǫw(C). Then for any constant p, any p-approximation for Max 2-SAT for H ′ is a
p(1 − 2ǫ)-approximation for H.

Proof. Let OP T, OP T ′ be optimal solutions for H, H ′ , respectively. We can immediately see that
OP T ′ ≥ OP T − ǫw(C), as any solution for H is also a solution for H ′ whose value differs by at
most ǫw(C). Using the probabilistic method it is easy to see that for Weighted Max 2-SAT it holds
that OP T ≥ w(C)/2. Using all of the above we can say that given a p-approximate solution for
OP T ′ it holds that:
p · OP T ′ ≥ p(OP T − ǫw(C)) ≥ p(OP T − 2ǫOP T ) = p(1 − 2ǫ)OP T

Finally the proof of the expected approximation value follows exactly as in Section 3.3. We
state the main theorem for this section.
Theorem 18. There exists a randomized distributed (3/4 − ǫ)-approximation for Weighted Max
2-SAT running in O(ǫ−1 ) communication rounds in the CONGEST model.

21

