# Distributed Subgraph Finding: Progress and Challenges

Keren Censor-Hillel
Department of Computer Science, Technion
<EMAIL_ADDRESS>
###### Abstract

This is a survey of the exciting recent progress made in understanding the
complexity of distributed subgraph finding problems. It overviews the results
and techniques for assorted variants of subgraph finding problems in various
models of distributed computing, and states intriguing open questions. This
version contains some updates over the ICALP 2021 version, and I will try to
keep updating it as additional progress is made.

Revisions (most recent first):

  * •

December 2022: Corrected the variant of triangle finding studied with respect
to the number of triangles in the graph – from listing to detection.
Corrected a typo in running time of sparse matrix multiplication.

  * •

November 2022: Added new results on deterministic clique listing and quantum
algorithms.

##  1 Introduction

Distributed subgraph finding is motivated by considering a user in a network
whose connections are unknown to its users. Typical examples could be friends
or followers in social networks, or computing devices in large networks. A
prime question is what is the local structure of the network, e.g., do two
connected users share common connections, or are they part of a slightly
larger cycle or clique? While some social networks provide the user with
information about common connections they have with their connections, the
general fundamental question that arises is that of finding small subgraphs in
such distributed settings. This type of questions also emerges when processing
huge graphs by distributed systems. For example, Hirvonen, Rybicki, Schmid,
and Suomela [HRSS17] study distributed algorithms for finding large cuts in
triangle-free graphs, and Pettie and Su [PS13] study coloring in triangle-free
graphs.

This article surveys the state-of-the-art in distributed subgraph finding. We
focus on synchronous settings, in which the main complexity measure is the
number of communication rounds that is required in order to find a subgraph
$H$. We will elaborate on the computational models and on the possible
interpretations of what it means to _find_ a subgraph, but let us start with a
warm-up.

Warm-up: locality. The first simple observation is that in a synchronous
network with no additional restrictions, the round complexity of finding a
subgraph $H$ by the devices in the network is $\Theta(k)$, where $k$ is the
diameter of $H$. The reason for this is that in a single round of
communication, all nodes of the network can learn the neighbors of their
neighbors,111This assumes that all nodes begin with knowledge of their
neighbors. Removing this assumption incurs another round of communication to
this argument. and by induction, within $t$ rounds each node can learn the
topology within its $t$-neighborhood.

To be more precise, what we get is that within $O(k)$ rounds, each node is
able to _list_ all the instances of $H$ to which it belongs. This is the most
powerful variant of subgraph finding.

The clear drawback of the above example is that it sweeps the under the carpet
the complexity of sending potentially very large messages in a single round.
Therefore, while the above classic $\mathsf{LOCAL}$ model [Lin92] is suitable
for studying many other tasks, it misrepresents the complexity of subgraph
finding. We will thus focus mainly on two distributed settings that capture
limited bandwidth, and in which the complexity of some subgraph finding
problems is related. Additional settings will be discussed towards the end of
the survey.

Computational models. The standard model that imposes restrictions on the
bandwidth over the above setting is the $\mathsf{CONGEST}$ model [Pel00]. This
is a synchronous model, in which each of $n$ nodes can send a message to each
of its neighbors in every round, where the size of messages is bounded by
$O(\log{n})$ bits. This choice of this bound on the size of messages allows
sending a node identifier within a single message. Typically, the graph that
is processed is the graph that underlies the communication network.

Another important model is the $\mathsf{CONGESTED~{}CLIQUE}$ model [LPPP05],
which we will abbreviate as the $\mathsf{CLIQUE}$ model in this document, in
which the $n$ nodes are part of a fully connected network, with the same
message bound of $O(\log{n})$ bits as in the $\mathsf{CONGEST}$ model. Here,
the input graph is an arbitrary graph $G$ on $n$ nodes, which is typically
assigned through a bijection to the nodes of the $\mathsf{CLIQUE}$, such that
each node receives as input the edges in $G$ that are adjacent to its assigned
node.

Subgraph finding. The extreme case mentioned above, where each node in the
system lists all instances of $H$ to which it belongs is referred to as
_membership listing_ (or sometimes _local listing_ or _local enumeration_). In
settings with bounded bandwidth, this is typically a difficult variant that is
known to require many rounds of computation for many subgraphs (see, e.g.,
discussion about triangle finding in Section 2). A weaker variant is that of
_listing_ or _enumeration_ , in which it is required that every instance of
the subgraph $H$ is output by some node, but not necessarily a node which
belongs to that instance.

Apart from these two listing variants, it is in many cases important to merely
_detect_ whether the input contains a copy of $H$ or not. The standard
formalization of distributed detection is that if there is no copy of $H$ then
all nodes output false, and otherwise at least one node outputs true. The
reason for not demanding a unanimous output is to avoid incurring an overhead
just for propagating the information of existence of $H$, for example if a
graph contains a single copy of $H$ and has many nodes that are very far from
that instance.

Similarly to the case of listing, the detection problem also has a membership
variant, which requires each node to output true or false based on whether it
is a part of a copy of $H$ or not.

Outline. Section 2 overviews the case in which $H$ is a triangle. It covers
both the $\mathsf{CLIQUE}$ and the $\mathsf{CONGEST}$ models. Sections 3 and 4
address larger cliques and larger cycles in both models, respectively.
Finally, Section 5 briefly mentions additional subgraphs and additional
settings.

##  2 Triangle Finding

A naïve simulation of the warm-up algorithm for membership listing in the
$\mathsf{CONGEST}$ or $\mathsf{CLIQUE}$ models, in which all neighbors are
sent to each other neighbor one by one, gives a trivial $O(\Delta)$-round
algorithm for triangle membership listing, where $\Delta$ is the maximum
degree in the graph. However, it is possible to do better, as we overview in
this section.

###  2.1 Triangle Finding in the $\mathsf{CLIQUE}$ Model

We begin with the $\mathsf{CLIQUE}$ model.

Triangle listing in the $\mathsf{CLIQUE}$ model. The first non-trivial
algorithm for triangle finding is due to Dolev, Lenzen, and Peled [DLP12].
This is a deterministic triangle listing algorithm for the $\mathsf{CLIQUE}$
model, which has a complexity of $O(n^{1/3}/\log{n})$ rounds. The simplicity
of this algorithm turned out to be a huge advantage for later additional
results, as we will see. The algorithm works as follows: The vertices of the
graph are partitioned into $n^{1/3}$ subsets $S_{1},\dots,S_{n^{1/3}}$, each
of $n^{2/3}$ nodes. Each of the $n$ nodes receives a different tuple of three
of these subsets. A node that receives $S_{i_{1}},S_{i_{2}},S_{i_{3}}$ for
indices $1\leq i_{1},i_{2},i_{3}\leq n^{1/3}$ (that are not necessarily
different) collects all edges with one endpoint in one of the three subsets
and one endpoint in another, that is, this node collects all edges in
$E(S_{i_{1}},S_{i_{2}})\cup E(S_{i_{1}},S_{i_{3}})\cup
E(S_{i_{2}},S_{i_{3}})$, and reports all triangles that it finds. It is
straightforward to see that all triangles are listed by this algorithm since
the number of 3-tuples of subsets is $n$ and so each is handled by some node.

The round complexity of the algorithm follows by proving that each node needs
to send and receive $O(n^{4/3})$ edges in total, which are to and from
locations that are known to all nodes (we will discuss this knowledge property
later), since the partition to subsets is hardcoded and so it is known to all
nodes. Sending: Take a node $v$ and assume that it is in the subset $S_{i}$.
There can be at most $n^{2/3}$ edges between $v$ and nodes in $S_{j}$ and
these edges need to be sent to all nodes that have $S_{i}$ and $S_{j}$ in
their 3-tuple. Since there are $n^{1/3}$ such 3-tuples, these $n^{2/3}$ edges
need to be sent to $n^{1/3}$ nodes. Repeating this for all $n^{1/3}$
possibilities for $j$ gives a total of $n^{2/3+1/3+1/3}=n^{4/3}$ edges that
$v$ has to send. Receiving: Each node needs to learn 3 subsets of edges, each
containing at most $n^{2/3}\cdot n^{2/3}=n^{4/3}$ edges. To conclude the
complexity analysis, one can use the simple claim that [DLP12] proves, which
states that a routing task in which each node needs to send and receive $n$
messages in a known pattern can be done in 2 rounds. This means that the
$O(n^{4/3})$ sent and received messages per node are divided by $n$, yielding
a complexity of $O(n^{1/3})$ rounds. Noticing that the partition and routing
are fixed, one can refrain from sending actual edge identifiers and replace
them with a bit mask, which saves a logarithmic factor and results in a
complexity of $O(n^{1/3}/\log{n})$ rounds.

This complexity turns out to be optimal. The first lower bound for this task
was of $\Omega(n^{1/3}/\log^{3}{n})$ rounds given by Pandurangan, Robinson and
Scquizzato [PRS18], and it was followed by a tight lower bound of
$\Omega(n^{1/3}/\log{n})$ rounds given by Izumi and Le Gall [ILG17]. The lower
bound is proven using an information-theoretic argument, which bounds by
$\Omega(n^{4/3})$ the entropy of the transcript that a certain node sees on a
random graph in which each edge appears independently at random with
probability $1/2$. As the entropy of the transcript is a lower bound on its
length, and since each node can receive at most $O(n\log{n})$ bits per round,
the lower bound on the round complexity follows. This approach also allowed
[ILG17] to obtain a lower bound of $\Omega(n/\log{n})$ rounds for _local_
listing of triangles, in which each node needs to output a list of all the
triangles which include it.

Triangle detection in the $\mathsf{CLIQUE}$ model. The approach of [DLP12]
inherently lists all triangles. A natural question is whether the decision
problem of triangle detection is easier than listing, for which the answer
turns out to be affirmative. Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, and
Suomela [CKK+19] show how to perform matrix multiplication over a ring in the
$\mathsf{CLIQUE}$ model within $O(n^{0.158})$ rounds. More precisely, the
complexity is $O(n^{1-2/\omega})$ rounds, where $\omega$ is the matrix
multiplication exponent, currently known to be bounded by $2.3728596$ due to
Alman and Vassilevska-Williams [AW21]. Ring matrix multiplication directly
carries over to triangle detection with the same complexity. The main approach
of [CKK+19] is to simulate matrix multiplication algorithms for parallel
settings in the $\mathsf{CLIQUE}$ model. This includes the so-called parallel
3D matrix multiplication, as well as bilinear Strassen-like algorithms.

Elaborating upon the matrix multiplication algorithms is beyond the scope of
this survey. Yet, we must mention a crucial component that underlies these
$\mathsf{CLIQUE}$ algorithms, as well as numerous additional $\mathsf{CLIQUE}$
algorithms for various tasks, which is the ingenious routing technique of
Lenzen [Len13]. In a nutshell, this technique provides a way to route in
$O(1)$ rounds any set of messages in which each node needs to send and receive
at most $n$ messages.

The above complexity of $O(n^{0.158})$ rounds for triangle detection in the
$\mathsf{CLIQUE}$ model is the current state-of-the-art. For reasons that will
be explained shortly, unlike the $\Omega(n^{1/3})$ lower bound for triangle
listing in this model, there is no known lower bound for triangle detection.
We thus have the following major open problem in distributed triangle finding.

######  Open Problem 2.1.

What is the complexity of triangle detection in the $\mathsf{CLIQUE}$ model?
In particular, is there an algorithm that is faster than $O(n^{0.158})$
rounds? Can any lower bound be proven?

The second part of the above question which asks for a lower bound for
triangle detection in the $\mathsf{CLIQUE}$ model is considered hard: Very
roughly speaking, Drucker, Kuhn, and Oshman [DKO14] show that the
$\mathsf{CLIQUE}$ model is strong enough to simulate certain circuits, which
implies that for a wide range of problems, any super-constant lower bound in
the $\mathsf{CLIQUE}$ model would result in a major breakthrough in circuit
complexity. It is noteworthy that the problem of triangle listing does not
fall into this category of problems due to its large outputs, which explains
why this does not contradict the aforementioned lower bound of
$\Omega(n^{1/3})$ rounds for triangle listing.

In addition to the aforementioned algorithm of [DLP12], the paper also gives a
triangle-detection algorithm whose complexity improves upon the above in the
case that the graph contains _many_ triangles. Specifically, they provide a
randomized algorithm that completes in $O(n^{1/3}/(t^{2/3}+1)+1)$ rounds in
expectation, where $t$ is the number of triangles in the graph, and in
$O(\min\\{n^{1/3}\log^{2/3}{n}/(t^{2/3}+1),n^{1/3}\\})$ rounds with high
probability.

For the broadcast version of this model, a.k.a. the
$\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$ model, in which the messages sent by
a node in a certain round must all be identical, an
$\Omega(n/e^{O(\sqrt{\log{n}})}\log{n})$-round lower bound on deterministic
triangle detection is given by [DKO14], through a reduction from 3-party
number-on-forehead set disjointness.

Triangle listing in sparse graphs in the $\mathsf{CLIQUE}$ model. The first
algorithms for triangle finding in sparse graphs were given by Dolev, Lenzen,
and Peled [DLP12]. One algorithm has a round complexity of $O(\Delta^{2}/n+1)$
and another has a round complexity of $O(A^{2}/n+\log_{2+n/A^{2}}{n})$, where
$A$ is the arboricity of the graph.222The arboricity of a graph is the minimal
number of forests that contain all of its edges. While bounded by the maximum
degree $\Delta$, the arboricity can in some cases be much smaller, e.g., a
star has a linear maximum degree but its arboricity is 1. The latter implies a
round complexity of ${O}(m^{2}/n^{3})$, in terms of the number of edges, $m$.

Pandurangan, Robinson, and Scquizzato [PRS18] give a randomized triangle
listing algorithm that completes within $\tilde{O}(m/n^{5/3}+1)$ rounds,
w.h.p. At the heart of the algorithm lies the partitioning approach of
[DLP12], but more is needed in order to exploit sparsity. In [PRS18], the
partition is random, and the routing of edges to the nodes to which they are
assigned is done in a randomized load balanced manner. This approach is what
handles load balancing of the information that needs to be routed in the
system in a way which is sensitive to the sparsity of the graph, rather than
optimizing only for the worst case. Moreover, the aforementioned
$\tilde{\Omega}(n^{1/3})$ lower bound of [PRS18] for triangle listing in
general graphs follows from a $\tilde{\Omega}(m/n^{5/3})$ lower bound for
graphs with $m$ edges.333In fact, the results of [PRS18] hold for the
$k$-machine model (see Klauck, Nanongkai, Pandurangan, and Robinson [KNPR15]),
which is similar to the $\mathsf{CLIQUE}$ model, but has $k$ nodes rather than
$n$. For a general $k$, the complexity of the algorithm is
$\tilde{O}(m/n^{5/3}+n/k^{4/3})$, and the lower bound is
$\tilde{\Omega}(m/k^{5/3})$.

Censor-Hillel, Leitersdorf, and Turner [CLT20] obtained an algorithm for
sparse graphs, with a complexity of ${O}(m/n^{5/3}+1)$ which is similar to,
but slightly improves upon, the complexity of the algorithm of [PRS18], by
polylogarithmic factors. The algorithm of [CLT20] is deterministic and is
based on an algorithm for sparse matrix multiplication, which completes in
$O((\rho_{S}\rho_{T}/n)^{1/3}+1)$ rounds, where $S$ and $T$ are the input
matrices and $\rho_{A}$ is the average number of non-zero elements per row of
a matrix $A$ (i.e., it is the number of non-zero elements of $A$, divided by
$n$).444The sparse matrix multiplication algorithm of [CLT20] can also be
converted to the $k$-machine model, in which it has a complexity of
$O(n^{4/3}(\rho_{S}\rho_{T})^{1/3}/k^{5/3}+1)$ rounds. While the
aforementioned semi-ring matrix multiplication algorithm of [CKK+19] assigns
the $n^{3}$ element-wise multiplication to the nodes in an optimal manner, it
applies to the worst case. The general approach used by[CLT20] for sparse
matrix multiplication is to assign the element-wise multiplications to nodes
in a way which is optimal given the input sparsity. The way this is done is by
load balancing the number of non-zero elements that each node needs to send
and receive in order for all element-wise multiplications to be computed.

Notes on matrix multiplication in the $\mathsf{CLIQUE}$ model. The first
algorithm for matrix multiplication in this model is due to Drucker, Kuhn, and
Oshman [DKO14], who showed a randomized complexity of $O(n^{\omega-2})\approx
O(n^{0.373})$ rounds with high probability, for semirings. A deterministic
$O(n^{1/3})$-round algorithm for matrix multiplication over a semiring is
given in [CKK+19].

Censor-Hillel, Dory, Korhonen, and Leitersdorf [CDKL20] provide two additional
sparse matrix multiplication algorithms, used for distance computations.
Compared to [CLT20], these algorithms also benefit from sparsity of the output
matrix $P=ST$. More concretely, their first algorithm completes in
$O((\rho_{S}\rho_{T}\rho_{P})^{1/3}/n^{2/3}+1)$ rounds. This matches the
complexity algorithm of [CLT20] for a general $P$, but improves upon it for
sparse output matrices (recall that the multiplication of two sparse matrices
need not be sparse in general). The second algorithm of [CDKL20] pays an
additive $\log{n}$ over the first one, i.e., has a round complexity of
$O((\rho_{S}\rho_{T}\rho)^{1/3}/n^{2/3}+\log{n})$, but here $\rho_{P}$ is
replaced by $\rho$, which stands for the number of elements per row that are
needed. That is, there is no need to compute any element in the output matrix
$P$ that is not among the $\rho$ smallest ones in its row (given an
appropriate definition of the total order on matrix elements). In other words,
the complexity of this algorithm does not depend on the sparsity of $P=ST$,
but on some sparsity parameter that is given as input.

Additional algebraic algorithms in the $\mathsf{CLIQUE}$ model with important
applications were given by Le Gall [Gal16]. These include fast algorithms for
rectangular matrix multiplications, as well as for multiple instances of
matrix multiplication.

As explained earlier, we do not expect a lower bound for matrix multiplication
in the $\mathsf{CLIQUE}$ model. However, it is shown in [CKK+19] that a near-
linear number of rounds is required in the
$\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$ model.

Finally, we mention that matrix multiplication based algorithms also give
results for _counting_ for some small subgraphs [CKK+19, CLT20].

###  2.2 Triangle Finding in the $\mathsf{CONGEST}$ Model.

We now move to triangle finding problems in the $\mathsf{CONGEST}$ model.

The first breakthroughs in this model are the first non-trivial (sublinears)
algorithms due to Izumi and Le Gall [ILG17]. These are randomized algorithms
for triangle listing and detection in $O(n^{3/4}\log{n})$ and
$O(n^{2/3}\log^{2/3}{n})$ rounds w.h.p., respectively. The approach of these
algorithms is to split the task of finding triangles into two parts: one which
looks for triangles that are $\epsilon$-heavy and another which looks for
other triangles, where an $\epsilon$-heavy triangle is one in which at least
one of its edges appears in at least $n^{\epsilon}$ triangles. Very roughly
speaking, heavy triangles can be detected within $O(n^{1-\epsilon})$ rounds by
randomly sampling which edges to send, and can be listed in
$O(n^{1-\epsilon/2})$ rounds by randomly hashing the edges sent to different
neighbors. A more involved argument shows that non-heavy triangles can be
listed in $O(n^{1-\epsilon}+n^{(1+\epsilon)/2}\log{n})$ rounds, w.h.p.
Carefully plugging in the right values of $n^{\epsilon}=\tilde{O}(n^{1/3})$
and $n^{\epsilon}=\tilde{O}(n^{1/2})$ then gives the round complexities for
triangle detection and listing.

The breakthrough that came after [ILG17] is due to Chang, Pettie, and Zhang
[CPZ19], who showed triangle listing (and thus also detection) in the
$\mathsf{CONGEST}$ model in $\tilde{O}(n^{1/2})$ rounds, w.h.p. In a nutshell,
the main methodology of this algorithm has two elements: One element is an
algorithm for decomposing the graph into well-connected components which could
behave somewhat similarly to the $\mathsf{CLIQUE}$ model. The second element
is to have the nodes of each component search for triangles that have an edge
in the component.

In more detail, [CPZ19] showed how to compute the following expander
decomposition in $O(n^{1/2})$ rounds. This decomposition is a partition of the
set of edges of the graph into three sets. In the first set $E_{m}$, each
connected component has minimum degree $n^{1/2}$ and conductance
$\Omega(1/\operatorname{polylog}{n})$. The graph induced by the edges in the
second set, $E_{s}$, is such that its arboricity is at most $n^{1/2}$. The
third set of remaining edges, $E_{r}$ is at most a constant fraction of the
total number of edges, and the triangle listing algorithm which we discuss in
what follows recurses over this remaining set of edges. The algorithm for the
decomposition itself is beyond the scope of this survey, and here we only
mention that it is rather far from being merely a distributed implementation
of its centralized counterpart.555The actual decomposition result is more
general, with a parameter $\delta$ which is tuned here to be $\delta=1/2$ in
order to optimize the running time of the triangle listing algorithm that uses
it.

The triangle listing algorithm over the two first sets above then works as
follows. Since the arboricity in $E_{s}$ is bounded by $n^{1/2}$, triangles
with at least one edge in this set are listed in a straightforward manner,
using an orientation that is deduced by the decomposition algorithm. Then,
triangles with an edge in any high-conductance component (i.e., in $E_{m}$)
are listed by having the nodes of each component mimic a variant of the
triangle listing algorithm in the $\mathsf{CLIQUE}$ model of Dolev, Lenzen,
and Peleg [DLP12]. This mimicking has three aspects. First, it replaces the
deterministic partition of [DLP12] with a randomized partition, in order to
have a good probability for a good balance of information within the
component. Second, the fact that a component has large conductance indeed
implies that it has a small mixing time, but this alone is insufficient for
efficiently exchanging large amounts of information within the component. To
this end, the algorithm makes use of the random-walk based routing techniques
of Ghaffari, Kuhn, and Su [GKS17] and Ghaffari and Li [GL18], whose
complexities improve as the mixing time decreases. Finally, even with these
ingredients, some nodes of a component may have too many edges that touch them
that are not inside the component, preventing them from efficiently using
their inner-component edges for routing this large amount of information.
Thus, some additional edges are added to the set $E_{r}$ of remaining edges
that the decomposition left for recursing over.

The decomposition approach was refined by Chang and Saranurak [CS19], allowing
the complexity of triangle listing to drop to $\tilde{O}(n^{1/3})$ rounds,
w.h.p. Since the $\tilde{\Omega}(n^{1/3})$ lower bound for triangle listing in
the $\mathsf{CLIQUE}$ model directly applies also in $\mathsf{CONGEST}$, this
complexity is near-optimal (up to $\operatorname{polylog}{n}$ factors). At a
high level, the decomposition obtained in [CS19] improves upon the one in
[CPZ19] in that it does not have $E_{s}$ at all (the bounded arboricity part)
and in the complexity of obtaining it. In addition, a somewhat modified
version of the routing algorithms of [GKS17, GL18] is introduced, for the
triangle listing usage of the decomposition.

An additional algorithm for triangle listing is given by Huang, Pettie, Zhang,
and Zhang [HPZZ20]. The complexity of this algorithm, given in terms of the
maximum degree $\Delta$, is $O(\Delta/\log{n}+\log\log\Delta)$ rounds, w.h.p.
For $\Delta=\tilde{O}(n^{1/3})$, this is faster compared with the algorithm of
[CS20], while the latter is faster for the larger range of $\Delta$.

Chang and Saranurak [CS20] then show deterministic algorithms for expander
decomposition and for expander routing. These yield round complexities of
$O(n^{0.58})$ and $n^{2/3}+o(1)$ for deterministic triangle detection and
triangle listing, respectively. Building upon this deterministic expander
decomposition and routing, Censor-Hillel, Leitersdorf, and Vulakh [CLV22]
showed deterministic triangle listing in $n^{1/3+o(1)}$ rounds. This
complexity nearly resolves the question of deterministic triangle listing, but
is slightly above the lower bound of $\tilde{\Omega}(n^{1/3})$ rounds, due to
the small $n^{o(1)}$ factor that arises from the deterministic expander
routing algorithm, leaving the following open question.

######  Open Problem 2.2.

Can deterministic expander routing be done in $\operatorname{polylog}{n}$
rounds to yield optimal deterministic triangle listing in the
$\mathsf{CONGEST}$ model, or is there a provable gap between the randomized
and deterministic complexities for this task?

The above are triangle listing algorithms so they clearly also solve the
detection variant. However, as opposed to triangle listing, for triangle
detection we currently do not have good lower bounds. What we do know is the
following. Abboud, Censor-Hillel, Khoury, and Lenzen [ACKL20] showed that
triangle detection cannot be solved in the $\mathsf{CONGEST}$ model within a
single round by a deterministic algorithm. Specifically, they showed that any
single-round algorithm requires a bandwidth of $\Delta\log{n}$ bits. Fischer,
Gonen, Kuhn, and Oshman [FGKO18] showed that this also holds for randomized
algorithms, by showing that randomized single-round algorithms require a
bandwidth of $\Delta$ bits. Both works also addressed the round complexity of
1-bit bandwidth algorithms, with a lower bound of $\Omega(\log^{*}{n})$ rounds
given in [ACKL20], which was improved to $\Omega(\log{n})$ rounds in
[FGKO18].666The function $\log^{*}{n}$ counts the number of times the
logarithm function needs to be applied starting from $n$ until the value drops
to at most 1.

We will later (Section 4) describe some lower bounds for finding other
subgraphs in the $\mathsf{CONGEST}$ model which are based on reductions from
2-party communication complexity problems, and there we will see why these
techniques do not give any meaningful lower bound for triangles. Moreover, in
the spirit of the aforementioned argument of Drucker, Kuhn, and Oshman
[DKO14], Eden, Fiat, Fischer, Kuhn, and Oshman [EFF+21] showed that any
polynomial lower bound of $\Omega(n^{\alpha})$ for some constant $\alpha$ for
triangle detection in $\mathsf{CONGEST}$ would imply major breakthroughs in
circuit complexity. This leaves us with another curious gap in our knowledge
of triangle finding in this model.

######  Open Problem 2.3.

What is the complexity of triangle detection in the $\mathsf{CONGEST}$ model
(randomized and deterministic)?

##  3 Finding Larger Cliques

The $\mathsf{CLIQUE}$ model: The deterministic triangle listing algorithm of
[DLP12] for the $\mathsf{CLIQUE}$ model can be easily generalized to list
larger cliques. To find cliques of size $p$ for some integer $p\geq 3$, the
set of nodes is partitioned into $n^{1/p}$ sets. Each node is assigned a
$p$-tuple of sets and learns all edges between any two of its sets. A similar
argument to that of triangles shows that indeed all $p$-cliques are listed by
this algorithm, and that its round complexity is $O(n^{1-2/p}/\log{n})$. In
fact, it is easy to see that this algorithm lists all instances of any
subgraph $H$ of $p$ nodes.

This complexity is optimal, due to a lower bound of
$\tilde{\Omega}(n^{1-2/p})$ rounds by Fischer, Gonen, Kuhn, and Oshman
[FGKO18], which generalizes the aforementioned lower bound for triangle
listing of [PRS18] and [ILG17], using additional machinery. In the
$\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$ model, Drucker, Kuhn, and Oshman
[DKO14] show that $\Omega(n/\log{n})$ rounds are needed for $p$-cliques, even
for the stronger detection variant, for almost all values of $p\geq 4$ (as
long as $p\leq(1-\epsilon)n$ for some constant $\epsilon>0$).

For sparse graphs, Censor-Hillel, Le Gall, and Leitersdorf [CGL20] show that
listing can be complete within $\tilde{O}(m/n^{1+2/p}+1)$ rounds, for $p\geq
3$. This follows from their $\mathsf{CONGEST}$ approach which is discussed
below, and is tight up to polylogarithmic factors using the lower bound
technique of [FGKO18, PRS18, ILG17]. This complexity was later obtained in a
deterministic manner by Censor-Hillel, Fischer, Gonen, Le Gall, Leitersdorf,
and Oshman [CFG+20].

As opposed to the listing variant, for $p$-clique detection the aforementioned
hardness of obtaining lower bounds in the $\mathsf{CLIQUE}$ model by [DKO14]
kicks in, and we do not know any non-constant lower bound (or any larger than
1 lower bound, for that matter), leaving the complexity of $p$-clique
detection open for $p>4$.

######  Open Problem 3.1.

What is the complexity of $p$-clique detection in the $\mathsf{CLIQUE}$ model
(randomized and deterministic), for $p\geq 4$?

The $\mathsf{CONGEST}$ model: Algorithms for finding larger cliques in the
$\mathsf{CONGEST}$ model, as in the case of triangles, are also based on the
conductance decomposition algorithms of Chang, Pettie, and Zhang [CPZ19] and
of Chang and Saranurak [CS19]. The first sublinear algorithms for larger
cliques in $\mathsf{CONGEST}$ are due to Eden, Fiat, Fischer, Kuhn, and Oshman
[EFF+21]. They show that $4$-cliques can be listed in
$\tilde{O}(n^{5/6+o(1)})$ rounds and that $5$-cliques can be listed in
$\tilde{O}(n^{73/75+o(1)})$ rounds, w.h.p. These listing algorithms are more
involved compared with the triangle listing algorithm, due to the need to
handle, for example, a $4$-clique with one edge within a certain component and
another edge within a different component, which imposes a complex challenge
that becomes even worse as $p$ grows.

Following [EFF+21], the work of Censor-Hillel, Le Gall, and Leitersdorf
[CGL20] provided algorithms for listing $p$-cliques in
$\tilde{O}(n^{p/(p+2)})$ rounds, w.h.p., for all $p\geq 4$ except for $p=5$.
For $p=5$, this work gave an algorithm which completes in
$\tilde{O}(n^{3/4+o(1)})$ rounds, w.h.p. The main approach of these algorithms
is iterating over the decomposition in a way that balances the minimum degree
and the arboricity thresholds. Within each cluster, sparsity-aware listing
helps speeding up the computation. While these algorithms improved upon the
state-of-the-art for $p=4,5$ and were the first sublinear algorithms for
$p\geq 6$, they fell short of the [FGKO18] lower bound of
$\tilde{\Omega}(n^{1-2/p})$ rounds. The question of whether clique listing in
the $\mathsf{CONGEST}$ model is as easy as, or harder than, its
$\mathsf{CLIQUE}$ counterpart, was recently answered by Censor-Hillel, Chang,
Le Gall, and Leitersdorf [CCGL21], using the newer conductance decomposition
of Chang and Saranurak [CS19] and additional mechanisms for optimal sparsity-
aware listing and for efficient transmission of edges in the clusters.
Deterministic algorithms for $p$-clique listing were given by Censor-Hillel,
Leitersdorf, and Vulakh [CLV22], with round complexities of $n^{1-2/p+o(1)}$.
As is the case for triangles, these complexities are optimal up to the small
$n^{o(1)}$ factor that arises from the expander routing procedure of Chang and
Saranurak [CS20].

For $p=4$, the tight listing of [CCGL21] also implies that $4$-clique
detection is not easier than its listing counterpart in the $\mathsf{CONGEST}$
model. This is due to a lower bound of $\tilde{\Omega}(n^{1/2})$ for
$4$-clique detection in $\mathsf{CONGEST}$, by Czumaj and Konrad [CK18]. The
lower bound of [CK18] is more general, and says that detecting $p$-cliques in
the $\mathsf{CONGEST}$ model requires $\tilde{\Omega}(n^{1/2}/p)$ rounds for
$p\leq n^{1/2}$, and $\tilde{\Omega}(n/p)$ rounds for $p\geq n^{1/2}$. Thus,
for values of $p$ larger than $4$, there is still a gap between detection and
listing.

######  Open Problem 3.2.

What is the complexity of $p$-clique detection in the $\mathsf{CONGEST}$ model
(randomized and deterministic), for $p>4$?

The lower bound of [CK18] uses a reduction from 2-party set disjointness. The
same work also shows that listing can be done sufficiently fast by the two
parties, which shows that if the detection problems are harder, a different
lower bound technique must be used.

##  4 Finding Larger Cycles

The $\mathsf{CLIQUE}$ model: Since the algorithm of [DLP12] easily lists any
subgraph of $p$ nodes, we have that, in particular, $p$-cycles can be listed
in the $\mathsf{CLIQUE}$ model within $O(n^{1-2/p})$ rounds
(deterministically).

The detection variant was then addressed by Censor-Hillel, Kaski, Korhonen,
Lenzen, Paz, and Suomela [CKK+19], who show a deterministic constant-round
algorithm for detecting $4$-cycles. In addition, they show an
$O(n^{0.158})$-round algorithm for detecting $p$-cycles, for any constant $p$.
More accurately, the complexity is $2^{O(p)}n^{0.158}$ rounds. This is a
randomized algorithm that relies on the color coding technique of Alon,
Yuster, and Zwick [AYZ95], in order to avoid too much congestion that would be
caused by collecting all possible candidates for cycle nodes. More recently,
Censor-Hillel, Fischer, Gonen, Le Gall, Leitersdorf, and Oshman [CFG+20]
showed that $2p$-cycles can be detected in $O(1)$ rounds for any $p$, using a
technique which also allows fast girth approximation. This is, notably, a
deterministic algorithm. For odd values of $p$, it is still not known whether
there is a constant-round $p$-cycle detection algorithm.

######  Open Problem 4.1.

What is the complexity of $p$-cycle detection in the $\mathsf{CLIQUE}$ model
(randomized and deterministic), for odd values of $p$?

The $\mathsf{CONGEST}$ model: For $4$-cycle detection, Drucker, Kuhn, and
Oshman [DKO14] provide a tight complexity of $\tilde{\Theta}(n^{1/2})$, by
providing both an algorithm and a lower bound. They also show that for any odd
value of $p$, detecting $p$-cycles requires $\tilde{\Omega}(n)$ rounds. The
upper bound is obtained by setting a threshold of $T=2n^{1/2}$, and defining
heavy nodes as nodes with at least $T$ neighbors. First, all non-heavy nodes
send all their neighbors to all their neighbors, in $T$ rounds. This detects
$4$-cycles which have at least 2 non-neighboring non-heavy nodes. Then, a
heavy node $v$ with more than $T$ heavy neighbors reports that there exists a
$4$-cycle. Finally, a heavy node $v$ with at most $T$ heavy neighbors sends
its heavy neighbors to all of its neighbors, again in $T$ rounds. The reason
for which too many heavy neighbors imply a $4$-cycle is because this means
that the total number of neighbors of heavy neighbors is at least $T^{2}$,
which is more than $2n$, and so there must be a node other than $v$ which is
connected to two of the neighbors of $v$, and hence we have a $4$-cycle.
Otherwise, if $v$ sends its heavy neighbors to all of its neighbors, then any
$4$-cycle with two neighboring nodes that are heavy is detected by one of its
nodes (by a simple case analysis).

The matching lower bound for $4$-cycles is a good point of reference for
understanding lower bounds for the $\mathsf{CONGEST}$ model that rely on
reductions from 2-party communication complexity. It relies on the fact that
there is a $4$-cycle-free graph $G$ on $n$ nodes with $\Theta(n^{3/2})$ edges,
due to Erdös [Erd38], whose work implies that this is the Turán Number of
$4$-cycles [Tur41]. The setting is as follows. Each of two players, Alice and
Bob, has an input string of $k$ bits, $x=(x_{1},\dots,x_{k})$ and
$y=(y_{1},\dots,y_{k})$, respectively. By communicating with each other, the
players need to compute the set disjointness function $Disj(x,y)$, whose value
is 1 if and only if the input strings represent disjoint subsets of the set
$\\{1,\dots,k\\}$, that is, if and only if there is no index $1\leq i\leq k$
such that $x_{i}=y_{i}=1$. The 2-party set disjointness problem is known to
require exchanging $\Omega(k)$ bits, even by randomized protocols due to
Kalyanasundaram and Schnitger [KS92], Razborov [Raz90], and Bar-Yossef,
Jayram, Kumar, and Sivakumar [BJKS04]. The reduction to distributed detection
of $4$-cycles is as follows. Each of the two players takes a subgraph of the
$4$-cycle free graph $G$ according to their respective input. That is, the
edges of $G$ are mapped to the set $\\{1,\dots,k\\}$, with a value of $n$ for
which $k=\Theta(n^{3/2})$. Each player imagines a subgraph of $G$ that has an
edge for any index in which their input is 1. The players then imagine that
their two subgraphs are connect by a perfect matching: each node in Alice’s
subgraph is connected to the respective node in Bob’s subgraph (the nodes of
both subgraphs are the nodes of $G$). Now, it is easy to see that the combined
graph contains a $4$-cycle if and only if the input strings $x,y$ are
disjoint, as the only $4$-cycles that can occur are those that have two edges
from the perfect matching, and two edges that represent the same index in the
bit strings of the players. Thus, if Alice and Bob can simulate a distributed
algorithm for $4$-cycle detection, they solve set disjointness. They simulate
a given algorithm as follows. Any message that the algorithm sends between two
nodes that are in the same subgraph (either that of Alice of that of Bob) can
be internally simulated by the respective player. The only messages that need
to be explicitly sent between the two players are those that are sent along
the edges of the perfect matching. There are $n$ such edges, and so simulating
a round of the detection algorithms costs $O(n\log(n))$ bits of communication
between the two players. Since $\Omega(k)=\Omega(n^{3/2})$ is a lower bound on
the total number of bits that need to be exchanged for solving set
disjointness, we get that the distributed $4$-cycle detection algorithm must
consist of at least
$\Omega(k/n\log(n))=\Omega(n^{3/2}/n\log(n))=\tilde{\Omega}(n^{1/2})$ rounds.

A remark on triangle detection: While this approach for reductions which imply
$\mathsf{CONGEST}$ lower bounds is heavily used in the literature, it is
doomed to fail for triangle detection. The reason is that any triangle in a
graph has at least one player which knows at least two of its nodes and thus
all of its edges, which nullifies any attempt for a lower bound constructions,
regardless of the 2-party problem or the graph construction.

Korhonen and Rybicki [KR17] then showed that the $\tilde{\Omega}(n^{1/2})$
lower bound for $4$-cycles can be extended and applies to $p$-cycles for all
even values of $p$. Notably, in the spirit of the results of [DKO14], it is
shown in Censor-Hillel, Fischer, Gonen, Oshman, Le Gall, and Leitersdorf
[CFG+20] that going above this lower bound for $p=6$ would imply new lower
bounds in circuit complexity, which are considered hard to obtain. The reason
that this barrier for lower bounds works in the $\mathsf{CONGEST}$ model is
because it is shown that it is sufficient to consider high-conductance
clusters, and that these can simulate circuits in a similar manner to the
$\mathsf{CLIQUE}$ model.

On the upper bound side, Korhonen and Rybicki [KR17] showed that $p$-cycle
detection for any constant $p$ can be done in a linear in $n$ number of
rounds. For odd values of $p$, this is optimal due to the above lower bound.
They also showed that this can be done faster for degenerate graphs. Fischer,
Gonen, Kuhn, and Oshman [FGKO18] showed how to detect $2p$-cycles within
$O(n^{1-1/p(p-1)})$ rounds, for $p\geq 2$. This was subsequently improved by
Eden, Fiat, Fischer, Kuhn, and Oshman [EFF+21], who showed how to detect
$2p$-cycles in $\tilde{O}_{p}(n^{1-2/(p^{2}-p+2)})$ rounds for odd $p\geq 3$,
and in $\tilde{O}_{p}(n^{1-2/(p^{2}-2p+4)})$ rounds for even $p\geq 4$. They
also show that as opposed to the case of $4$-cliques, the listing variant of
$4$-cycles is harder than its detection counterpart, requiring
$\tilde{\Omega}(n)$ rounds. For $p=3,4,5$, Censor-Hillel, Fischer, Gonen,
Oshman, Le Gall, and Leitersdorf [CFG+20] then showed improved algorithms
(randomized) for detecting $2p$-cycles, which completes within
$\tilde{O}(n^{1-1/p})$ rounds. Still, the upper bounds here are above the
respective $\tilde{\Omega}(n^{1/2})$ lower bound.

######  Open Problem 4.2.

What is the complexity of $p$-cycle detection in the $\mathsf{CONGEST}$ model
(randomized and deterministic), for even value of $p\geq 6$?

Finding _induced_ cycles is a different task, as it is insufficient to have
edges that form a cycle, but rather also requires no other edges between nodes
of the cycle. This question was addressed by Le Gall and Miyamoto [GM21a], who
showed a lower bound of $\tilde{\Omega}(n)$ rounds for detecting induced
$p$-cycles for any $p\geq 4$. This implies that detection of induced cycles is
strictly harder than the non-induced case. This bound is tight for $p=4$, and
this work also shows that obtaining a higher lower bound for $p=5,6,7$ cannot
be done using the standard framework of reductions from 2-party communication
complexity problems. For larger values of $p\geq 8$, a lower bound of
$\tilde{\Omega}(n^{2-\Theta(1/p)})$ is given. In addition, this work studies
the problem of finding induced diamonds, which are $4$-cycles with exactly one
additional edge.

##  5 Additional Variants of Distributed Subgraph Finding

Finding Other Subgraphs: The literature has also been studying additional
subgraphs, apart from cliques and cycles.

Drucker, Kuhn, and Oshman [DKO14] study the complexity of finding trees and
complete bipartite subgraphs in the $\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$
model. Korhonen and Rybicki [KR17] show that trees can be detected in $O(1)$
rounds in the $\mathsf{BROADCAST~{}CONGEST}$ model. Nikabadi and Korhonen
[NK21] show algorithms for induced subgraphs, and lower bounds for induced
cycles were given by Le Gall and Miyamoto [GM21b].

On the lower bound front, Gonen and Oshman [GO17] showed lower bounds for
finding subgraphs that are created from smaller ones using certain allowed
operations. Fischer, Gonen, Kuhn, and Oshman [FGKO18] showed that for any
$p\geq 4$, there exists a subgraph $H$ of size $p$ such that $H$ detection
requires $\tilde{\Omega}(n^{2-\Theta(1/p)})$ rounds. Eden, Fiat, Fischer,
Kuhn, and Oshman [EFF+21] showed that this complexity is roughly the right
one, by providing an upper bound of $\tilde{O}(n^{2-2/(3p+1)}+o(1))$ rounds.
In particular, their result shows that there does not exist a constant-sized
subgraph for which detection requires a truly quadratic number of rounds.

Subgraph Freeness Testing: The variant of testing for $H$-freeness has also
been studied in the distributed setting, initially introduced by Brakerski and
Patt-Shamir [BP11].

The definition of distributed testing for $H$-freeness requires that if there
is no instance of $H$ in the graph then all the nodes output true, but instead
of requiring at least one node to output false in case there is an instance of
$H$ as would be an analog to the detection problem, testing only requires at
least one node to output false in case the graph is far from being $H$-free.
Here, being $\epsilon$-far from having a property is the same as its standard
definition by Goldreich, Goldwasser, and Ron [GGR98], and means that no matter
which $\epsilon$-fraction of the graph is changed (removed, in the case of
$H$-freeness), the resulting graph must still have a copy of $H$. For
triangles and other small subgraphs, this typically means that there are many
instances of $H$ in a graph that is far from being $H$-free.

For testing triangle-freeness, Censor-Hillel, Fischer, Schwartzman, and
Vasudev [CFSV19] showed a $O(1/\epsilon^{2})$-round algorithm. This was later
improved by Even, Fischer, Fraigniaud, Gonen, Levi, Medina, Montealegre,
Olivetti, Oshman, Rapaport, and Todinca [EFF+17] and Fraigniaud and Olivetti
[FO17] to a complexity of $O(1/\epsilon)$ rounds. These, along with the work
of Fraigniaud, Rapaport, Salo, and Todinca [FRST16] also show fast testing for
larger cliques, cycles, and additional subgraphs.

Subgraph Finding in Dynamic Networks: Subgraph finding has also been studied
from the perspective of dynamic networks. Bonne and Censor-Hillel [BC19]
characterize the bandwidth that is required for various clique finding
problems by algorithms that work in a dynamic setting and must produce the
correct answer immediately at the end of the round in which a topology change
occurs.

Subgraph finding in a harsh dynamic setting in which the number of topology
changes per round is unlimited, was studied by Censor-Hillel, Kolobov, and
Schwartzman [CKS21], who showed upper and lower bounds for small subgraphs.

Subgraph Finding in Quantum Networks: Izumi, Le Gall, and Magniez [ILM20] have
shown that in a quantum $\mathsf{CONGEST}$ model, triangle detection can be
solved within $\tilde{O}(n^{1/4})$ rounds, using a distributed version
developed by Izumi and Le Gall in [IG19] of a _Grover Search_ [Gro96]. Later,
Censor-Hillel, Fischer, Le Gall, Leitersdorf, and Oshman showed quantum
triangle detection in $\tilde{O}(n^{1/4})$ rounds and clique detection for
larger cliques, using nested Grover searchers [CFL+22]. Recently, van
Apeldoorn and de Vos [vAdV22] have shown algorithms for cycle detection and
girth computation in the quantum $\mathsf{CONGEST}$ model.

We note that the listing variant for triangles cannot be improved using
quantum tools, since it is obtained through information theoretic arguments,
which apply to this setting as well.

Acknowledgements. This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under grant agreement no.
755839. The author thanks Francois Le Gall for clarifications and Dean
Leitersdorf for useful feedback on a preliminary version of this survey.

## References

  * [ACKL20] Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen.  Fooling views: a new lower bound technique for distributed computations under congestion.  Distributed Computing, 33:545––559, 2020.
  * [AW21] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), 2021.
  * [AYZ95] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.
  * [BC19] Matthias Bonne and Keren Censor-Hillel.  Distributed detection of cliques in dynamic networks.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 132:1–132:15, 2019.
  * [BJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar.  An information statistics approach to data stream and communication complexity.  J. Comput. Syst. Sci., 68(4):702–732, 2004.
  * [BP11] Zvika Brakerski and Boaz Patt-Shamir.  Distributed discovery of large near-cliques.  Distributed Comput., 24(2):79–89, 2011.
  * [CCGL21] Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf.  Tight distributed listing of cliques.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
  * [CDKL20] Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf.  Fast approximate shortest paths in the congested clique.  Distributed Computing, 2020.
  * [CFG+20] Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman.  Fast distributed algorithms for girth, cycles and small subgraphs.  In Proceedings of the 34th International Symposium on Distributed Computing (DISC), pages 33:1–33:17, 2020.
  * [CFL+22] Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman.  Quantum distributed algorithms for detection of cliques.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 35:1–35:25, 2022.
  * [CFSV19] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev.  Fast distributed algorithms for testing graph properties.  Distributed Computing, 32(1):41–57, 2019.
  * [CGL20] Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf.  On distributed listing of cliques.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 474–482, 2020.
  * [CK18] Artur Czumaj and Christian Konrad.  Detecting cliques in CONGEST networks.  In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 16:1–16:15, 2018.
  * [CKK+19] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.  Algebraic methods in the congested clique.  Distributed Computing, 32(6):461–478, 2019.
  * [CKS21] Keren Censor-Hillel, Victor I. Kolobov, and Gregory Schwartzman.  Finding subgraphs in highly dynamic networks.  In In proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 140–150, 2021.
  * [CLT20] Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner.  Sparse matrix multiplication and triangle listing in the congested clique model.  Theor. Comput. Sci., 809:45–60, 2020.
  * [CLV22] Keren Censor-Hillel, Dean Leitersdorf, and David Vulakh.  Deterministic near-optimal distributed listing of cliques.  In Proc. of the Symp. on Principles of Distributed Comp. (PODC), pages 271–280, 2022.
  * [CPZ19] Yi-Jun Chang, Seth Pettie, and Hengjie Zhang.  Distributed triangle detection via expander decomposition.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 821–840, 2019.
  * [CS19] Yi-Jun Chang and Thatchaphol Saranurak.  Improved distributed expander decomposition and nearly optimal triangle enumeration.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 66–73, 2019.
  * [CS20] Yi-Jun Chang and Thatchaphol Saranurak.  Deterministic distributed expander decomposition and routing with applications in distributed derandomization.  In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 377–388, 2020.
  * [DKO14] Andrew Drucker, Fabian Kuhn, and Rotem Oshman.  On the power of the congested clique model.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 367–376, 2014.
  * [DLP12] Danny Dolev, Christoph Lenzen, and Shir Peled.  ”tri, tri again”: Finding triangles and small subgraphs in a distributed setting - (extended abstract).  In Proceedings of the 26th International Symposium on Distributed Computing (DISC), pages 195–209, 2012.
  * [EFF+17] Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca.  Three notes on distributed property testing.  In Proceedings of the 31st International Symposium on Distributed Computing (DISC), pages 15:1–15:30, 2017.
  * [EFF+21] Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman.  Sublinear-time distributed algorithms for detecting small cliques and even cycles.  In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), pages 15:1–15:16, 2019. Full version in Distributed Computing 2021.
  * [Erd38] Paul Erdös.  On sequences of integers no one of which divides the product of two others and on some related problems.  Inst. Math. Mech. Univ. Tomsk, 2:74 – 82, 1938.
  * [FGKO18] Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman.  Possibilities and impossibilities for distributed subgraph detection.  In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 153–162, 2018.
  * [FO17] Pierre Fraigniaud and Dennis Olivetti.  Distributed detection of cycles.  In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 153–162, 2017.
  * [FRST16] Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca.  Distributed testing of excluded subgraphs.  In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 342–356, 2016.
  * [Gal16] François Le Gall.  Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems.  In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 57–70, 2016.
  * [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  J. ACM, 45(4):653–750, 1998.
  * [GKS17] Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su.  Distributed MST and routing in almost mixing time.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 131–140, 2017.
  * [GL18] Mohsen Ghaffari and Jason Li.  New distributed algorithms in almost mixing time via transformations from parallel algorithms.  In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 31:1–31:16, 2018.
  * [GM21a] François Le Gall and Masayuki Miyamoto.  Lower bounds for induced cycle detection in distributed computing.  In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC), pages 58:1–58:19, 2021.
  * [GM21b] François Le Gall and Masayuki Miyamoto.  Lower bounds for induced cycle detection in distributed computing.  In 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, pages 58:1–58:19, 2021.
  * [GO17] Tzlil Gonen and Rotem Oshman.  Lower bounds for subgraph detection in the CONGEST model.  In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS), pages 6:1–6:16, 2017.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pages 212–219, 1996.
  * [HPZZ20] Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang.  The communication complexity of set intersection and multiple equality testing.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1715–1732, 2020.
  * [HRSS17] Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela.  Large cuts with local algorithms on triangle-free graphs.  Electron. J. Comb., 24(4):P4.21, 2017.
  * [IG19] Taisuke Izumi and François Le Gall.  Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 84–93, 2019.
  * [ILG17] Taisuke Izumi and François Le Gall.  Triangle finding and listing in CONGEST networks.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 381–389, 2017.
  * [ILM20] Taisuke Izumi, François Le Gall, and Frédéric Magniez.  Quantum distributed algorithm for triangle finding in the CONGEST model.  In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 23:1–23:13, 2020.
  * [KNPR15] Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson.  Distributed computation of large-scale graph problems.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391–410, 2015.
  * [KR17] Janne H. Korhonen and Joel Rybicki.  Deterministic subgraph detection in broadcast CONGEST.  In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS), pages 4:1–4:16, 2017.
  * [KS92] Bala Kalyanasundaram and Georg Schnitger.  The probabilistic communication complexity of set intersection.  SIAM J. Discret. Math., 5(4):545–557, 1992.
  * [Len13] Christoph Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 42–50, 2013.
  * [Lin92] Nathan Linial.  Locality in distributed graph algorithms.  SIAM J. Comput., 21(1):193–201, 1992.
  * [LPPP05] Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg.  Minimum-weight spanning tree construction in _O_(log log _n_) communication rounds.  SIAM J. Comput., 35(1):120–131, 2005.
  * [NK21] Amir Nikabadi and Janne H. Korhonen.  Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters.  In Proceedings of the 25th International Conference on Principles of Distributed Systems (OPODIS), volume 217, pages 15:1–15:18, 2021\.
  * [Pel00] David Peleg.  Distributed Computing: A Locality-Sensitive Approach.  Society for Industrial and Applied Mathematics, USA, 2000.
  * [PRS18] Gopal Pandurangan, Peter Robinson, and Michele Scquizzato.  On the distributed complexity of large-scale graph computations.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 405–414, 2018.
  * [PS13] Seth Pettie and Hsin-Hao Su.  Fast distributed coloring algorithms for triangle-free graphs.  In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 681–693, 2013.
  * [Raz90] Alexander A. Razborov.  On the distributional complexity of disjontness.  In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP), pages 249–253, 1990.
  * [Tur41] Paul Turán.  On an extremal problem in graph theory.  Mat. Fiz. Lapok, 48:436 – 452, 1941.
  * [vAdV22] Joran van Apeldoorn and Tijn de Vos.  A framework for distributed quantum queries in the CONGEST model.  In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC), pages 109–119, 2022.


# Cosmological implications of the Gaia Milky Way declining rotation curve.

Even Coquery  École Centrale de Lyon, 36 Avenue Guy de Collongue, 69134
Écully, France  Alain Blanchard  Université de Toulouse, UPS-OMP, IRAP, CNRS,
14 Avenue Edouard Belin, F-31400 Toulouse, France

###### Abstract

Although the existence of dark matter has been widely acknowledged in the
cosmology community, it is as yet unknown in nature, despite decades of
research, which questions its very existence. This never-ending search for
dark matter leads to consider alternatives. Since increasing the enclosed mass
is the only way to explain the flat appearance of galaxies rotation curves in
a Newtonian framework, the MOND theory proposed to modify Newton’s dynamics
when the acceleration is around or below a threshold value, $a_{0}$. Observed
rotation curves, generally flat at large distances, are then usually well
reproduced by MOND with $a_{0}\sim 1.2\times 10^{-10}$ m/s2. However, the
recent Gaia evidence of a decline in the Milky Way rotation curve is a
distinct behavior. Therefore, we examine whether $\Lambda$CDM and MOND can
accommodate the Gaia declining rotation curve of the Milky Way. We first
depict a standard model to describe the Milky Way’s baryonic components.
Secondly, we show that a NFW model is able to fit the decline, assuming a
scale radius $R_{s}$ of the order of $4$ kpc. In a third step, we show that
the usual MOND paradigm is not able to reproduce the declining part for a
standard baryonic model. Finally, we examine whether the MOND theory can
accommodate the declining part of the rotation curve when relaxing the
characteristics of the baryonic components. To do so we use a MCMC method on
the characteristics of the stellar and the HI disk, including their mass. We
found that the stellar disk should be massive, of the order of $10^{11}$ M⊙.
The HI disk mass is capped at nearly 1.8 $10^{11}$ M⊙ but could also be
negligible. Finally, $a_{0}$ is consistent with 0, with an upper limit of
$0.53\times 10^{-10}$ m/s2 (95%), a value much lower than the above mentioned
value usually advocated to explain standard flat rotation curves in MOND
theory.

##  1 Introduction

Studying galaxies rotation curves (RC) is of paramount importance in
cosmology, as they hint towards the existence of dark matter. Indeed,
observations have shown that most galaxies rotation curves are flat, which is
in strong disagreement with Newtonian dynamics’ predictions for known baryonic
components. Historically, cosmologists’ favourite answer to this crisis is to
assume the existence of an invisible mass in order to accommodate the
observations. This assumption is also supported by the observations of
unrelated phenomena, such as gravitational lensing (Refregier, 2003),
cosmological microwave background (Ade et al., 2016), and more. Dark matter,
whose quantity was estimated to be nearly 30% of the Universe mass-energy
content, has now become a pillar of cosmology’s standard model, $\Lambda$CDM.

However, since dark matter has never been observed directly, we could
alternatively envisage that Newtonian dynamics may change under certain
conditions. The MOND111Which stands for MOdified Newtonian Dynamics theory
(Milgrom, 1983) suggests that Newton’s second law is modified under a low
acceleration $a_{0}$. In the deep MOND limit, the rotation velocity for a
circular orbit resumes to $v=(GMa_{0})^{1/4}$, which explains the flat
appearance of most rotation curves. Previous fits of rotations curves using
MOND agree on a value of about $1.2\times 10^{-10}$ m/s2 (Begeman et al.,
1991), an acceleration threshold so low that MONDian effects could not be
detected on Earth nor in the Solar System. This theory has been further
developed, leading to more complex formulations such as AQUAL (Bekenstein &
Milgrom, 1984), QUMOND (Milgrom, 2023), or the relativistic TeVeS (Bekenstein,
2004). However, these theories face tensions in multiple fields, such as
galaxy cluster dynamics (Sanders, 2003), CMB anisotropies, or matter power
spectrum (Dodelson, 2011). To alleviate these tensions, hybrid theories have
been built (see for example Bruneton et al. (2009) or Skordis & Złośnik (2021)
for $\Lambda$CDM cosmology with MONDian effects at galactic scales). Despite
those tensions, MOND remains a strikingly simple theory for reproducing flat
galaxies rotation curves.

Although it is relatively easy to measure other galaxies rotation curves
(Corbelli & Salucci, 2000; Roberts, 1975), probing the Milky Way’s from the
inside is a challenge at high radius. Previous data tend to confirm that the
MW’s RC is flat (Mroz et al., 2019), consistent with expectations in MOND
theory. However, Gaia’s latest data release (Vallenari et al., 2022) sheds
light on a velocity decline after $\approx 15$ kpc, which different analyses
agree on (see for example Wang et al. (2022), Zhou et al. (2023), Jiao et al.
(2023), Robin et al. (2022)). Other galaxies rotation curves were also found
to be declining, and were studied under the MOND paradigm by Zobnina & Zasov
(2020). They conclude that some galaxies rotation curves do not meet with the
usual MOND paradigm, needing a lower value of $a_{0}$, which is in conflict
with values obtained from previous fits of the rotation curves. Studying
Gaia’s newfound decline might yield similar conclusions in the Milky Way.
Milky Way rotation curve measurements before the decline are nonetheless more
scattered, as several papers account for very different values (e.g. Mroz et
al. (2019), Zhou et al. (2023), Labini et al. (2023), Wang et al. (2022),
McGaugh (2018) and Robin et al. (2022)). Such discrepancies lead us to focus
on the declining part of the RC, without considering the inner part.

In this paper, we aim at shedding light on the declining RC’s implications
regarding MOND. We start by building a model for the baryonic components of
the Milky Way, in order to compute the rotation curve at various radii from
the galactic center. In order to compare $\Lambda$CDM with MOND, we implement
this model both under a dark matter paradigm and under Milgrom’s modified
dynamics. We then use this model as a basis to find the optimal value of
$a_{0}$ that fits the decline - if such a value exists. Finally, we compare
MOND results with $\Lambda$CDM, and detail why the MOND paradigm does not
accommodate the Milky Way rotation curve under reasonable assumptions.

##  2 The Milky Way’s rotation curve

###  2.1 Modeling the baryonic components of the Milky Way

In order to compute the rotation curve, we first need to establish a model for
the spatial distributions of the baryonic components of the Milky Way. We
choose to work with the B2 model used in Jiao et al. (2023), and described in
de Salas et al. (2019). This model consists of three components :

  * •

A spherical bulge modelled by a Hernquist potential :

$\Phi(r)=-\frac{GM_{bulge}}{r+r_{b}}$ (1)

  * •

A thin stellar disk,

  * •

Multiple gas disks.

Judging by the values provided by de Salas et al. (2019) and references
therein, we only consider the HI disk, since the other gas masses are
negligible.

Both the stellar disk and the HI disk densities are given by a double-
exponential :

$\rho^{i}(R,z)=\rho_{0}^{i}\exp(-\frac{R}{r_{d}^{i}}-\frac{|z|}{z_{d}^{i}})$
(2)

where $i\in\\{st.,$ HI}.

$\rho_{0}^{i}$ is a normalization constant :

$\left\\{\begin{aligned}
&\rho_{0}^{st.}=\frac{M^{st.}}{4\pi(r_{d}^{st.})^{2}z_{d}^{st.}}\\\
&\rho_{0}^{\text{H{I}}}=\frac{M_{\text{H{I}}}}{4\pi
r_{d}^{\text{H{I}}}z_{d}^{\text{H{I}}}(R_{t}+r_{d}^{\text{H{I}}})e^{-R_{t}/r_{d}^{\text{H{I}}}}}\\\
\end{aligned}\right.$

where $M^{i}$, $M_{bulge}$, $r_{d}^{i}$, $z_{d}^{i}$, $R_{t}$ and $r_{b}$ can
be found in de Salas et al. (2019), and summed up in Table 1.

Table 1: B2 model parameters (de Salas et al., 2019) Parameter | Value (B2 Model)
---|---
$M^{st.}$ (M⊙) | $3.65\times 10^{10}$
$r_{d}^{st.}$ (kpc) | 2.35
$z_{d}^{st.}$ (kpc) | 0.14
$M^{\text{H{I}}}$ (M⊙) | $8.2\times 10^{9}$
$r_{d}^{\text{H{I}}}$ (kpc) | 18.24
$z_{d}^{\text{H{I}}}$ (kpc) | 0.52
$R_{t}$ (kpc) | 2.75
$M_{bulge}$ (M⊙) | $1.55\times 10^{10}$
$r_{b}$ (kpc) | 0.7

###  2.2 Rotation curve under $\Lambda$CDM

In Newtonian dynamics, assuming a circular movement, each mass component
produces an acceleration field that can be written in term of a circular
velocity associated to this component :

$\frac{(v^{i})^{2}}{r}=K_{r}^{i}$ (3)

where $K_{r}^{i}$ is the radial acceleration, and $i$ corresponds to any
baryonic component described above (stellar disk, bulge, gas disk) or to the
added dark matter mass component : $i\in\\{st.,bulge,$ HI$,dm\\}$.

Which means that in order to compute the velocity, we first have to determine
the radial force. We do so by integrating Poisson’s equation with the density
$\rho^{i}$. For the density given in Equation 2, Poisson’s equation can be
solved in terms of Hankel transforms. We can thus find the radial force by
considering the R-derivative. Details of calculation can be found in Kuijken &
Gilmore (1989). We can easily determine $v_{bulge}$ using Equation 3 and the
first derivative of Hernquist’s potential 1.

Finally, we need to specify a dark matter model to compute $v_{dm}$. In
$\Lambda$CDM dark matter potentials are expected to follow a NFW profile
(Navarro et al., 1996a). We will therefore use a standard NFW model (Navarro
et al., 1996b)

$\rho_{NFW}(r)=\frac{\rho_{0,NFW}}{r/R_{s}(1+r/R_{s})^{2}},$ (4)

where $\rho_{0,NFW}$ and the scale radius $R_{s}$ are free parameters. Then we
only need to integrate the density of Equation 4 between $0$ and a given
radius $r$ to get the enclosed mass in the corresponding sphere, and then use
the circular movement assumption to obtain the velocity :

$v_{dm}(r)^{2}=\frac{{GM_{dm}(r)}}{r}.$

The rotation curve under circular movement assumption can now be evaluated :

$v^{2}=v_{st.}^{2}+v_{gas}^{2}+v_{bulge}^{2}+v_{dm}^{2}.$ (5)

Using Equation 5, we can now compute the rotation curve under the $\Lambda$CDM
dark matter paradigm. We provide an example in Figure 1, with parameters
chosen to yield an acceptable fit to the declining part of the rotation curve.
This example shows that NFW is able to explain the declining part, with a
$\chi^{2}$ of 3.3 which is acceptable.

Figure 1: Rotation curve decline example using NFW. $\rho_{0,NFW}=1.8\times
10^{8}$ M⊙/kpc3, $R_{s}=4$ kpc. The parameters for the baryonic components are
those of the

B2 model in Table 1 taken from Jiao et al. (2023).

This yields different results than Jiao et al. (2023). When computing the
dynamical mass using the same critical density value as Jiao et al. (2023)
using the parameters from our fit of the RC under NFW, we get
$M_{dyn}=4.28\times 10^{11}$ M⊙ for a virial radius of 153.5 kpc. These values
are higher than the results from Jiao et al. (2023). However, they remain
consistent with their newfound upper limit on the dynamical mass. In addition,
extrapolation to a distance nearly ten times greater is certainly very
uncertain. We notice however that Lin & Li (2019) infer a determination of the
Wilky Way’s rotation curve up to 100 kpc, consistent with a NFW profile,
similar to the one given in Figure 1.

###  2.3 Rotation velocity under MOND

Using the standard MOND formulation instead of a more rigorous one on a
rotation curve computation, leads to a difference of about 5% (López-
Corredoira & Betancort-Rijo, 2021). For the sake of simplicity, we will thus
stick to Newton’s second law as modified in Milgrom (2015) :

$\mu(a/a_{0})a=K_{r}$ (6)

where $K_{r}$ is the total radial force per unit mass and $\mu$ is a function
chosen such as (McGaugh, 2004) :

$\left\\{\begin{aligned} &\lim_{a>>a_{0}}\mu(a/a_{0})=1\\\
&\lim_{a<<a_{0}}\mu(a/a_{0})=a/a_{0}.\\\ \end{aligned}\right.$

In the following, we choose to work with $\mu(x)=\frac{x}{\sqrt{1+x^{2}}}$, as
it is standard and used by McGaugh (2004)222This choice is not important as we
focus on the asymptotic behavior of the curve.. By only keeping the $a>0$
solution, one can derive the total velocity from Equation 6 :

$v(r)=\left(\frac{r^{2}}{2}\left(K_{r}^{2}+\sqrt{K_{r}^{2}(K_{r}^{2}+4a_{0}^{2})}\right)\right)^{1/4}.$

We then fit the declining part of the rotation curve with this MOND paradigm,
under the baryonic model described above. The value of $a_{0}$ was determined
by minimizing the $\chi^{2}$ considering the Jiao et al. (2023) declining part
of the RC. The best value of $a_{0}$ found here is $2.417\times 10^{-10}$
m/s2, which is not consistent with the value derived from the RC in other
galaxies. The resulting RC is shown Figure 2. As one can see, the fit is not
satisfying, with a $\chi^{2}=49.7$ for fourteen data points and one degree of
freedom. Since this value is not acceptable, we conclude that using the B2
model described as in Jiao et al. (2023), the declining rotation curve cannot
be reproduced with Milgrom dynamics.

Figure 2: Decline fit under the MOND paradigm. $a_{0}=1.321\times 10^{-10}$
m/s2. The parameters for the baryonic components are the same than in Figure
1.

##  3 Relaxing the baryonic components to fit the decline with MOND

###  3.1 Methodology

In the previous section, we have seen that the MOND theory could not
accommodate the declining part of the rotation curve of the Milky Way, when
the baryonic components are those of the B2 model in section 2.1. In this
section we examine whether relaxing the properties of the baryonic components
could alleviate this inconsistency. As the disk mass is the dominant baryonic
component, it is clearly an important parameter in featuring the Milky Way
rotation curve. We thus treat this quantity as a free parameter, as well as
$a_{0}$. For the scale radius, we use two values : $r_{d}=2.35$ kpc (which is
the value measured by Misiriotis et al. (2006) and used by Jiao et al. (2023)
as well as de Salas et al. (2019)), and $r_{d}=3.1$ kpc, which are close to
the bounds provided by Bland-Hawthorn & Gerhard (2016).

To determine our two parameters, the disk mass $M^{st.}$ and $a_{0}$, we ran
two MCMC, one for each scale radius. We apply the MCMC Ensemble Slice Sampler
algorithm from zeus (Karamanis et al., 2021a; Karamanis et al., 2021b).
$M^{st.}$ is allowed to vary between $3\times 10^{10}$ M⊙ and $2\times
10^{11}$ M⊙ and $a_{0}$ between $0$ and $3\times 10^{-10}$ m/s2.

###  3.2 Results

Applying the methodology described above yields constraints on the parameter
space, visualized by the contours in Figure 3. The red cross indicates
standard values of $M^{st.}$ and $a_{0}$ and their uncertainties. The
uncertainty on $M^{st.}$ is representative of the extreme values found in
Binney & Tremaine (2011) and Bland-Hawthorn & Gerhard (2016), whereas the
uncertainty on $a_{0}$ can be found in Milgrom (2015). One can notice that
there is a correlation between the stellar disk mass and $a_{0}$. Moreover,
the value of $r_{d}$ does not have much impact on the results. From these
contours we extract a pair of values $(M^{st.},a_{0})$ presented in Table 2
that minimizes the $\chi^{2}$ : $\chi^{2}=5.56$ for $r_{d}=2.35$ kpc, and
$\chi^{2}=14.2$ for $r_{d}=3.1$ kpc which are acceptable considering we only
have two free parameters. We check that these values allow to fit the decline
in Figure 4 with $\chi^{2}$ slightly higher than with NFW.

Table 2: Central values for $r_{d}=2.35$ kpc and $r_{d}=3.1$ kpc $r_{d}$ (kpc) |  $M^{st.}$ (M⊙) |  $a_{0}$ (m/s2)
---|---|---
$2.35$ | $\left(11.01^{+0.63}_{-0.76}\right)\times 10^{10}$ | $\left(0.65^{+0.12}_{-0.10}\right)\times 10^{-10}$
$3.1$ | $\left(10.95^{+0.62}_{-0.66}\right)\times 10^{10}$ | $\left(0.592^{+0.104}_{-0.092}\right)\times 10^{-10}$
Figure 3: MCMC contours for $r_{d}=2.35$ kpc and $r_{d}=3.1$ kpc. The stellar
disk mass and $a_{0}$ are left as free parameters. The red cross indicates the
observed values of $M^{stellar}$ and $a_{0}$ with their respective uncertainty
(see text). Figure 4: Fits using MCMC results. All of the other parameters are
the same as in Figure 2.

As the red cross indicates, the obtained value of $a_{0}$ is smaller than the
standard $1.2\times 10^{-10}$ m/s2 and is not consistent with previous
results, namely from Begeman et al. (1991). In other words, according to our
study, there is no way for MOND to explain both the Milky Way rotation curve
and other galaxies rotation curves with the same value of $a_{0}$.

Moreover, the stellar disk mass used to find such a value is about $10\times
10^{10}$ solar masses, which is not consistent with the value $(3.5\pm
1)\times 10^{10}$ M⊙ from Bland-Hawthorn & Gerhard (2016).

###  3.3 More freedom on the baryonic components.

Figure 5: MCMC contours with a free stellar disk mass, free HI disk mass, free
$a_{0}$, free scale radius and free scale height.

Since relieving constraints on the stellar disk mass alone does not yield
satisfying results, in this section we explore possibilities by increasing the
number of free parameters on the baryonic components. We launch another MCMC
with $M^{st.}$, $a_{0}$, $M^{\text{H{I}}}$, $r_{d}$ and $z_{d}$ as free
parameters. Each prior used for this MCMC can be found in Table 3.

Figure 5 reveals a number of interesting properties that can be inferred : it
is possible to fit adequately the rotation curve with the baryonic components
provided that they are allowed to take values well above the standard values :
for the models taken in the 1$\sigma$ domain, the $\chi^{2}$ typically lies
between 3 and 6 which is acceptable and similar to the $\Lambda$CDM case. The
scale height of the disk has no correlation with other parameters (except a
weak correlation with the disk mass) and has no preferred value. The HI disk
mass $M^{\text{H{I}}}$ has little to no impact on the results, as a wide range
of values allows to fit the decline. Large values of the HI disk mass are
allowed, much above the standard value, but remaining below the preferred
stellar disk mass. The 1$\sigma$ intervals for the scale radius of the stellar
disk and for its mass are higher than found in Bland-Hawthorn & Gerhard (2016)
and show a correlation with the stellar disk mass. Relieving the constraints
on the baryonic matter distribution yields a lower value for $a_{0}$ than
found in the previous MCMC analysis, and $a_{0}$ does not appear to be
correlated with the baryonic distribution parameters. One can notice that
$a_{0}=0$ m/s2 is in the $1\sigma$ interval, assuming a heavy stellar disk and
a scale radius $r_{d}>3$ kpc. The fact that the stellar disk is heavier than
usual observations (Bland-Hawthorn & Gerhard, 2016) can be explained by the
close-to-zero value of $a_{0}$ : since little to no MONDian effect is
requested and no dark halo is assumed, one needs extra matter in the disk to
reach an acceptable value of the circular velocity. Essentially, this consists
in a dark matter disk instead of the halo used in Figure 1, while models using
a lighter disk and a non vanishing $a_{0}$ are not significantly preferred
over the $a_{0}=0$ paradigm.

Table 3: Prior used for the MCMC Figure 5. Parameter | Lower bound | Higher bound
---|---|---
$M^{st.}$ (M⊙) | $3\times 10^{10}$ | $2\times 10^{11}$
$a_{0}$ (m/s2) | 0 | $3\times 10^{-8}$
$M^{gas}$ (M⊙) | 0 | $3\times 10^{11}$
$r_{d}$ (kpc) | 0 | 20
$z_{d}$ (kpc) | 0 | 2

##  4 Discussion and conclusion

In this work, we examine the two major solutions to the missing mass problem
in galaxies, applied to the Milky Way. More precisely, we compare the ability
of $\Lambda$CDM (dark matter) and MOND (modified dynamics) to fit the Milky
Way declining rotation curve measured by Gaia. Using a standard model for the
baryonic components of the Milky Way we show that a simple dark matter
distribution model like NFW, expected in $\Lambda$CDM, is able to explain
Gaia’s decline with ease, whereas the MOND formulation cannot accommodate the
decline under the B2 model, even when allowing $a_{0}$ to be a free parameter.
We then consider relieving constraints on baryonic parameters as well as the
value of $a_{0}$ in order to examine whether MOND could accommodate the
decline. For this we perform an MCMC on $a_{0}$ and the parameters of the
baryonic components on the data of the declining part of the Milky Way
rotation curve. Preferred models have disk masses at odds with values inferred
from observations, with no significant preference for a non vanishing $a_{0}$.
We get an upper limit on $a_{0}$ of $0.53\times 10^{-10}$ m/s-2 (95%),
significantly lower than what has been found necessary to fit flat rotation
curves in other galaxies with MOND, nearly 5 $\sigma$ away.

We conclude that the declining rotation curve of the Milky Way as recently
inferred from Gaia’s data favors an NFW halo of dark matter as expected in
$\Lambda$CDM over the MOND alternative.

###### Acknowledgements.

## References

  * Ade et al. (2016) Ade P. A. R., et al., 2016, Astronomy & Astrophysics, 594, A13
  * Begeman et al. (1991) Begeman K. G., Broeils A. H., Sanders R. H., 1991, Monthly Notices of the Royal Astronomical Society, 249, 523
  * Bekenstein (2004) Bekenstein J. D., 2004, Phys. Rev. D, 70, 083509
  * Bekenstein & Milgrom (1984) Bekenstein J., Milgrom M., 1984, ApJ, 286, 7
  * Binney & Tremaine (2011) Binney J., Tremaine S., 2011, Galactic Dynamics Second Edition. Princeton University Press
  * Bland-Hawthorn & Gerhard (2016) Bland-Hawthorn J., Gerhard O., 2016, Annual Review of Astronomy and Astrophysics, 54, 529
  * Bruneton et al. (2009) Bruneton J.-P., Liberati S., Sindoni L., Famaey B., 2009, Journal of Cosmology and Astroparticle Physics, 2009, 021–021
  * Corbelli & Salucci (2000) Corbelli E., Salucci P., 2000, Monthly Notices of the Royal Astronomical Society, 311, 441–447
  * Dodelson (2011) Dodelson S., 2011, International Journal of Modern Physics D, 20, 2749–2753
  * Jiao et al. (2023) Jiao Y., Hammer F., Wang H., Wang J., Amram P., Chemin L., Yang Y., 2023, Astronomy & Astrophysics, 678, A208
  * Karamanis et al. (2021a) Karamanis M., Beutler F., Peacock J. A., 2021a, arXiv preprint arXiv:2105.03468
  * Karamanis et al. (2021b) Karamanis M., Beutler F., Peacock J. A., 2021b, MNRAS, 508, 3589
  * Kuijken & Gilmore (1989) Kuijken K., Gilmore G., 1989, Monthly Notices of the Royal Astronomical Society, 239, 571
  * Labini et al. (2023) Labini F. S., Chrobáková v., Capuzzo-Dolcetta R., López-Corredoira M., 2023, The Astrophysical Journal, 945, 3
  * Lin & Li (2019) Lin H.-N., Li X., 2019, MNRAS, 487, 5679
  * López-Corredoira & Betancort-Rijo (2021) López-Corredoira M., Betancort-Rijo J. E., 2021, The Astrophysical Journal, 909, 137
  * McGaugh (2004) McGaugh S. S., 2004, The Astrophysical Journal, 609, 652
  * McGaugh (2018) McGaugh S. S., 2018, Research Notes of the AAS, 2, 156
  * Milgrom (1983) Milgrom M., 1983, ApJ, 270, 365
  * Milgrom (2015) Milgrom M., 2015, Canadian Journal of Physics, 93, 107
  * Milgrom (2023) Milgrom M., 2023, Physical Review D, 108, 084005
  * Misiriotis et al. (2006) Misiriotis A., Xilouris E. M., Papamastorakis J., Boumis P., Goudis C. D., 2006, Astronomy & Astrophysics, 459, 113
  * Mroz et al. (2019) Mroz P., et al., 2019, The Astrophysical Journal Letters, 870, L10
  * Navarro et al. (1996b) Navarro J. F., Frenk C. S., White S. D. M., 1996b, The Astrophysical Journal, 462, 563
  * Navarro et al. (1996a) Navarro J. F., Frenk C. S., White S. D. M., 1996a, ApJ, 462, 563
  * Refregier (2003) Refregier A., 2003, Annual Review of Astronomy and Astrophysics, 41, 645–668
  * Roberts (1975) Roberts M. S., 1975, in Hayli A., ed., Vol. 69, Dynamics of the Solar Systems. p. 331
  * Robin et al. (2022) Robin A. C., et al., 2022, Astronomy & Astrophysics, 667, A98
  * Sanders (2003) Sanders R. H., 2003, Monthly Notices of the Royal Astronomical Society, 342, 901–908
  * Skordis & Złośnik (2021) Skordis C., Złośnik T., 2021, Physical Review Letters, 127
  * Vallenari et al. (2022) Vallenari A., Brown A., Prusti T., 2022, Astronomy & Astrophysics, 674
  * Wang et al. (2022) Wang H.-F., Chrobáková Ž., López-Corredoira M., Labini F. S., 2022, The Astrophysical journal, 942, 12
  * Zhou et al. (2023) Zhou Y., Li X., Huang Y., Zhang H., 2023, The Astrophysical journal, 946, 73
  * Zobnina & Zasov (2020) Zobnina D. I., Zasov A. V., 2020, Astronomy Reports, 64, 295–309
  * de Salas et al. (2019) de Salas P. F., Malhan K., Freese K., Hattori K., Valluri M., 2019, Journal of Cosmology and Astroparticle Physics, 2019, 037


* [8] Braverman A., Kazhdan D., Some examples of Hecke algebras for two-dimensional local fields, Nagoya Math. J. 184 (2006), 57–84, arXiv:math.RT/0510538.
  * [9] Braverman A., Kazhdan D., The spherical Hecke algebra for affine Kac–Moody groups I, Ann. of Math. 174 (2011), 1603–1642, arXiv:0809.1461.
  * [10] Casselman W., Cely J.E., Hales T., The spherical Hecke algebra, partition functions, and motivic integration, Trans. Amer. Math. Soc. 371 (2019), 6169–6212, arXiv:1611.05773.
  * [11] Cluckers R., Loeser F., Constructible motivic functions and motivic integration, Invent. Math. 173 (2008), 23–121, arXiv:math.AG/0410203.
  * [12] Drinfeld V.G., Langlands’ conjecture for ${\rm GL}(2)$ over functional fields, in Proceedings of the International Congress of Mathematicians (Helsinki, 1978), Acad. Sci. Fennica, Helsinki, 1980, 565–574.
  * [13] Drinfeld V.G., Two-dimensional $l$-adic representations of the fundamental group of a curve over a finite field and automorphic forms on ${\rm GL}(2)$, Amer. J. Math. 105 (1983), 85–114.
  * [14] Drinfeld V.G., Moduli varieties of $F$-sheaves, Funct. Anal. Appl. 21 (1987), 107–122.
  * [15] Drinfeld V.G., The proof of Petersson’s conjecture for ${\rm GL}(2)$ over a global field of characteristic $p$, Funct. Anal. Appl. 22 (1988), 28–43.
  * [16] Etingof P., Frenkel E., Kazhdan D., An analytic version of the Langlands correspondence for complex curves, arXiv:1908.09677.
  * [17] Etingof P., Frenkel E., Kazhdan D., Hecke operators for curves over local fields, in preparation.
  * [18] Feigin B., Frenkel E., Affine Kac–Moody algebras at the critical level and Gelfand–Dikii algebras, Internat. J. Modern Phys. A 7 (1992), suppl. 1A, 197–215.
  * [19] Fesenko I., Analysis on arithmetic schemes. I, 2003, extra vol., 261–284.
  * [20] Fesenko I., Measure, integration and elements of harmonic analysis on generalized loop spaces, in Proceedings of the St. Petersburg Mathematical Society, Vol. XII, Amer. Math. Soc. Transl. Ser. 2, Vol. 219, Amer. Math. Soc., Providence, RI, 2006, 149–165.
  * [21] Frenkel E., Wakimoto modules, opers and the center at the critical level, Adv. Math. 195 (2005), 297–404, arXiv:math.QA/0210029.
  * [22] Frenkel E., Langlands correspondence for loop groups, Cambridge Studies in Advanced Mathematics, Vol. 103, Cambridge University Press, Cambridge, 2007\.
  * [23] Frenkel E., Lectures on the Langlands program and conformal field theory, in Frontiers in Number Theory, Physics, and Geometry. II, Springer, Berlin, 2007, 387–533, arXiv:hep-th/0512172.
  * [24] Frenkel E., Gauge theory and Langlands duality, Talk given at MSRI, Berkeley, September 2014, available at https://youtu.be/NQfeBeRKMiw?t=4190.
  * [25] Frenkel E., Gaitsgory D., Vilonen K., On the geometric Langlands conjecture, J. Amer. Math. Soc. 15 (2002), 367–417, arXiv:math.AG/0012255.
  * [26] Gaitsgory D., On a vanishing conjecture appearing in the geometric Langlands correspondence, Ann. of Math. 160 (2004), 617–682, arXiv:math.AG/0204081.
  * [27] Gaitsgory D., Outline of the proof of the geometric Langlands conjecture for ${\rm GL}_{2}$, Astérisque 370 (2015), 1–112, arXiv:1302.2506.
  * [28] Gaitsgory D., Progrès récents dans la théorie de Langlands géométrique, Astérisque 390 (2017), exp. no. 1109, 139–168, arXiv:1606.09462.
  * [29] Gawȩdzki K., Lectures on conformal field theory, in Quantum Fields and Strings: a Course for Mathematicians, Vols. 1, 2 (Princeton, NJ, 1996/1997), Amer. Math. Soc., Providence, RI, 1999, 727–805.
  * [30] Ginzburg V., Perverse sheaves on a loop group and Langlands duality, arXiv:alg-geom/9511007.
  * [31] Goldman W.M., Projective structures with Fuchsian holonomy, J. Differential Geom. 25 (1987), 297–326.
  * [32] Gordon J., Motivic Haar measure on reductive groups, Canad. J. Math. 58 (2006), 93–114, arXiv:math.AG/0203106.
  * [33] Griffiths P., Harris J., Principles of algebraic geometry, Pure and Applied Mathematics, Wiley-Interscience, New York, 1978.
  * [34] Hrushovski E., Kazhdan D., Integration in valued fields, in Algebraic geometry and number theory, Progr. Math., Vol. 253, Birkhäuser Boston, Boston, MA, 2006, 261–405, arXiv:math.AG/0510133.
  * [35] Hrushovski E., Kazhdan D., The value ring of geometric motivic integration, and the Iwahori Hecke algebra of ${\rm SL}_{2}$, Geom. Funct. Anal. 17 (2008), 1924–1967, arXiv:math.AG/0609115.
  * [36] Kapranov M., Double affine Hecke algebras and 2-dimensional local fields, J. Amer. Math. Soc. 14 (2001), 239–262, arXiv:math.AG/9812021.
  * [37] Kim H.H., Lee K.H., Spherical Hecke algebras of $\rm{\rm SL}_{2}$ over 2-dimensional local fields, Amer. J. Math. 126 (2004), 1381–1399.
  * [38] Knapp A.W., Vogan Jr. D.A., Cohomological induction and unitary representations, Princeton Mathematical Series, Vol. 45, Princeton University Press, Princeton, NJ, 1995.
  * [39] Kontsevich M., Notes on motives in finite characteristic, in Algebra, Arithmetic, and Geometry: in Honor of Yu.I. Manin, Vol. II, Progr. Math., Vol. 270, Birkhäuser Boston, Boston, MA, 2009, 213–247, arXiv:math.AG/0702206.
  * [40] Lafforgue L., Chtoucas de Drinfeld et correspondance de Langlands, Invent. Math. 147 (2002), 1–241.
  * [41] Langlands R.P., Problems in the theory of automorphic forms, in Lectures in Modern Analysis and Applications, III, Lecture Notes in Math., Vol. 170, Springer, Berlin, 1970, 18–61.
  * [42] Langlands R.P., On the analytical form of the geometric theory of automorphic forms, in Russian, available at http://publications.ias.edu/rpl/paper/2678.
  * [43] Laumon G., Correspondance de Langlands géométrique pour les corps de fonctions, Duke Math. J. 54 (1987), 309–359.
  * [44] Laumon G., Transformation de Fourier, constantes d’équations fonctionnelles et conjecture de Weil, Inst. Hautes Études Sci. Publ. Math. 65 (1987), 131–210.
  * [45] Lorscheid O., Automorphic forms for elliptic function fields, Math. Z. 272 (2012), 885–911, arXiv:1012.4825.
  * [46] Lusztig G., Singularities, character formulas, and a $q$-analog of weight multiplicities, Astérisque 101 (1983), 208–229.
  * [47] Mirković I., Vilonen K., Geometric Langlands duality and representations of algebraic groups over commutative rings, Ann. of Math. 166 (2007), 95–143, arXiv:math.RT/0401222.
  * [48] Morrow M., Integration on product spaces and ${\rm GL}_{n}$ of a valuation field over a local field, Commun. Number Theory Phys. 2 (2008), 563–592, arXiv:0712.2175.
  * [49] Morrow M., Integration on valuation fields over local fields, Tokyo J. Math. 33 (2010), 235–281, arXiv:0712.2172.
  * [50] Teschner J., Quantisation conditions of the quantum Hitchin system and the real geometric Langlands correspondence, arXiv:1707.07873.
  * [51] Waller R., Private communication, November 2018.
  * [52] Waller R., Measure and integration on non-locally compact spaces and representation theory, Ph.D. Thesis, University of Nottingham, 2019.
  * [53] Weil A., A 1940 letter of André Weil on analogy in mathematics (translated by Martin H. Krieger), Notices Amer. Math. Soc. 52 (2005), 334–341.