# Distributed Deterministic Exact Minimum Weight Cycle and Multi Source
Shortest Paths in Near Linear Rounds in CONGEST model

Udit Agarwal

###### Abstract

We present new deterministic algorithms for computing distributed weighted
minimum weight cycle (MWC) in undirected and directed graphs and distributed
weighted all nodes shortest cycle (ANSC) in directed graphs. Our algorithms
for these problems run in $\tilde{O}(n)$ rounds in the CONGEST model on graphs
with arbitrary non-negative edge weights, matching the lower bound up to
polylogarithmic factors. Before our work, no near linear rounds deterministic
algorithms were known for these problems. The previous best bound for solving
these problems deterministically requires an initial computation of all pairs
shortest paths (APSP) on the given graph, followed by post-processing of
$O(n)$ rounds, and in total takes $\tilde{O}(n^{4/3})$ rounds, using
deterministic APSP [3].

The main component of our new $\tilde{O}(n)$ rounds algorithms is a
deterministic technique for constructing a sequence of successive blocker
sets. These blocker sets are then treated as source nodes to compute $h$-hop
shortest paths, which can then be used to compute candidate shortest cycles
whose hop length lies in a particular range. The shortest cycles can then be
obtained by selecting the cycle with the minimum weight from all these
candidate cycles.

Additionally using the above blocker set sequence technique, we also obtain
$\tilde{O}(n)$ rounds deterministic algorithm for the multi-source shortest
paths problem (MSSP) for both directed and undirected graphs, given that the
size of the source set is at most $\sqrt{n}$. This new result for MSSP can be
a step towards obtaining a $o(n^{4/3})$ rounds algorithm for deterministic
APSP. We also believe that our new blocker set sequence technique may have
potential applications for other distributed algorithms.

##  1 Introduction

###  1.1 Background and Motivation

Finding the minimum weight cycle (MWC) in a graph is one of the fundamental
problems in the area of graph algorithms and has received a huge amount of
attention for the past several decades in the context of centralized
algorithms (e.g., [8, 10, 13, 15, 16, 17, 19, 21, 22, 23]). The related
problem of finding the shortest cycles for each node in a graph, known as All
Nodes Shortest Cycle (ANSC), is relatively less-studied and has only gained
attention in the past decade [1, 9, 24, 25].

In this work, we study the computation of MWC in the CONGEST model of
distributed computing. In the CONGEST model, the input is a directed (or
undirected) graph $G=(V,E)$, and the distributed computation occurs at the
nodes in this graph. The output of MWC problem is to compute the weight of the
minimum weight cycle in the graph $G$. We assume an arbitrary non-negative
edge weight on each edge. In this paper, we consider the computation of the
exact shortest cycles and paths in the graph.

###  1.2 Our Results

Table 1 lists the comparison of our new results with the earlier known
deterministic results for the shortest cycle problems, including MWC and ANSC,
and the multi-source shortest paths (MSSP) problem. We now explain our results
in more detail.

Table 1: Table comparing our new results with previous known deterministic results. Problem | Previous Bound | This Paper
---|---|---
Undirected/ |  |
Directed MWC |  $\tilde{O}(n^{4/3})$ [3] | $\bm{\tilde{O}(n)}$
Directed ANSC |  $\tilde{O}(n^{4/3})$ [3] | $\bm{\tilde{O}(n)}$
Undirected/ |  |
Directed MSSP |  $\tilde{O}(\min\\{n^{4/3},n\cdot|S|\\})$ [3, 5] | $\bm{\tilde{O}(n)}$

####  1.2.1 Directed Shortest Cycles

In a directed graph, the problem of computing the shortest cycle at a node $v$
involves finding the cycle with minimum weight among all cycles that contain
node $v$. The ANSC problem deals with finding the shortest cycle for each node
$v$ in the graph, whereas MWC deals with finding the global shortest cycle in
the graph. The current known approach for computing shortest cycles involves
first computing APSP and then for each node $v$, taking the minimum across all
possible values $\\{w(v,u)+\delta(u,v)\\}$ where $u$ is an outgoing neighbor
of $v$. This gives the value of the shortest cycle containing node $v$. (Here
$\delta(u,v)$ refers to the weight of the shortest path from node $u$ to $v$)
This approach takes $O(APSP+n)$ rounds in total and is also used in Manoharan
and Ramachandran [18] to obtain randomized algorithms for shortest cycle
problems. Since the current best bound for computing deterministic APSP is
$\tilde{O}(n^{4/3})$ [3], this approach for computing shortest cycles requires
$\tilde{O}(n^{4/3})$ rounds in total.

In Section 1.3, we give a brief overview of our new framework that involves
computing a sequence of blocker sets, which then allows us to compute shortest
cycles, without requiring an initial computation of APSP. This, in effect,
allows us to obtain $\tilde{O}(n)$ rounds algorithms for the shortest cycle
problems.

####  1.2.2 Undirected Shortest Cycles

The problem of computing shortest cycles in undirected graphs is known to be
much harder as compared to the directed setting. This has also been noted in
an earlier work on MWC by Roditty and Williams [22]. The reason behind this is
that the reduction from the Shortest Cycle problems to APSP no longer works in
the undirected setting: an edge $(v,u)$ might also be the shortest path from
$u$ to $v$, and $\min_{u}\\{w(v,u)+\delta(u,v)\\}$ might be $2\cdot w(v,u)$
and not the weight of the shortest cycle containing node $v$.

Instead in undirected graphs, the value of the minimum weight cycle can be
obtained by taking the minimum across all possible values
$\\{w(v,u)+\delta(u,w)+\delta(v,w)\\}$ where $u\in\mathcal{N}(v)$ and $w\in
V$. This requires an initial computation of APSP and $O(n)$ additional rounds
for each node $v$ to communicate distance values $\delta(v,w)$, where $w\in
V$, to all its neighbor nodes, thus taking $O(APSP+n)$ rounds in total. Since
the current deterministic bound for APSP is $\tilde{O}(n^{4/3})$ [3], this
approach will also require $\tilde{O}(n^{4/3})$ for computing deterministic
MWC. We give a brief overview of our framework in Section 1.3 and a detailed
description of our $\tilde{O}(n)$ deterministic algorithm for computing
undirected MWC in Section 5.

Our result provides a temporary polynomial gap between the current
deterministic complexity of APSP and MWC computation in both directed and
undirected graphs. All previously known deterministic results for these
problems exhibit the same round complexity of $\tilde{O}(n^{4/3})$ [3].

####  1.2.3 Multi Source Shortest Paths (MSSP).

The problem of computing MSSP involves computing shortest path distances from
all source nodes in a given source set $S$ to every node $v$ in the graph. The
current approach to compute MSSP involves either computing APSP or running
SSSP using Bellman-Ford algorithm [5] for every node in the source set $S$.
This results in the total round bound of
$\tilde{O}(\min\\{n^{4/3},n\cdot|S|\\})$. In Section 6, we describe our
$\tilde{O}(n)$ rounds deterministic algorithm for computing MSSP, when there
are at most $\sqrt{n}$ source nodes. Note that our algorithm works for both
directed and undirected graphs.

###  1.3 Our Framework for Computing Shortest Cycles

Our $\tilde{O}(n)$ deterministic algorithms for computing shortest cycles
follows the following framework for a given graph $G$ (directed or
undirected):

  1. 1.

Compute a series of blocker sets $Q_{i}$, for $1\leq i\leq\lceil\frac{\log
n}{\log\log n}\rceil-1$, for $h_{i}$ hops, with source set $Q_{i-1}$, such
that $Q_{i}$ intersects all exact shortest paths from source set $Q_{i-1}$
with hop-length $h_{i-1}$. Here $Q_{0}=V$, $h_{0}=\log^{2}n$ and
$h_{i}=h_{i-1}\cdot\log n$.

  2. 2.

For each $i$, $1\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$, compute
$h_{i}$-hop incoming shortest paths and $h_{i}$-hop outgoing shortest paths
for source set $Q_{i}$.

  3. 3.

Determine the weight of the shortest cycles using the values computed in Step
(2).

We now outline the ideas, followed by an informal description of each of the
steps in our above framework for computing shortest cycles.

####  1.3.1 Deterministic Algorithm for Computing a Sequence of Blocker Sets
(Step 1).

For a given source set $S$ and hop-length $h$, Agarwal and Ramachandran [3]
gave a deterministic algorithm that computes a blocker set $Q$ for $S$ in
$\tilde{O}(|S|\cdot h)$ rounds. Their algorithm involves framing the
computation of a small blocker set as an approximate set cover problem on a
related hypergraph, and then adapting the efficient NC algorithm in Berger,
Rompel and Shor [6] for computing an approximate minimum set cover problem in
a hypergraph to an $\tilde{O}(|S|\cdot h)$ rounds randomized algorithm for
computing the blocker set. They then derandomize this algorithm to obtain an
overall $\tilde{O}(|S|\cdot h)$ deterministic algorithm.

Our new contribution is to construct a sequence of blocker sets $Q_{i}$, for
$1\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$, such that nodes in
$Q_{i}$ intersect all exact shortest paths from source nodes in $Q_{i-1}$ with
hop-length $h_{i-1}$. We use the deterministic blocker set algorithm in
Agarwal and Ramachandran [3] to compute these individual $Q_{i}$’s. We
describe this step in more detail in Section 3 where we also establish
additional properties that such a sequence of blocker sets guarantees, which
then allows us to obtain our deterministic algorithms for computing shortest
cycles.

####  1.3.2 Computing Small-hop Shortest Paths from Blocker Sets $Q_{i}$ (Step
2).

After computing the sequence of blocker sets $Q_{i}$, for $1\leq
i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$, in Step (1), In Step (2) we
compute the $h_{i}$-hop outgoing and $h_{i}$-hop incoming shortest paths from
source nodes in sets $Q_{i}$. This takes $O(\sum_{i=0}^{\lceil\frac{\log
n}{\log\log n}\rceil-1}|Q_{i}|\cdot h_{i+1})$ rounds in total using the
Bellman-Ford algorithm [5]. We describe this further in Section 2.

####  1.3.3 Computing the weight of Shortest Cycles (Step 3).

Shortest cycles in both directed and undirected graphs exhibit the following
property: they are composed of one or more shortest paths. In directed graphs,
the shortest cycle containing node $v$ consists of an outgoing edge $(v,u)$,
followed by the shortest path from $u$ to $v$. Similarly, in undirected
graphs, the shortest cycle for node $v$ consists of a shortest path from $v$
to some node $u$, followed by an edge $(u,w)$, and then a shortest path from
$w$ to node $v$. We exploit this property of the shortest cycles, along with
the small-hops shortest path values obtained in Step 2, to obtain the weight
of the shortest cycles in both directed and undirected graphs. We describe
this in more detail in Sections 4 and Section 5.

###  1.4 Related Work

####  1.4.1 Deterministic Shortest Paths in CONGEST model.

The classical Bellman-Ford algorithm [5] is still the current best approach
for deterministically computing the single-source version of shortest paths
(SSSP), even if the diameter of the graph is sublinear in the number of nodes
and has the round complexity of $O(n)$.

For the all-pairs version (APSP), the first non-trivial deterministic
algorithm for this problem was proposed by Agarwal et al. [4] and had the
round bound complexity of $\tilde{O}(n^{3/2})$. This result was later improved
by Agarwal and Ramachandran [3], with a total round complexity of
$\tilde{O}(n^{4/3})$.

####  1.4.2 Randomized Shortest Cycles in CONGEST model.

A trivial approach to computing shortest cycles is to first compute APSP on
the graph and then use the distance values to compute the weight of the
shortest cycles. Such an approach has been used in Manoharan and Ramachandran
[18], where the authors use the randomized $\tilde{O}(n)$ rounds APSP
algorithm of Bernstein and Nanongkai [7] to obtain randomized algorithms for
shortest cycle problems.

One can argue whether it is possible to use such an approach to obtain
$\tilde{O}(n)$ rounds deterministic algorithms for computing shortest cycles.
However, such an approach would require first using deterministic APSP to
compute the distance values, which are required to obtain the shortest cycles
algorithms in [18]. Since the current best bound for deterministic APSP is
$\tilde{O}(n^{4/3})$ [3], such an approach would require at least
$\tilde{O}(n^{4/3})$ rounds.

###  1.5 Organization of the Paper

In Section 2 we give an overview of the well-known CONGEST model and the
Bellman-Ford algorithm for computing small hop shortest paths. We describe our
deterministic algorithm for computing a sequence of successive blocker sets in
Section 3. In Section 4, we describe our $\tilde{O}(n)$ deterministic
algorithm for computing minimum weight cycle in directed graphs, and in
Section 5 we describe our $\tilde{O}(n)$ deterministic algorithm for computing
minimum weight cycle in undirected graphs. Finally in Section 6, we describe
our $\tilde{O}(n)$ rounds deterministic algorithm for computing multi-source
shortest paths.

##  2 Preliminaries

###  2.1 CONGEST model

We now describe the well-known CONGEST model for distributed computation. In
this model, $n$ independent processors are interconnected in a network by
bounded-bandwidth links. We refer to these processors as nodes and the links
as edges. This network is modeled by a graph $G=(V,E)$ where $V$ refer to the
set of processors and $E$ refer to the set of links between the processors.
The model also assumes that the system is fault-free, i.e. nodes do not crash
or behave badly and messages are not lost, delayed, or corrupted.

The processors (or nodes) are assumed to have unique IDs in the range of
$\\{1,\ldots,poly(n)\\}$ and have infinite computational power available on
each node. Each node has limited topological knowledge and only knows about
its incident edges. Each edge has an arbitrary real non-negative edge weight.
The communication network of $G$ is represented by the underlying undirected
graph $U_{G}$ of $G$. The communication channels across all edges are
bidirectional, even if the edges are directed. Note that the model allows a
node to send different messages along different edges.

The computation in this model proceeds in synchronous rounds. In each round,
each node $v\in V$ can send a constant number of words along each outgoing
edge, and it receives the messages sent to it in the previous round. The
CONGEST model normally assumes that a word has $O(\log n)$ bits. Since we
allow arbitrary edge-weights, here we assume that a constant number of node-
ids, edge-weights, and distance values can be sent along every edge in every
round (similar assumptions are made in [3, 4, 7, 11]). After receiving the
messages, every node performs some local computation. We measure the
performance of algorithms in terms of their round complexity, defined as the
worst-case number of rounds of distributed communication.

###  2.2 Notations

Let $G=(V,E)$ be a directed or undirected graph with arbitrary non-negative
weights: $V$ is the set of nodes, and $E$ is the set of edges, such that
$|V|=n$ and $|E|=m$. Let $\mathcal{N}_{out}(v)$ refer to the set of out
neighbors of node $v$ and let $\mathcal{N}_{in}(v)$ refer to the set of in
neighbors of node $v$. In undirected graphs, we simply denote the neighbors of
node $v$ with $\mathcal{N}(v)$, since edges are not directed.

Let $w(u,v)$ denote the weight of the edge $(u,v)$ and let $\delta(s,t)$ refer
to the weight of the shortest path from node $s\in V$ to $t\in V$. For a given
hop-length $h$, the value $\delta^{h}(s,t)$ refer to the weight of the
shortest path from $s$ to $t$ among all such paths from $s$ to $t$, that has
at most $h$ hops. Let $\delta(v)$ denote the weight of the shortest cycle
containing node $v$ and let $\delta^{h}(v)$ denote the weight of the shortest
cycle containing node $v$, that has at most $h$ hops. Let $wt(\mathcal{P})$
refer to the weight of a path $\mathcal{P}$ and let $wt(\mathcal{C})$ refer to
the weight of a cycle $\mathcal{C}$.

Let $parent(s,t)$ refer to the parent of node $t$ on the computed shortest
path between nodes $s$ and $t$ and let $parent^{h}(s,t)$ refer to the parent
of node $t$ on the computed $h$-hop shortest path between nodes $s$ and $t$.
Similarly let $next(s,t)$ refer to the node next to $s$, which lies on the
computed shortest path between nodes $s$ and $t$ and let $next^{h}(s,t)$ refer
to the node next to $s$, which lies on the computed $h$-hop shortest path
between nodes $s$ and $t$.

###  2.3 Small Hops Shortest Paths

We now define the notion of $h$-hops shortest paths and show how traditional
Bellman-Ford algorithm [5] is used to compute these $h$-hops shortest paths.
We start with defining the notion of $h$-hop-accurate shortest path distances
defined in [7].

######  Definition 2.1 ($h$-hop accurate [7]).

For an integer $h$ and a source node $s\in V$ and a target node $t\in V$, a
distance value $\delta^{h}(s,t)$ is $h$-hop accurate if the following holds:
(1) $\delta^{h}(s,t)\geq\delta(s,t)$ and, (2) if there is a shortest path from
$s$ to $t$ of hop-length $\leq h$, then $\delta^{h}(s,t)=\delta(s,t)$.

####  2.3.1 Bellman Ford Algorithm.

We now show how the Bellman-Ford algorithm computes these $h$-hop accurate
shortest path distance values from a given source node $s$. The algorithm runs
for $h$ rounds, where $h$ is an input given by the user. Here is a brief
description of the algorithm.

Algorithm 1 Computing $h$-hop outgoing shortest path distances using Bellman-
Ford algorithm [5]

1:Input: $G=(V,E)$; source : $s$; number of hops: $h$

2:For $\bm{0\leq i\leq h}$: Initialize $D^{i}(s,t)=\infty$ for $t\neq s$; Set
$D^{i}(s,s)=0$.

3:For $\bm{0\leq i\leq h}$: Initialize $parent^{h}(s,t)\leftarrow t$ for
$t\neq s$; Set $parent^{h}(s,s)\leftarrow s$

4:Round $\bm{i}$: ($0\leq i\leq h-1$)

5: Every node $v$ sends the computed distance value $D^{i}(s,v)$ to all its
outgoing neighbors.

6: $\begin{aligned} &\text{Using the values received in
Step~{}\ref{algBF:send}, node $v$ computes the distance value}\\\
&\text{$D^{i+1}(s,v)\leftarrow\min_{u\in\mathcal{N}_{in}(v)}\\{D^{i}(s,u)+w(u,v)\\}$.}\end{aligned}$

7: if $D^{i+1}(s,v)\neq D^{i}(s,v)$ then: set
$parent^{h}(s,v)\leftarrow\arg\min_{u\in\mathcal{N}_{in}(v)}\\{D^{i}(s,u)+w(u,v)\\}$

Clearly, Algorithm 1 takes $O(h)$ rounds. Moreover, it can be proved that when
the algorithm terminates the computed $h$-hop shortest path distance values,
$D^{h}(s,v)$, is equal to $\delta^{h}(s,v)$, and is $h$-hop-accurate for every
node $v\in V$. Note that we can modify the above algorithm if we instead want
to compute $h$-hop incoming shortest path distance values $\delta^{h}(v,s)$ at
each node $v\in V$. We describe this modified algorithm in Algorithm 2, that
computes $\delta^{h}(v,s)$ distance values at each node $v\in V$, and also
takes $O(h)$ rounds.

Algorithm 2 Computing $h$-hop incoming shortest path distances using Bellman-
Ford algorithm [5]

1:Input: $G=(V,E)$; source : $s$; number of hops: $h$

2:For $\bm{0\leq i\leq h}$: Initialize $D^{i}(t,s)=\infty$ for $t\neq s$; Set
$D^{i}(s,s)=0$.

3:For $\bm{0\leq i\leq h}$: Initialize $next^{h}(t,s)\leftarrow t$ for $t\neq
s$; Set $next^{h}(s,s)\leftarrow s$

4:Round $\bm{i}$: ($0\leq i\leq h-1$)

5: Every node $v$ sends the distance value $D^{i}(v,s)$ to all its incoming
neighbors.

6: $\begin{aligned} &\text{Using the values received in
Step~{}\ref{algBF:send}, node $v$ computes the distance value}\\\
&\text{$D^{i+1}(v,s)\leftarrow\min_{u\in\mathcal{N}_{out}(v)}\\{w(v,u)+D^{i}(u,s)\\}$.}\end{aligned}$

7: if $D^{i+1}(v,s)\neq D^{i}(v,s)$ then: set
$next^{h}(v,s)\leftarrow\arg\min_{u\in\mathcal{N}_{out}(v)}\\{w(v,u)+D^{i}(u,s)\\}$

###  2.4 Blocker Sets

We now describe the notion of blocker sets from King [14] where it was used in
the dynamic setting to compute fully dynamic APSP. This technique was then
first adapted to the distributed CONGEST model in [4] and later improved to
run with almost optimal bounds in [3]. The blocker sets, in essence, is a
deterministic tool to compute Set Cover deterministically, when the underlying
set is a collection of paths. We now define the notion of $h$-hop Consistent
SSSP Collection (or $h$-CSSSP) which is used in [3] to compute blocker sets
efficiently.

######  Definition 2.2 ($h$-hop CSSSP [2]).

Let $\mathcal{T}$ be a collection of trees of depth $h$ for a set of sources
$S\subseteq V$. Then $\mathcal{T}$ is an $h$-hop CSSSP collection if for every
$u,v\in V$ the path from $u$ to $v$ is the same in each of the trees in
$\mathcal{T}$ (if such a path exists), including the $h$-hop tree $T_{u}$
rooted at $u$. Further, each $T_{u}$ contains every vertex $v$ that has a path
with at most $h$ hops from $u$ in $G$ that has shortest path distance
$\delta(u,v)$.

Using the Bellman-Ford algorithm described in Section 2.3, one can compute
$h$-hop CSSSP for a source set $S$ and hop-length $h$ in $O(|S|\cdot h)$
rounds. The advantage of using $h$-CSSSP instead of a collection of $h$-hop
shortest paths is that it guarantees that all paths rooted at any vertex $v$
constitutes a rooted tree at $v$, which is not guaranteed if we only use the
collection of $h$-hop shortest paths. This is described in detail in [2].

######  Lemma 2.3 ( [2, 5]).

For a source set $S$ and hop-length $h$, $h$-hop CSSSP can be computed in
$O(|S|\cdot h)$ rounds.

We now define the notion of blocker set from King [14] which was later adapted
to the CONGEST model in [4].

######  Definition 2.4 (Blocker Set [14, 4]).

Let $H$ be a collection of rooted $h$-hop trees for a source set $S\subseteq
V$. A set $Q\subseteq V$ is a blocker set for paths in the set $H$ if every
root-to-leaf path of length $h$ in every tree in $H$ contains a node in set
$Q$.

We use the following result from Agarwal and Ramachandran [3] which we use in
our algorithm to compute a desired sequence of successive blocker sets
described in Section 3.

######  Lemma 2.5 ( [3]).

For a source set $S\subseteq V$ and hop-length $h$ and given its corresponding
$h$-CSSSP collection $\mathcal{T}$, a blocker set $Q$ for the collection of
paths in $\mathcal{T}$ can be computed deterministically in
$\tilde{O}(|S|\cdot h/(\epsilon^{2}\delta^{3}))$ rounds, where both $\epsilon$
and $\delta$ are small positive constants with a value less than or equal to
$1/12$. Also, the blocker set $Q$ has size $O(n\log n/h)$.

Since $\epsilon$ and $\delta$ are small positive constants and the only
variables are $S$ and $h$, we can deduce the following simpler corollary from
the above lemma.

######  Corollary 2.6 ( [3]).

For a source set $S\subseteq V$ and hop-length $h$ and given its corresponding
$h$-CSSSP collection $\mathcal{T}$, a blocker set $Q$ for the collection of
paths in $\mathcal{T}$ can be computed deterministically in
$\tilde{O}(|S|\cdot h)$ rounds. Also, the blocker set $Q$ has size $O(n\log
n/h)$.

###  2.5 Broadcasting Primitives

We now describe a commonly known broadcasting primitive that we use in many of
our algorithms.

######  Lemma 2.7 ( [20]).

Let $G=(V,E)$ be a directed or undirected graph. Suppose each node $v\in V$
holds $k_{v}\geq 0$ messages of $O(\log n)$ bits each, for a total of
$K=\sum_{v\in V}k_{v}$ messages. Then all nodes in the network can receive
these $K$ messages within $O(K+n)$ rounds, where $n=|V|$.

See Peleg [20] for the proof of Lemma 2.7.

##  3 Computing Sequence of Blocker Sets

In this Section, we describe our algorithm for computing a sequence of
successive blocker sets. A similar approach has been used earlier in the
randomized setting in the distributed computation of randomized all pairs
shortest paths (APSP) by Bernstein and Nanongkai [7]. We use the deterministic
blocker set algorithm of Agarwal and Ramachandran [3] to compute the
individual blocker sets in our deterministic algorithm for computing this
sequence of successive blocker sets.

Our sequence of successive blocker sets $\\{Q_{i}\\}$ exhibit very strong
properties related to long-hop shortest paths, which allows us to obtain our
$\tilde{O}(n)$ rounds deterministic algorithms for minimum weight cycle and
multi-source shortest paths problems described in Sections 4, 5 and 6. One
such crucial property is that given two nodes $s$ and $t$ such that the true
shortest path from $s$ to $t$ has very high hop length, then there exists a
blocker node $q$ in one of the blocker sets in the sequence $\\{Q_{i}\\}$ such
that the long-hop shortest path from $s$ to $t$ can be composed of a short-hop
incoming shortest path from $q$ to $s$ and a short-hop outgoing shortest path
from $q$ to $t$. We establish this property for the sequence of blocker sets
$\\{Q_{i}\\}$ later on in this section.

Algorithm 3 Computing Sequence of Blocker Sets $\\{Q_{i}\\}$

1:Input: $G=(V,E)$;

2:Set $Q_{0}\leftarrow V$; $h_{0}\leftarrow\log^{2}n$

3:for $1\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$ do

4: Compute $h_{i-1}$-CSSSP $\mathcal{T}_{i-1}$ for source set $Q_{i-1}$ using
the algorithm in [2].

5: $\begin{aligned} &\text{Compute blocker set $Q_{i}$ for the paths in
$\mathcal{T}_{i-1}$ with $Q_{i-1}$ as the source set, using}\\\ &\text{the
deterministic blocker set algorithm
in~{}\cite[cite]{[\@@bibref{}{AR20}{}{}]}.}\end{aligned}$

6: Every node $q_{i}\in Q_{i}$ broadcast its ID to the entire network.

7: $h_{i}\leftarrow h_{i-1}\cdot\log n$

Algorithm 3 describes our deterministic algorithm for computing a sequence of
blocker sets in a given graph $G=(V,E)$. In Step 2 we set the initial blocker
set $Q_{0}$ to the entire vertex set $V$ and we set the initial hop-length
$h_{0}$ to $\log^{2}n$. The for loop in Steps 3-7 runs for $\lceil\frac{\log
n}{\log\log n}\rceil-1$ iterations in total.

Each iteration $i$ of the for loop proceeds in the following manner: first in
Step 4 an $h_{i-1}$-CSSSP $\mathcal{T}_{i-1}$ is constructed for the source
set $Q_{i-1}$. We use the h-CSSSP algorithm in [2] to construct this CSSSP.
Then in Step 5 we compute a blocker set $Q_{i}$ for the paths in the
collection $\mathcal{T}_{i-1}$ using the blocker set algorithm in [3]. The
nodes that are selected in the set $Q_{i}$ broadcast their IDs to the entire
network in Step 6 in $O(|Q_{i}|+n)$ rounds. We then update the hop-length
$h_{i}$ for the next iteration in Step 7.

We now establish some important properties exhibited by the sequence of
blocker sets constructed in Algorithm 3. The following lemma shows that for
every pair of nodes $s$ and $t$ for which there exists a shortest path between
them, there exists a blocker set $Q_{j}$ in the sequence $\\{Q_{i}\\}$ such
that for some node $q_{j}\in Q_{j}$, the weight of the shortest path from $s$
to $t$, $\delta(s,t)$, is equal to the sum of the $h_{j}$-hop shortest path
distances $\delta^{h_{j}}(s,q_{j})$ and $\delta^{h_{j}}(q_{j},t)$.

######  Lemma 3.1.

Let $G=(V,E)$ be a directed or undirected graph and let $\\{Q_{i}\\}$ be the
sequence of blocker sets computed in Algorithm 3 for graph $G$. Then for each
node pairs $s,t\in V$ for which a shortest path exists, there exists some $j$
such that for some node $q_{j}\in Q_{j}$, the weight of the shortest path from
$s$ to $t$, $\delta(s,t)=\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},t)$.

###### Proof.

Consider node pair $(s,t)$ in $G$ such that among all node pairs for which the
above lemma does not hold, the value of the shortest path distance
$\delta(s,t)$ is the minimum among them. If there are multiple such pairs,
pick the one with the minimum shortest path hop-length. Now we need to show
that no such pair exists in $G$.

Let $p_{s,t}$ be the shortest path from $s$ to $t$. If there are multiple such
paths, pick the one with the minimum hop length. Let $(a,t)$ be the last edge
on this path. If $a=s$ and the hop length is 1, then the above lemma holds as
$s\in Q_{0}$ and $h_{0}\geq 1$.

We now consider the case when $a\neq s$. Let the subpath from $s$ to $a$ be
$p_{s,a}$. Since $p_{s,a}$ has hop-length less than $p_{s,t}$ and has weight
less than or equal to $\delta(s,t)$, the above lemma holds for pair $(s,a)$.
Thus there exists some $j^{\prime}$ and a node $q_{j^{\prime}}\in
Q_{j^{\prime}}$ such that
$\delta(s,a)=\delta^{h_{j^{\prime}}}(s,q_{j^{\prime}})+\delta^{h_{j^{\prime}}}(q_{j^{\prime}},a)$.

Now since the above lemma does not hold for pair $(s,t)$, it implies that the
path from $q_{j^{\prime}}$ to $t$ has hop-length strictly greater than
$h_{j^{\prime}}$ and the hop-length from $q_{j^{\prime}}$ to $a$ is equal to
$h_{j^{\prime}}$. Since the hop-length from $q_{j^{\prime}}$ to $a$ is equal
to $h_{j^{\prime}}$, by the definition of blocker set (Definition 2.4), there
exists some node $q_{j^{\prime}+1}\in Q_{j^{\prime}+1}$, such that
$q_{j^{\prime}+1}$ lies on the path from $q_{j^{\prime}}$ to $a$. Now we can
re-write the distance value $\delta(s,t)$ as:

$\displaystyle\delta(s,t)$ $\displaystyle=\delta(s,a)+w(a,t)$
$\displaystyle=\delta^{h_{j^{\prime}}}(s,q_{j^{\prime}})+\delta^{h_{j^{\prime}}}(q_{j^{\prime}},a)+w(a,t)$
$\displaystyle=\delta^{h_{j^{\prime}}}(s,q_{j^{\prime}})+\delta^{h_{j^{\prime}}}(q_{j^{\prime}},q_{j^{\prime}+1})+\delta^{h_{j^{\prime}}}(q_{j^{\prime}+1},a)+w(a,t)$
$\displaystyle\geq\delta^{2\cdot
h_{j^{\prime}}}(s,q_{j^{\prime}+1})+\delta^{1+h_{j^{\prime}}}(q_{j^{\prime}+1},t)$
$\displaystyle\geq\delta^{h_{j^{\prime}+1}}(s,q_{j^{\prime}+1})+\delta^{h_{j^{\prime}+1}}(q_{j^{\prime}+1},t)\text{\hskip
7.22743pt (since $2\cdot h_{j^{\prime}}\leq\log n\cdot
h_{j^{\prime}}=h_{j^{\prime}+1}$)}$

Since the sum of the distance values
$\delta^{h_{j^{\prime}+1}}(s,q_{j^{\prime}+1})$, and
$\delta^{h_{j^{\prime}+1}}(q_{j^{\prime}+1},t)$ corresponds to a path from $s$
to $t$, hence:

$\displaystyle\delta(s,t)$
$\displaystyle=\delta^{h_{j^{\prime}+1}}(s,q_{j^{\prime}+1})+\delta^{h_{j^{\prime}+1}}(q_{j^{\prime}+1},t)$

The above equation shows that the property holds for pair $(s,t)$ for
$j=j^{\prime}+1$, contradicting our earlier assumption. This shows that the
stated property holds for all node pairs $(s,t)$ such that a shortest path
exists between them.

∎

We now provide an upper bound on the size of the blocker sets $Q_{j}$ in the
blocker set sequence $\\{Q_{i}\\}$ (Lemma 3.2) and then using this we show
that Algorithm 3 runs in $\tilde{O}(n)$ rounds (Lemma 3.3).

######  Lemma 3.2.

Let $G=(V,E)$ be a directed or undirected graph and let $\\{Q_{i}\\}$ be the
sequence of blocker sets computed in Algorithm 3 for graph $G$. Then for each
$1\leq j\leq\lceil\frac{\log n}{\log\log n}\rceil-1$, the blocker set $Q_{j}$
in the blocker set sequence $\\{Q_{i}\\}$ has size $O(\frac{n\log
n}{h_{j-1}})$.

###### Proof.

In Step 5, the blocker set $Q_{j}$ is constructed for the paths in collection
$\mathcal{T}_{j-1}$, which have hop-length at most $h_{j-1}$. Thus by
Corollary 2.6, the set $Q_{j}$ has size $O(\frac{n\log n}{h_{j-1}})$. ∎

######  Lemma 3.3.

Algorithm 3 computes the blocker set sequence $\\{Q_{i}\\}$ deterministically
in $\tilde{O}(n)$ rounds.

###### Proof.

We first show that each iteration of the for loop in Steps 3-7 takes
$\tilde{O}(n)$ rounds. Using Lemma 2.3, Step 4 takes $O(|Q_{i-1}|\cdot
h_{i-1})=O(\frac{n\log n}{h_{i-2}}\cdot h_{i-1})$ (since
$|Q_{i-1}|=O(\frac{n\log n}{h_{i-2}})$ using Lemma 3.2) rounds. Since
$h_{i-1}=h_{i-2}\cdot\log n$, Step 4 takes $O(n\log^{2}n)$ rounds in each
iteration $i$. The computation of blocker set $Q_{i}$ in Step 5 takes
$\tilde{O}(|Q_{i-1}|\cdot h_{i-1})$ rounds (Corollary 2.6). As earlier,
$\tilde{O}(|Q_{i-1}|\cdot h_{i-1})=\tilde{O}(n\log^{2}n)=\tilde{O}(n)$. Step 6
takes $O(n)$ rounds (Lemma 2.7). Since there are in total $O(\frac{\log
n}{\log\log n})$ iterations of the for loop, the entire execution of Algorithm
3 takes $\tilde{O}(n)$ rounds. ∎

##  4 Directed Shortest Cycles

In this section, we describe our deterministic algorithm for computing the
weight of shortest cycles in a directed graph $G=(V,E)$. A trivial way to
compute these shortest cycles is first to do an initial computation of APSP on
the graph and then using the computed shortest path distance values to compute
the weight of the shortest cycles. Specifically for each node $v\in V$, the
weight of the shortest cycle containing node $v$ can be calculated by taking
the minimum of $\\{w(v,u)+\delta(u,v)\\}$ across all outgoing neighbors $u$ of
node $v$. This approach results in a $\tilde{O}(n^{4/3})$ round bound as the
current best deterministic bound for APSP is $\tilde{O}(n^{4/3})$ [3].

Our algorithm for computing shortest cycles differs from the above described
approach in that it does not need an initial computation of APSP. Instead we
first compute the blocker set sequence $\\{Q_{i}\\}$ for $G$ and then compute
the small hop shortest path distances from each of the blocker sets $Q_{j}$ in
this sequence. We then use these small hop distance values to compute the
weight of the shortest cycles for each of the nodes $v$ in graph $G$. This
approach, in effect, allows us to obtain a $\tilde{O}(n)$ rounds deterministic
algorithm for the shortest cycles problem.

The blocker set sequence $\\{Q_{i}\\}$ described in Section 3 exhibits another
strong property in the context of shortest cycles which is crucial in
obtaining our shortest cycles algorithm. Specifically given a node $v\in V$
such that the shortest cycle containing node $v$ has a very high hop length,
then there exists a blocker node $q$ in one of the blocker sets in the
sequence $\\{Q_{i}\\}$ such that the shortest cycle at node $v$ consists of an
outgoing edge $(v,u)$, followed by a short-hop incoming shortest path from
source $q$ to $u$ and a short-hop outgoing shortest path from source $q$ to
node $v$. We state this formally in Lemma 4.1.

######  Lemma 4.1.

Let $G=(V,E)$ be a directed graph and let $\\{Q_{i}\\}$ be the sequence of
blocker sets computed in Algorithm 3 for graph $G$. Let $C_{v}$ denote the
shortest cycle containing node $v$, if such a cycle exists. Then there exists
$u\in\mathcal{N}(v)$ and a $j$ such that for some node $q_{j}\in Q_{j}$, the
weight of cycle $C_{v}$,
$wt(C_{v})=w(v,u)+\delta^{h_{j}}(u,q_{j})+\delta^{h_{j}}(q_{j},v)$.

###### Proof.

Let $(v,u)$ be the edge incident to $v$ on cycle $C_{v}$. Let $p_{u,v}$ be the
subpath from $u$ to $v$ in $C_{v}$. Clearly $p_{u,v}$ is a shortest path from
$u$ to $v$ in $G$, otherwise $C_{v}$ would not be the shortest cycle for node
$v$. Then using Lemma 3.1, there exists $q_{j}\in Q_{j}$ such that
$\delta(u,v)$ is equal to the sum of values $\delta^{h_{j}}(u,q_{j})$ and
$\delta^{h_{j}}(q_{j},v)$. This establishes the above lemma. ∎

Algorithm 4 describes our deterministic algorithm for computing the shortest
cycles for each node $v\in V$ in a given directed graph $G=(V,E)$. In Step 2
we set the initial hop length $h_{0}$ to $\log^{2}n$ and we also set the
shortest cycle distance values, $\delta(v)$, for all nodes $v\in V$ to
$\infty$. We then compute the deterministic blocker set sequence $\\{Q_{i}\\}$
for graph $G$ using the algorithm described in Section 3 in Step 3. The for
loop in Steps 4-10 runs for $\lceil\frac{\log n}{\log\log n}\rceil$ iterations
in total.

Algorithm 4 Computing Directed Shortest Cycles

1:Input: Directed Graph $G=(V,E)$

2:Set $h_{0}\leftarrow\log^{2}n$; $\delta(v)\leftarrow\infty$ for all $v\in V$

3:Compute deterministic blocker set sequence $\\{Q_{i}\\}$ for $G$ using
Algorithm 3.

4:for $0\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$ do

5: $\begin{aligned} &\text{Compute $h_{i}$-hop in-SSSP for all source nodes
$q_{i}\in Q_{i}$ using Bellman-Ford}\\\
&\text{algorithm~{}\cite[cite]{[\@@bibref{}{B58}{}{}]}
(Algorithm~{}\ref{algBFIncoming}).}\end{aligned}$

6: $\begin{aligned} &\text{Compute $h_{i}$-hop out-SSSP for all source nodes
$q_{i}\in Q_{i}$ using Bellman-Ford}\\\
&\text{algorithm~{}\cite[cite]{[\@@bibref{}{B58}{}{}]}
(Algorithm~{}\ref{algBF}).}\end{aligned}$

7: $\begin{aligned} &\text{Each node $u\in V$ sends to all its incoming
neighbors $v\in\mathcal{N}_{in}(u)$, the $h_{i}$-hop in-SSSP}\\\
&\text{distance values, $\delta^{h_{i}}(u,q_{i})$, for all source nodes
$q_{i}\in Q_{i}$.}\end{aligned}$

8: Local Step at each node $\bm{v\in V}$:

9: $\delta(v)\leftarrow\min\\{\delta(v),\text{\hskip 5.0pt}\min_{q_{i}\in
Q_{i}}\\{\min_{u\in\mathcal{N}_{out}(v)}(w(v,u)+\delta^{h_{i}}(u,q_{i})+\delta^{h_{i}}(q_{i},v))\\}\\}$

10: $h_{i}\leftarrow h_{i-1}\cdot\log n$

Each iteration $i$ of the for loop in Steps 4-10 proceeds in the following
manner: Step 5 computes the $h_{i}$-hop incoming shortest paths from all
source nodes $q_{i}$ in the blocker set $Q_{i}$ using the well-known Bellman-
Ford algorithm [5] (also described in Algorithm 2). Similarly in Step 6 using
Bellman-Ford algorithm [5] (Algorithm 1), we compute the $h_{i}$-hop outgoing
shortest paths from all source nodes $q_{i}$ in the blocker set $Q_{i}$. Then
in Step 7 every node $u\in V$ sends all the computed $h_{i}$-hop incoming
shortest path distance values, $\delta^{h_{i}}(u,q_{i})$, for all blocker
nodes $q_{i}\in Q_{i}$ to all its incoming neighbor nodes
$v\in\mathcal{N}_{in}(u)$.

Using the received values in Step 7, every node $v\in V$ then computes the
weight of candidate shortest cycles passing through it, by summing up the
following three components: (1) weight of an outgoing edge $(v,u)$, (2)
followed by the weight of the $h_{i}$-hop shortest path from $u$ to a blocker
node $q_{i}\in Q_{i}$, $\delta^{h_{i}}(u,q_{i})$, (3) and the weight of the
$h_{i}$-hop shortest path from $q_{i}$ to $v$, $\delta^{h_{i}}(q_{i},v)$. Node
$v$ then calculates the weight of all such candidate cycles for all of its
outgoing neighbor nodes $u$ and for all blocker nodes $q_{i}\in Q_{i}$. It
then updates the value of $\delta(v)$, if the weight of one of the candidate
cycles is smaller than the current value of $\delta(v)$ (Steps 8-9).

We now show that, for each node $v\in V$, Algorithm 4 correctly computes the
weight of the shortest cycle passing through node $v$, if such a cycle exists
in the graph $G$.

######  Lemma 4.2.

Let $G=(V,E)$ be a directed graph. Then for each node $v\in V$, Algorithm 4
correctly computes the weight of the shortest cycle passing through node $v$,
$\delta(v)$, if such a cycle exists.

###### Proof.

Fix a node $v$. We consider two cases: (i) the case when $v$ is not part of
any cycle in graph $G$, (ii) the case when $v$ is part of some cycle in graph
$G$.

(i) $v$ is not part of any cycle in graph $G$: In this case, we need to show
that the shortest cycle distance value for node $v$, $\delta(v)$, remains at
$\infty$ throughout the execution of the algorithm. On the contrary assume
that $\delta(v)$ was instead set to some finite value. The only step where the
$\delta(v)$ values are updated is Step 9, where it is updated to value
$w(v,u)+\delta^{h_{i}}(u,q_{i})+\delta^{h_{i}}(q_{i},v)$, for some outgoing
neighbor $u$ of $v$ and a blocker node $q_{i}\in Q_{i}$. It further implies
that both distance values, $\delta^{h_{i}}(u,q_{i})$ and
$\delta^{h_{i}}(q_{i},v)$, are finite. Let $p_{u,q_{i}}$ be the path that
corresponds to the distance value $\delta^{h_{i}}(u,q_{i})$ and let path
$p_{q_{i},v}$ corresponds to the distance value $\delta^{h_{i}}(q_{i},v)$. But
the edge $(v,u)$, followed by paths $p_{u,q_{i}}$ and $p_{q_{i},v}$ gives us a
cycle involving node $v$, resulting in a contradiction.

(ii) $v$ is part of some cycle in $G$: Let $C_{v}$ be a shortest cycle for
node $v$. In this case, we need to show that the value for $\delta(v)$
computed by the algorithm equals the weight of $C_{v}$. By Lemma 4.1, there
exists $u\in\mathcal{N}_{out}(v)$ and a $j$ such that for some blocker node
$q_{j}\in Q_{j}$:

$wt(C_{v})=w(v,u)+\delta^{h_{j}}(u,q_{j})+\delta^{h_{j}}(q_{j},v)$

But then this value would have been captured in Step 9 of the Algorithm, thus
$\delta(v)\leq wt(C_{v})$.

Now if the value of $\delta(v)$ is strictly less than $wt(C_{v})$, then
similar to the previous case (Case (i)), we can argue that there exists
another cycle composed of an edge $(v,u^{\prime})$, followed by a path from
$u^{\prime}$ to $q_{i^{{}^{\prime}}}$ of hop-length at most $h_{i^{\prime}}$,
and another path from $q_{i^{{}^{\prime}}}$ to $v$ of hop-length at most
$h_{i^{\prime}}$ and has total weight less than $wt(C_{v})$, thus resulting in
a contradiction as $C_{v}$ is a shortest cycle through node $v$. This
completes the proof. ∎

In the following lemma, we show that Algorithm 4 runs in $\tilde{O}(n)$
rounds.

######  Lemma 4.3.

Algorithm 4 computes all $\delta(v)$ values deterministically in
$\tilde{O}(n)$ rounds.

###### Proof.

Step 2 is a local step. Using Lemma 3.3, the blocker set sequence
$\\{Q_{i}\\}$ can be computed deterministically in $\tilde{O}(n)$ rounds. We
now show that each iteration of the for loop in Steps 4-10 takes
$\tilde{O}(n)$ rounds.

Using Bellman-Ford algorithm [5], Steps 5 & 6 takes $O(|Q_{i}|\cdot
h_{i})=O(\frac{n\log n}{h_{i-1}}\cdot h_{i})=O(n\log^{2}n)$ (since
$|Q_{i}|=O(\frac{n\log n}{h_{i-1}})$ using Lemma 3.2) rounds. Step 7 that
involves all nodes $u\in V$ to send distance values, $\delta^{h_{i}}(u,q_{i})$
to all of their neighbor nodes take $O(|Q_{i}|)=O(\frac{n\log n}{h_{i-1}})$
rounds. Steps 8-10 are local steps and hence do not involve any communication.
Since there are in total $O(\frac{\log n}{\log\log n})$ iterations of the for
loop, the entire execution of Algorithm 4 takes $\tilde{O}(n)$ rounds in
total. ∎

Lemmas 4.2 and 4.3 together lead to the following theorem.

######  Theorem 4.4.

There is a deterministic distributed algorithm that computes ANSC on an
$n$-node directed graph with arbitrary non-negative edge weights in
$\tilde{O}(n)$ rounds.

######  Corollary 4.5.

There is a deterministic distributed algorithm that computes MWC on an
$n$-node directed graph with arbitrary non-negative edge weights in
$\tilde{O}(n)$ rounds.

##  5 Undirected Shortest Cycles

In this section, we describe our deterministic algorithm for computing MWC in
a given undirected graph $G=(V,E)$. As noted earlier in Section 1.2.2 and has
also been noted in an earlier work on MWC by Roditty and Williams [22], the
problem of computing shortest cycles in undirected graphs is much more
difficult as compared to the directed graphs. The reason behind this is that
the reduction from MWC to APSP no longer works in undirected graphs: an edge
$(v,u)$ might also be the shortest path from $u$ to $v$, and
$\min_{u}\\{w(v,u)+\delta(u,v)\\}$ might be equal to $2\cdot w(v,u)$ and not
the weight of the shortest cycle containing node $v$.

A common approach for computing the value of the minimum weight cycle in
undirected graphs, is by taking the minimum across all possible values
$\\{w(v,u)+\delta(u,w)+\delta(v,w)\\}$ where $u\in\mathcal{N}(v)$ and $w\in
V$. In the CONGEST model, this will require an initial computation of APSP,
followed by $O(n)$ communication rounds for each node to communicate its
distance values, $\delta(v,w)$, where $w\in V$, to all its neighbor nodes.
This approach takes $O(APSP+n)$ rounds in total. Since the current
deterministic bound for APSP is $\tilde{O}(n^{4/3})$ [3], this approach would
require $\tilde{O}(n^{4/3})$ rounds in total.

Similar to our algorithm for computing shortest cycles in directed graphs
described in Section 4, our algorithm for computing MWC in undirected graphs
does not need an initial computation of APSP. Before further describing our
approach for computing MWC in undirected graphs, we first describe the notion
of critical edge from Roditty and Williams [22] which is critical to obtaining
our MWC algorithm. Specifically given a minimum weight cycle $\mathcal{C}$ in
graph $G$, the critical edge property states that for every node
$v\in\mathcal{C}$, there exists an edge $(u,w)$ on $\mathcal{C}$ such that the
disjoint paths from $v$ to $u$ and from $v$ to $w$ are both shortest paths in
graph $G$. We now state a simplified version of this property from [22] that
we use in our algorithms below.

######  Lemma 5.1 (Critical Edge [22]).

Let $G=(V,E)$ be an undirected graph. Let
$\mathcal{C}=\\{v_{1},v_{2},\ldots,v_{l}\\}$ be a minimum weight cycle in $G$
of weight $wt(\mathcal{C})$ and let $s\in\mathcal{C}$. There exists an edge
$(v_{i},v_{i+1})$ on $\mathcal{C}$ such that
$\lceil\frac{wt(\mathcal{C})}{2}\rceil$ $-$
$w(v_{i},v_{i+1})\leq\delta_{\mathcal{C}}(s,v_{i})\leq\lfloor\frac{wt(\mathcal{C})}{2}\rfloor$
and $\lceil\frac{wt(\mathcal{C})}{2}\rceil$ $-$
$w(v_{i},v_{i+1})\leq\delta_{\mathcal{C}}(v_{i+1},s)\leq\lfloor\frac{wt(\mathcal{C})}{2}\rfloor$.
Furthermore, $\delta(s,v_{i})=\delta_{\mathcal{C}}(s,v_{i})$ and
$\delta(v_{i+1},s)=\delta_{\mathcal{C}}(v_{i+1},s)$.

Similar to the Lemma 4.1 for shortest cycles in directed graphs, using the
above-described notion of critical edge for undirected cycles we show that
there exists a minimum weight cycle $\mathcal{C}$ in an undirected graph $G$
(if $G$ has at least one cycle) such that $\mathcal{C}$ can be decomposed into
two short-hop shortest paths from a node in a blocker set in the sequence
$\\{Q_{i}\\}$, followed by a critical edge. Specifically, there exists a
critical edge $(u,v)\in\mathcal{C}$ and a $j$ such that for some blocker node
$q_{j}\in Q_{j}$, the cycle $\mathcal{C}$ can be decomposed into three
components: (1) $h_{j}$-hop shortest path from $q_{j}$ to $v$, (2) $h_{j}$-hop
shortest path from $q_{j}$ to $u$, (3) and the critical edge $(u,v)$. We now
establish this observation in the following lemma.

######  Lemma 5.2.

Let $G=(V,E)$ be an undirected graph that contain at least one cycle and let
$\\{Q_{i}\\}$ be the blocker set sequence for $G$. Then there exists a minimum
weight cycle $\mathcal{C}$ in $G$ and a blocker node $q_{j}\in Q_{j}$ for some
$j$, such that $wt(\mathcal{C})$ is equal to the sum of these three
components: (1) weight of a critical edge $(u,v)\in\mathcal{C}$, $w(u,v)$. (2)
weight of the $h_{j}$-hop shortest path from $q_{j}$ to $u$,
$\delta^{h_{j}}(q_{j},u)$, and (3) weight of the $h_{j}$-hop shortest path
from $q_{j}$ to $v$, $\delta^{h_{j}}(q_{j},v)$.

###### Proof.

On the contrary, assume that the above property does not hold for any minimum
weight cycles in some graph $G$. Let $j^{\prime}$ be the maximum value of $j$
such that a blocker node $q_{j}$ from the blocker set $Q_{j}$ lies on a
minimum weight cycle in $G$, i.e. no other minimum weight cycles in $G$
contains a blocker node from any of the blocker sets $Q_{j}$, where
$j>j^{\prime}$. Let this minimum weight cycle be $\mathcal{C}^{\prime}$ and
$q_{j^{\prime}}$ be a blocker node from blocker set $Q_{j^{\prime}}$ such that
$q_{j^{\prime}}\in\mathcal{C}^{\prime}$.

Let $(u,v)\in\mathcal{C}^{\prime}$ be the critical edge corresponding to
source $q_{j^{\prime}}$. Using Lemma 5.1,
$\delta(q_{j^{\prime}},u)=\delta_{\mathcal{C}^{\prime}}(q_{j^{\prime}},u)$ and
$\delta(q_{j^{\prime}},v)=\delta_{\mathcal{C}^{\prime}}(q_{j^{\prime}},v)$.
Since the above property does not hold for any minimum weight cycle in $G$, at
least one of the following conditions does not hold:

  1. (i)

$\delta^{h_{j^{\prime}}}(q_{j^{\prime}},u)=\delta(q_{j^{\prime}},u)$

  2. (ii)

$\delta^{h_{j^{\prime}}}(q_{j^{\prime}},v)=\delta(q_{j^{\prime}},v)$

Without loss of generality assume that
$\delta^{h_{j^{\prime}}}(q_{j^{\prime}},u)\neq\delta(q_{j^{\prime}},u)$. It
implies that any shortest path from $q_{j^{\prime}}$ to $u$ has hop length
greater than $h_{j^{\prime}}$. Let $p_{q_{j^{\prime}},u}$ be a shortest path
from $q_{j^{\prime}}$ to $u$ that has minimum hop length and let $a$ be the
node that is at hop length $h_{j^{\prime}}$ from node $q_{j^{\prime}}$ on path
$p_{q_{j^{\prime}},u}$.

Consider the path $p_{q_{j^{\prime}},a}$ that is part of the collection
$\mathcal{T}_{j^{\prime}}$ constructed for source set $Q_{j^{\prime}}$ in Step
4 of Algorithm 3. By the definition of blocker set (Definition 2.4), there
exists a node $q_{j^{\prime}+1}\in Q_{j^{\prime}+1}$ such that it lies on the
path $p_{q_{j^{\prime}},a}$.

Consider the cycle $\mathcal{C}^{{}^{\prime\prime}}$ obtained by replacing the
path from $q_{j^{\prime}}$ to node $a$ in $\mathcal{C}^{\prime}$ with the path
$p_{q_{j^{\prime}},a}$ . Clearly, the cycle $\mathcal{C}^{{}^{\prime\prime}}$
is also a minimum weight cycle in $G$. Now since the node $q_{j^{\prime}+1}\in
Q_{j^{\prime}+1}$ lies on $\mathcal{C}^{{}^{\prime\prime}}$, it violates our
assumption that $j^{\prime}$ is the maximum value of $j$ such that a node from
the blocker set $Q_{j}$ lies on a minimum weight cycle in $G$, thus resulting
in a contradiction.

This establishes the lemma.

∎

As noted earlier in the section, for a given source node $s$ and an edge
$(u,v)$ the value $\\{w(u,v)+\delta(s,u)+\delta(s,v)\\}$ may not necessarily
correspond to the weight of a cycle involving edge $(u,v)$. It may be possible
that either the shortest path from $s$ to $u$ or from $s$ to $v$ in itself
contains edge $(u,v)$. To differentiate such scenarios, we define a set
$\mathcal{A}_{s,v}\subseteq\mathcal{N}(v)$ such that it contains all nodes
$u\in\mathcal{N}(v)$ such that the computed shortest paths from $s$ to $u$ and
from $s$ to $v$ does not contain edge $(u,v)$. In a similar vein, we define
the notion of $\mathcal{A}^{h}_{s,v}$ when we deal with $h$-hop shortest
paths. Formally, we define the sets $\mathcal{A}_{s,v}$ and
$\mathcal{A}^{h}_{s,v}$ below:

$\mathcal{A}_{s,v}=\\{u|u\in\mathcal{N}(v),parent(s,v)\neq u\text{\hskip 5.0pt
\& \hskip 5.0pt}parent(s,u)\neq v\\}$
$\mathcal{A}^{h}_{s,v}=\\{u|u\in\mathcal{N}(v),parent^{h}(s,v)\neq
u\text{\hskip 5.0pt \& \hskip 5.0pt}parent^{h}(s,u)\neq v\\}$

Given a source node $s\in V$, a node $v\in V$ can construct the set
$\mathcal{A}^{h}_{s,v}$ locally, if it knows the $h$-hop shortest path
distance values, $\delta^{h}(s,u)$, and the corresponding parent values,
$parent^{h}(s,u)$, for all its neighbor nodes $u\in\mathcal{N}(v)$. This leads
to the following lemma.

######  Lemma 5.3.

Let $G=(V,E)$ be an undirected graph. Let $s\in V$ be a source node and let
$h>0$. If every node $v\in V$ knows the $h$-hop shortest path distance values,
$\delta^{h}(s,u)$, and the corresponding parent values, $parent^{h}(s,u)$, for
all neighbor nodes $u\in\mathcal{N}(v).$ Then node $v$ can compute the set
$\mathcal{A}^{h}_{s,v}$ locally without the need of any further communication.

We now define below some new notations in order to accurately capture the set
of cycles in graph $G$ such that they have a particular edge, say edge
$(v,u)$, as the critical edge.

######  Definition 5.4.

Let $G=(V,E)$ be an undirected graph and let $\\{Q_{i}\\}$ be the blocker set
sequence for $G$. For a node $v\in V$, we define the following collections of
cycles:

  1. 1.

$\mathcal{C}^{h}_{s,v,u}$: collection of cycles $C$ in $G$ such that edge
$(v,u)$ is the critical edge in $C$ with node $s$ as the source node and the
paths from $s$ to $v$ and from $s$ to $u$ are the $h$-hop shortest paths.

  2. 2.

$\mathcal{C}^{h}_{s,v}$: union of all sets $\mathcal{C}^{h}_{s,v,u}$ such that
$u\in\mathcal{A}^{h}_{s,v}$.

  3. 3.

$\mathcal{C}^{h}_{Q_{i},v}$: union of all sets $\mathcal{C}^{h}_{q_{j},v}$
such that $q_{j}\in Q_{j}$, where $Q_{j}$ is a blocker set in $\\{Q_{i}\\}$.

  4. 4.

$\mathcal{C}_{v}$: union of all sets $\mathcal{C}^{h_{i}}_{Q_{i},v}$ for all
$0\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$

Algorithm 5 describes our deterministic algorithm for computing the weight of
the global minimum weight cycle in a given undirected graph $G=(V,E)$. Let
$\delta_{MWC}(v)$ refers to the minimum weight across all the cycles in the
collection $\mathcal{C}_{v}$. In Step 2 we set the initial hop length $h_{0}$
to $\log^{2}n$ and we also set the value $\delta_{MWC}(v)$ to $\infty$. We
then compute the deterministic blocker set sequence $\\{Q_{i}\\}$ for graph
$G$ using the algorithm described in Section 3 in Step 3. The for loop in
Steps 4-11 runs for $\lceil\frac{\log n}{\log\log n}\rceil$ iterations in
total.

Algorithm 5 Computing Undirected Minimum Weight Cycle

1:Input: Undirected Graph $G=(V,E)$;

2:Set $h_{0}\leftarrow\log^{2}n$; $\delta_{MWC}(v)\leftarrow\infty$

3:Compute deterministic blocker set sequence $\\{Q_{i}\\}$ for $G$ using
Algorithm 3.

4:for $0\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$ do

5: $\begin{aligned} &\text{Compute $h_{i}$-hop SSSP for all source nodes
$q_{i}\in Q_{i}$ using Bellman-Ford
algorithm~{}\cite[cite]{[\@@bibref{}{B58}{}{}]}}\\\
&\text{(Algorithm~{}\ref{algBF}).}\end{aligned}$

6: $\begin{aligned} &\text{Each node $u\in V$ sends to all its neighbors
$v\in\mathcal{N}(u)$, the $h_{i}$-hop SSSP distance values,}\\\
&\text{$\delta^{h_{i}}(q_{i},u)$, along with the corresponding parent values,
$parent^{h_{i}}(q_{i},u)$ for all source nodes}\\\ &\text{$q_{i}\in
Q_{i}$.}\end{aligned}$

7: Local Step at each node $\bm{v\in V}$:

8: For each blocker node $q_{i}\in Q_{i}$:

9: Construct set $\mathcal{A}^{h_{i}}_{q_{i},v}$ locally.

10: $\delta_{MWC}(v)\leftarrow\min\\{\delta_{MWC}(v),\text{\hskip
5.0pt}\min_{u\in\mathcal{A}^{h_{i}}_{q_{i},v}}(w(v,u)+\delta^{h_{i}}(q_{i},u)+\delta^{h_{i}}(q_{i},v))\\}$

11: $h_{i}\leftarrow h_{i-1}\cdot\log n$

12:Every node $v\in V$ broadcast their local value of $\delta_{MWC}(v)$ to the
entire network.

13:Locally compute global minimum weight cycle by taking the minimum of all
received values in Step 12.

Each iteration $i$ of the for loop in Steps 4-11 proceeds in the following
manner: Step 5 computes the $h_{i}$-hop shortest path distance values and the
corresponding parent values from all source nodes $q_{i}$ in the blocker set
$Q_{i}$ using Bellman-Ford algorithm [5](also described in Algorithm 1). Then
in Step 6 every node $u\in V$ sends all the computed $h_{i}$-hop shortest path
distance values, $\delta^{h_{i}}(q_{i},u)$, and their corresponding parent
values, $parent^{h_{i}}(q_{i},u)$ for all blocker nodes $q_{i}\in Q_{i}$ to
all its neighbor nodes $u\in\mathcal{N}(v)$.

Using the received shortest path distance values, $\delta^{h_{i}}(q_{i},u)$,
and the corresponding parent values, $parent^{h_{i}}(q_{i},u)$, for all
blocker nodes $q_{i}\in Q_{i}$, in Step 9 every node $v\in V$ then constructs
the set $\mathcal{A}^{h_{i}}_{q_{i},v}$ locally for each blocker node $q_{i}$
separately. For each blocker node $q_{i}\in Q_{i}$, node $v\in V$ then
computes the weight of candidate shortest cycles with edge $(v,u)$ as the
critical edge for source node $q_{i}$, where
$u\in\mathcal{A}^{h_{i}}_{q_{i},v}$. These weights can be computed by summing
up the following three components: (1) weight of the critical edge $(v,u)$,
(2) followed by the $h_{i}$-hop shortest path distance value,
$\delta^{h_{i}}(q_{i},v)$, from $q_{i}$ to $v$, and (3) the $h_{i}$-hop
shortest path distance value, $\delta^{h_{i}}(q_{i},u)$, from $q_{i}$ to $u$.
It then updates the value of $\delta_{MWC}(v)$, if the weight of one of these
candidate cycles is smaller than the current value of $\delta_{MWC}(v)$ (Step
10).

Finally, after all nodes in $V$ have computed their local values for
$\delta_{MWC}(v)$, each node then broadcast its locally computed value for
$\delta_{MWC}(v)$ to the entire network in Step 12 in $O(n)$ rounds. Using all
the $\delta_{MWC}(v)$ values received in Step 12, every node in the network
can now compute the weight of the minimum weight cycle by taking the minimum
of all the received $\delta_{MWC}(v)$ values (Step 13).

We now show that Algorithm 5 correctly computes the weight of the minimum
weight cycle in a given undirected graph $G=(V,E)$, if a cycle exists in $G$.

######  Lemma 5.5.

Let $G=(V,E)$ be an undirected graph. Then Algorithm 5 correctly computes the
weight of the minimum weight cycle in $G$, if there exists a cycle in $G$.

###### Proof.

We consider two cases: (i) when there is no cycle in $G$ (ii) there exists at
least one cycle in $G$.

(i) there is no cycle in graph $G$: In this case, we need to show that the
value for $\delta_{MWC}(v)$ remains at $\infty$ throughout the execution of
the algorithm, for all nodes $v\in V$. On the contrary assume that
$\delta_{MWC}(v)$ was instead set to some finite values for some nodes. Let
$v$ be such a node.

The only step where the $\delta_{MWC}(v)$ value is updated is Step 10, where
it is updated to value
$w(v,u)+\delta^{h_{i}}(q_{i},u)+\delta^{h_{i}}(q_{i},v)$, for some blocker
node $q_{i}\in Q_{i}$ and $u\in\mathcal{A}^{h_{i}}_{q_{i},v}$. It further
implies that both distance values, $\delta^{h_{i}}(q_{i},u)$ and
$\delta^{h_{i}}(q_{i},v)$, are finite. Let $p_{q_{i},u}$ be the path that
corresponds to the distance value $\delta^{h_{i}}(q_{i},u)$ and let path
$p_{q_{i},v}$ corresponds to the distance value $\delta^{h_{i}}(q_{i},v)$.
Since $u\in\mathcal{A}^{h_{i}}_{q_{i},v}$, edge $(u,v)$ is not present on both
paths $p_{q_{i},u}$ and $p_{q_{i},v}$, and hence we can generate a cycle in
$G$ by combining the edge $(v,u)$, followed by paths $p_{q_{i},u}$ and
$p_{q_{i},v}$, thus resulting in a contradiction.

(ii) there exists at least one cycle in $G$: In this case we need to show that
the value for $\delta_{MWC}$ computed by the algorithm equals the weight of a
minimum weight cycle in $G$. By Lemma 5.2, there exists a minimum weight cycle
$C$ in $G$ such that for some blocker node $q_{j}\in Q_{j}$ and the critical
edge $(u,v)\in C$ for source $q_{j}$, the following holds:

$wt(C)=w(u,v)+\delta^{h_{j}}(q_{j},u)+\delta^{h_{j}}(q_{j},v)$

Now since edge $(u,v)$ is not part of the $h_{j}$-hop shortest paths from
$q_{j}$ to nodes $u$ and $v$, $u\in\mathcal{A}^{h_{j}}_{q_{j},v}$ and
$v\in\mathcal{A}^{h_{j}}_{q_{j},u}$. Hence the above value for $wt(C)$ would
have been captured in Step 10 of the Algorithm at nodes $u$ and $v$, thus
$\delta_{MWC}\leq wt(C)$.

Now if the value of $\delta_{MWC}$ is strictly less than $w(C)$, then similar
to the previous case (Case(i)), we can argue that there exists another cycle
composed of a critical edge $(u,v)$, followed by a path from a blocker node
$q_{i^{\prime}}$ to $v$ of hop-length at most $h_{i^{\prime}}$, and another
path from $q_{i^{\prime}}$ to $v$ of hop-length at most $h_{i^{\prime}}$ and
has total weight less than $wt(C)$. This results in a contradiction as $C$ is
a minimum weight cycle in $G$. This completes the proof. ∎

In the following lemma, we show that Algorithm 5 runs in total $\tilde{O}(n)$
rounds.

######  Lemma 5.6.

Algorithm 5 computes $\delta_{MWC}$ deterministically in $\tilde{O}(n)$
rounds.

###### Proof.

Step 2 is a local step. Using Lemma 3.3, the blocker set sequence
$\\{Q_{i}\\}$ can be computed deterministically in $\tilde{O}(n)$ rounds. Step
12 takes $O(n)$ rounds using Lemma 2.7 and Step 13 is a local step. We now
show that each iteration of the for loop in Steps 4-11 takes $\tilde{O}(n)$
rounds.

Using Bellman-Ford algorithm [5], Step 5 takes $O(|Q_{i}|\cdot h_{i})=$
$O(\frac{n\log n}{h_{i-1}}\cdot h_{i})=O(n\log^{2}n)$ (since
$|Q_{i}|=O(\frac{n\log n}{h_{i-1}})$ using Lemma 3.2) rounds. Step 6 that
involves all nodes $u\in V$ to send distance values,
$\delta^{h_{i}}(q_{i},u)$, and the parent values, $parent^{h_{i}}(q_{i},u)$,
to all of their neighbor nodes takes $O(|Q_{i}|)=O(\frac{n\log n}{h_{i-1}})$
rounds. Steps 7-11 are local steps and hence do not involve any communication.
Since there are in total $O(\frac{\log n}{\log\log n})$ iterations of the for
loop, the entire execution of Algorithm 5 takes $\tilde{O}(n)$ rounds in
total. ∎

Lemmas 5.5 and 5.6 together lead to the following theorem.

######  Theorem 5.7.

There is a deterministic distributed algorithm that computes MWC on an
$n$-node undirected graph with arbitrary non-negative edge weights in
$\tilde{O}(n)$ rounds.

One could argue whether the approach discussed in this section can lead to an
$\tilde{O}(n)$ rounds deterministic ANSC algorithm for undirected graphs. In
order to do so, one would need the exact shortest path distance values from
every node $v$ to the endpoints of the critical edge of its corresponding
shortest cycle (instead of the current Step 10 of Algorithm 5). This, however,
will require an initial computation of APSP.

##  6 Deterministic MSSP in Congest Model

In this section, we describe how to compute multi-source shortest path
distances using the deterministic blocker set sequence algorithm described in
Section 3. Our deterministic algorithm runs in $\tilde{O}(n)$ rounds when the
source set $S$ has size at most $\sqrt{n}$. This problem has been studied in
other models of distributed computing, such as Congested Clique, in a recent
work by Elkin and Neiman [12]. We now formally describe the problem statement
below.

######  Definition 6.1 (MSSP [12]).

Let $G=(V,E)$ be a directed or undirected graph. Let $S\subseteq V$ be a
source set. The MSSP problem deals with computing the shortest path distance
values, $\delta(s,t)$ for each $s\in S$ at all nodes $t\in V$.

Prior to this work, no near-linear rounds deterministic algorithm was known
for this particular problem when $|S|=\Omega(n^{\epsilon})$ for any positive
constant $\epsilon>0$. Algorithm 6 describes our deterministic algorithm for
computing the shortest path distance values from source nodes in set $S$ to
all nodes $v\in V$. In Step 2 we compute the deterministic blocker set
sequence $\\{Q_{i}\\}$ for graph $G$ using the algorithm described in Section
3. We then set the initial hop length $h_{0}$ to $\log^{2}n$ and we define the
value of $h_{i}$ to $h_{i-1}\cdot\log n$ in Step 3.

Algorithm 6 MSSP

1:Input: Directed or Undirected Graph $G=(V,E)$;

2:Compute deterministic blocker set sequence $\\{Q_{i}\\}$ for $G$ using
Algorithm 3.

3:$h_{0}\leftarrow\log^{2}n$; $h_{i}\leftarrow h_{i-1}\cdot\log n$.

4:Compute $\sqrt{n}$-hop out-SSSP for all source nodes $s\in S$ using Bellman-
Ford algorithm [5] (Algorithm 1).

5:Local Step at each node $\bm{v\in V}$: Set
$\delta(s,v)\leftarrow\delta^{\sqrt{n}}(s,v)$ for all $s\in S$.

6:Let $i^{\prime}$ be the max value of $i$ such that
$h_{i}\leq\frac{\sqrt{n}}{2}$.

7:for $i^{\prime}\leq i\leq\lceil\frac{\log n}{\log\log n}\rceil-1$ do

8: $\begin{aligned} &\text{Compute $h_{i}$-hop in-SSSP for all source nodes
$q\in Q_{i}$ using Bellman-Ford
algorithm~{}\cite[cite]{[\@@bibref{}{B58}{}{}]}}\\\
&\text{(Algorithm~{}\ref{algBFIncoming}).}\end{aligned}$

9: $\begin{aligned} &\text{Compute $h_{i}$-hop out-SSSP for all source nodes
$q\in Q_{i}$ using Bellman-Ford
algorithm~{}\cite[cite]{[\@@bibref{}{B58}{}{}]}}\\\
&\text{(Algorithm~{}\ref{algBF}).}\end{aligned}$

10: $\begin{aligned} &\text{Each node $s\in S$ broadcasts the $h_{i}$-hop in-
SSSP distance values, $\delta^{h_{i}}(s,q_{i})$, for all}\\\ &\text{blocker
nodes $q_{i}\in Q_{i}$.}\end{aligned}$

11: Local Step at each node $v\in V$:

12: For each source $s\in S$:

13: $\delta(s,v)\leftarrow\min\\{\delta(s,v),\min_{q_{i}\in
Q_{i}}\\{\delta^{h_{i}}(s,q_{i})+\delta^{h_{i}}(q_{i},v)\\}\\}$

14: $h_{i}\leftarrow h_{i-1}\cdot\log n$

In Step 4 we compute the $\sqrt{n}$-hop outgoing shortest path distance values
from all source nodes $s\in S$ using Bellman-Ford algorithm [5] (Algorithm 1).
Then in Step 5 every node $v\in V$ sets its current estimate for source nodes
$s\in S$, $\delta(s,v)$, to $\delta^{\sqrt{n}}(s,v)$.

Since we have already computed shortest path distance values for all shortest
paths from source set $S$ of hop-length at most $\sqrt{n}$, we need to focus
on computing shortest path distance values for paths that have hop length
greater than $\sqrt{n}$. In order to do so, we compute the maximum value of
$i$ such that the value of $h_{i}$ is at most $\frac{\sqrt{n}}{2}$, and we
denote this value of $i$ as $i^{\prime}$ (Step 6. The for loop in Steps 7-14
runs for $\lceil\frac{\log n}{\log\log n}\rceil-i^{\prime}$ iterations in
total.

Each iteration $i$ of the for loop in Steps 7-14 proceeds in the following
manner: Step 8 computes the $h_{i}$-hop incoming shortest path distance
values, $\delta^{h_{i}}(v,q_{i})$, from all blocker nodes $q_{i}$ in the
blocker set $Q_{i}$ using Bellman-Ford algorithm [5] (also described in
Algorithm 2). Similarly in Step 9 we compute the $h_{i}$-hop outgoing shortest
path distance values, $\delta^{h_{i}}(q_{i},v)$, from all blocker nodes
$q_{i}$ in the blocker set $Q_{i}$ using Bellman-Ford algorithm [5] (Algorithm
1).

In Step 10 every node $s\in S$ broadcasts the $h_{i}$-hop incoming shortest
path distance values, $\delta^{h_{i}}(s,q_{i})$, to the entire network. Using
the received shortest path distance values, $\delta^{h_{i}}(s,q_{i})$, for all
source nodes $s\in S$ and blocker nodes $q_{i}\in Q_{i}$, in Steps 11-13 every
node $v\in V$ then computes the candidate shortest path distance values from
nodes in $S$ by summing up the distance values, $\delta^{h_{i}}(s,q_{i})$, and
$\delta^{h_{i}}(q_{i},v)$ for every pair $(s,q_{i})$. It then updates the
current value for $\delta(s,v)$ for all source nodes $s$ using the equation in
Step 13.

We now show that, for each source $s\in S$ and $v\in V$, Algorithm 6 correctly
computes the shortest path distance values, $\delta(s,v)$. We break this into
two parts, depending on the hop-length of the shortest path between nodes $s$
and $v$. In Lemma 6.2 we handle the case when the shortest path from $s$ to
$v$ has hop length at most $\sqrt{n}$ and in Lemma 6.3 we handle the case when
all all shortest paths from $s$ to $v$ have hop-length greater than
$\sqrt{n}$.

######  Lemma 6.2.

Let $G=(V,E)$ be a directed or undirected graph and let $S\subseteq V$ be a
source set of $V$ of size at most $\sqrt{n}$. Then for each source $s\in S$
and node $v\in V$ such that there exists a shortest path from $s$ to $v$ of
hop-length at most $\sqrt{n}$, Algorithm 6 correctly computes the weight of
the shortest paths from $s$ to $v$.

###### Proof.

Fix a source node $s\in S$ and a node $v\in V$. Here we need to show that the
computed value for $\delta(s,v)$ is equal to $\delta^{\sqrt{n}}(s,v)$.

Since we compute $\sqrt{n}$-hop shortest path distance values from all source
nodes in $S$ using the Bellman-Ford algorithm in Step 4, the value
$\delta^{\sqrt{n}}(s,v)$ is set for $\delta(s,v)$ in Step 5. Hence
$\delta(s,v)\leq\delta^{\sqrt{n}}(s,v)$.

Now consider the case when $\delta(s,v)<\delta^{\sqrt{n}}(s,v)$, then it
implies that there exists an $i$ such that for some $q_{i}\in Q_{i}$, the
following holds:

$\delta^{h_{i}}(s,q_{i})+\delta^{h_{i}}(q_{i},v)<\delta^{\sqrt{n}}(s,v)$

which is a contradiction, as this implies that there exists a path from $s$ to
$v$ through node $q_{i}$ that has weight less than $\delta^{\sqrt{n}}(s,v)$.
This establishes the lemma. ∎

######  Lemma 6.3.

Let $G=(V,E)$ be a directed or undirected graph and let $S\subseteq V$ be a
source set of $V$ of size at most $\sqrt{n}$. Then for each source $s\in S$
and node $v\in V$ such that all shortest paths from $s$ to $v$ have hop-length
greater than $\sqrt{n}$, Algorithm 6 correctly computes the shortest path
distance values, $\delta(s,v)$, from nodes $s$ to $v$.

###### Proof.

Fix a source node $s\in S$ and a node $v\in V$ such that all shortest paths
from $s$ to $v$ have hop-length greater than $\sqrt{n}$. By Lemma 3.1 there
exists a $j$ such that
$\delta(s,v)=\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$. Clearly
$h_{j}>\frac{\sqrt{n}}{2}$, otherwise the hop-length of the path will be less
than $\sqrt{n}$, and hence $j\geq i^{\prime}$. Here we need to show that the
computed value for $\delta(s,v)$ is equal to
$\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$.

Since we compute $h_{j}$-hop outgoing and incoming shortest path distance
values from all blocker nodes in $Q_{j}$ using the Bellman-Ford algorithm in
Steps 8-9, the value $\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$ is set
for $\delta(s,v)$ in Step 14. Hence
$\delta(s,v)\leq\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$.

Now consider the case when
$\delta(s,v)<\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$, then it implies
following two cases:

(i) that there exists an $i$ such that for some $q_{i}\in Q_{i}$, the
following holds:

$\delta^{h_{i}}(s,q_{i})+\delta^{h_{i}}(q_{i},v)<\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$

This implies that there is a shorter path from $s$ to $t$ through a blocker
node $q_{i}\in Q_{i}$ for $i\neq j$, which is a contradiction as the path from
$s$ to $v$ through node $q_{j}$ is the shortest path from $s$ to $v$.

(ii) $\delta^{\sqrt{n}}(s,v)<\delta^{h_{j}}(s,q_{j})+\delta^{h_{j}}(q_{j},v)$:
This implies that there is a shorter path from $s$ to $t$ of hop-length at
most $\sqrt{n}$. But this cannot happen since all shortest paths from $s$ to
$v$ have hop-length greater than $\sqrt{n}$. ∎

In the following lemma, we show that Algorithm 6 runs in $\tilde{O}(n)$
rounds.

######  Lemma 6.4.

Algorithm 6 computes all the $\delta(s,v)$ values deterministically in
$\tilde{O}(n)$ rounds.

###### Proof.

Step 2 takes $\tilde{O}(n)$ rounds using Lemma 3.3. Steps 3 and 5 are local
steps.

Using Bellman-Ford algorithm [5], Step 4 takes $O(\sqrt{n}\cdot\sqrt{n})$
$=O(n)$ rounds. We now show that each iteration of the for loop in Steps 7-14
takes $\tilde{O}(n)$ rounds.

Steps 8 and 9 takes $O(|Q_{i}|\cdot h_{i})=O(\frac{n\log n}{h_{i-1}}\cdot
h_{i})$ $=O(n\log^{2}n)$ (since $|Q_{i}|=O(\frac{n\log n}{h_{i-1}})$ using
Lemma 3.2) rounds. Step 10 that involves all source nodes $s\in S$ to send
distance values, $\delta^{h_{i}}(s,q_{i})$, to the entire network takes
$O(|S|\cdot|Q_{i}|)$ $=O(\sqrt{n}\cdot\frac{n\log n}{h_{i-1}})$
$=O(\sqrt{n}\cdot\frac{n\log n}{\sqrt{n}/2})$ $=O(n\log n)$ rounds. Steps
11-14 are local steps and hence do not involve any communication. Since there
are in total $O(\frac{\log n}{\log\log n})$ iterations of the for loop, the
entire execution of the algorithm takes $\tilde{O}(n)$ rounds in total. ∎

Lemmas 6.2-6.4 together lead to the following theorem.

######  Theorem 6.5.

There is a deterministic distributed algorithm that computes MSSP on an
$n$-node directed or undirected graph with arbitrary non-negative edge weights
in $\tilde{O}(n)$ rounds, given that the size of source set is at most
$\sqrt{n}$.

## References

  * [1] U. Agarwal and V. Ramachandran.  Fine-grained complexity for sparse graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 239–252, 2018.
  * [2] U. Agarwal and V. Ramachandran.  Distributed weighted all pairs shortest paths through pipelining.  In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 23–32. IEEE, 2019.
  * [3] U. Agarwal and V. Ramachandran.  Faster deterministic all pairs shortest paths in congest model.  In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 11–21, 2020.
  * [4] U. Agarwal, V. Ramachandran, V. King, and M. Pontecorvi.  A deterministic distributed algorithm for exact weighted all-pairs shortest paths in õ (n 3/2) rounds.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 199–205, 2018.
  * [5] R. Bellman.  On a routing problem.  Quarterly of applied mathematics, 16(1):87–90, 1958.
  * [6] B. Berger, J. Rompel, and P. W. Shor.  Efficient nc algorithms for set cover with applications to learning and geometry.  Journal of Computer and System Sciences, 49(3):454–477, 1994.
  * [7] A. Bernstein and D. Nanongkai.  Distributed exact weighted all-pairs shortest paths in randomized near-linear time.  SIAM Journal on Computing, 52(2):STOC19–112, 2021.
  * [8] M. Cygan, H. N. Gabow, and P. Sankowski.  Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings.  Journal of the ACM (JACM), 62(4):1–30, 2015.
  * [9] M. Dalirooyfard, C. Jin, V. V. Williams, and N. Wein.  Approximation algorithms and hardness for $n$-pairs shortest paths and all-nodes shortest cycles.  arXiv preprint arXiv:2204.03076, 2022.
  * [10] M. Dalirrooyfard and V. V. Williams.  Conditionally optimal approximation algorithms for the girth of a directed graph.  In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168, page 35. Schloss Dagstuhl–Leibniz-Zentrum f $\\{$$\backslash$" u$\\}$ r Informatik, 2020.
  * [11] M. Elkin.  Distributed exact shortest paths in sublinear time.  Journal of the ACM (JACM), 67(3):1–36, 2020.
  * [12] M. Elkin and O. Neiman.  Centralized, parallel, and distributed multi-source shortest paths via hopsets and rectangular matrix multiplication.  In 39th International Symposium on Theoretical Aspects of Computer Science, 2022.
  * [13] A. Kadria, L. Roditty, A. Sidford, V. V. Williams, and U. Zwick.  Algorithmic trade-offs for girth approximation in undirected graphs.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1471–1492. SIAM, 2022.
  * [14] V. King.  Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 81–89. IEEE, 1999.
  * [15] E. L. Lawler.  Optimal cycles in graphs and the minimal cost-to-time ratio problem.  In Periodic optimization, pages 37–60. Springer, 1972.
  * [16] A. Lincoln, V. V. Williams, and R. Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1236–1252. SIAM, 2018.
  * [17] A. Lingas and E.-M. Lundell.  Efficient approximation algorithms for shortest cycles in undirected graphs.  Information Processing Letters, 109(10):493–498, 2009.
  * [18] V. Manoharan and V. Ramachandran.  Brief announcement: Near optimal bounds for replacement paths and related problems in the congest model.  In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 369–371, 2022.
  * [19] J. B. Orlin and A. Sedeño-Noda.  An o (nm) time algorithm for finding the min length directed cycle in a graph.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1866–1879. SIAM, 2017.
  * [20] D. Peleg.  Distributed computing: a locality-sensitive approach.  SIAM, 2000.
  * [21] L. Roditty and R. Tov.  Approximating the girth.  ACM Transactions on Algorithms (TALG), 9(2):1–13, 2013.
  * [22] L. Roditty and V. V. Williams.  Minimum weight cycles and triangles: Equivalences and algorithms.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 180–189. IEEE, 2011.
  * [23] L. Roditty and V. V. Williams.  Subquadratic time approximation algorithms for the girth.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 833–845. SIAM, 2012.
  * [24] P. Sankowski and K. Węgrzycki.  Improved distance queries and cycle counting by frobenius normal form.  Theory of Computing Systems, 63(5):1049–1067, 2019.
  * [25] R. Yuster.  A shortest cycle for each vertex of a graph.  Information processing letters, 111(21-22):1057–1061, 2011.


* Piro et al. (2021) Piro, A. L., Haynie, A., & Yao, Y. 2021, ApJ, 909, 209
  * Planck Collaboration et al. (2018) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2018, arXiv e-prints, arXiv:1807.06209
  * Qin et al. (2023) Qin, Y.-J., Zhang, K., Bloom, J., et al. 2023, arXiv e-prints, arXiv:2309.10022
  * Rabinak & Waxman (2011) Rabinak, I., & Waxman, E. 2011, ApJ, 728, 63
  * Ricker et al. (2014) Ricker, G. R., Winn, J. N., Vanderspek, R., et al. 2014, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 9143, Space Telescopes and Instrumentation 2014: Optical, Infrared, and Millimeter Wave, ed. J. Oschmann, Jacobus M., M. Clampin, G. G. Fazio, & H. A. MacEwen, 914320
  * Rodrigo & Solano (2020) Rodrigo, C., & Solano, E. 2020, in XIV.0 Scientific Meeting (virtual) of the Spanish Astronomical Society, 182
  * Rodrigo et al. (2012) Rodrigo, C., Solano, E., & Bayo, A. 2012, SVO Filter Profile Service Version 1.0, IVOA Working Draft 15 October 2012, doi:10.5479/ADS/bib/2012ivoa.rept.1015R
  * Roming et al. (2005) Roming, P. W. A., Kennedy, T. E., Mason, K. O., et al. 2005, Space Sci. Rev., 120, 95
  * Rubin & Gal-Yam (2017) Rubin, A., & Gal-Yam, A. 2017, The Astrophysical Journal, 848, 8
  * Rubin et al. (2016) Rubin, A., Gal-Yam, A., Cia, A. D., et al. 2016, The Astrophysical Journal, 820, 33
  * Salim & Narayanan (2020) Salim, S., & Narayanan, D. 2020, ARA&A, 58, 529
  * Sapir & Halbertal (2014) Sapir, N., & Halbertal, D. 2014, The Astrophysical Journal, 796, 145
  * Sapir et al. (2011) Sapir, N., Katz, B., & Waxman, E. 2011, ApJ, 742, 36
  * Sapir et al. (2013) Sapir, N., Katz, B., & Waxman, E. 2013, The Astrophysical Journal, 774, 79
  * Sapir & Waxman (2017) Sapir, N., & Waxman, E. 2017, ApJ, 838, 130
  * Saxton et al. (2022) Saxton, R. D., König, O., Descalzo, M., et al. 2022, Astronomy and Computing, 38, 100531
  * Schlafly & Finkbeiner (2011) Schlafly, E. F., & Finkbeiner, D. P. 2011, ApJ, 737, 103
  * Schlegel et al. (1998) Schlegel, D. J., Finkbeiner, D. P., & Davis, M. 1998, ApJ, 500, 525
  * Shvartzvald et al. (2023) Shvartzvald, Y., Waxman, E., Gal-Yam, A., et al. 2023, arXiv e-prints, arXiv:2304.14482
  * Siebert et al. (2021) Siebert, M. R., Davis, K., Tinyanont, S., Foley, R. J., & Strasburger, E. 2021, Transient Name Server Classification Report, 2021-2383, 1
  * Skilling (2004) Skilling, J. 2004, in American Institute of Physics Conference Series, Vol. 735, Bayesian Inference and Maximum Entropy Methods in Science and Engineering: 24th International Workshop on Bayesian Inference and Maximum Entropy Methods in Science and Engineering, ed. R. Fischer, R. Preuss, & U. V. Toussaint, 395–405
  * Skilling (2006) Skilling, J. 2006, Bayesian Analysis, 1, 833
  * Smartt (2009) Smartt, S. J. 2009, Annual Review of Astronomy and Astrophysics, 47, 63
  * Smartt (2015) —. 2015, PASA, 32, e016
  * Smith et al. (2002) Smith, J. A., Tucker, D. L., Kent, S., et al. 2002, AJ, 123, 2121
  * Sollerman et al. (2021) Sollerman, J., Yang, S., Schulze, S., et al. 2021, A&A, 655, A105
  * Soumagnac et al. (2020) Soumagnac, M. T., Ganot, N., Irani, I., et al. 2020, ApJ, 902, 6
  * Speagle (2020) Speagle, J. S. 2020, MNRAS, 493, 3132
  * Steele et al. (2004) Steele, I. A., Smith, R. J., Rees, P. C., et al. 2004, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 5489, Ground-based Telescopes, ed. J. Oschmann, Jacobus M., 679–692
  * Stritzinger et al. (2018) Stritzinger, M. D., Taddia, F., Burns, C. R., et al. 2018, A&A, 609, A135
  * Svirski et al. (2012) Svirski, G., Nakar, E., & Sari, R. 2012, ApJ, 759, 108
  * Tartaglia et al. (2018) Tartaglia, L., Sand, D. J., Valenti, S., et al. 2018, ApJ, 853, 62
  * Terreran et al. (2022) Terreran, G., Jacobson-Galán, W. V., Groh, J. H., et al. 2022, ApJ, 926, 20
  * Tinyanont et al. (2022) Tinyanont, S., Ridden-Harper, R., Foley, R. J., et al. 2022, MNRAS, 512, 2777
  * Tonry et al. (2018) Tonry, J. L., Denneau, L., Heinze, A. N., et al. 2018, Publications of the Astronomical Society of the Pacific, 130, 064505
  * Valenti et al. (2016) Valenti, S., Howell, D. A., Stritzinger, M. D., et al. 2016, MNRAS, 459, 3939
  * Valerin et al. (2022) Valerin, G., Pumo, M. L., Pastorello, A., et al. 2022, Monthly Notices of the Royal Astronomical Society, 513, 4983
  * Vallely et al. (2021) Vallely, P. J., Kochanek, C. S., Stanek, K. Z., Fausnaugh, M., & Shappee, B. J. 2021, MNRAS, 500, 5639
  * van der Walt et al. (2019) van der Walt, S., Crellin-Quick, A., & Bloom, J. 2019, The Journal of Open Source Software, 4, 1247
  * Van Dyk (2017) Van Dyk, S. D. 2017, Philosophical Transactions of the Royal Society of London Series A, 375, 20160277
  * van Loon et al. (2005) van Loon, J. T., Cioni, M. R. L., Zijlstra, A. A., & Loup, C. 2005, A&A, 438, 273
  * Vasylyev et al. (2022) Vasylyev, S. S., Filippenko, A. V., Vogl, C., et al. 2022, The Astrophysical Journal, 934, 134
  * Vasylyev et al. (2023a) Vasylyev, S. S., Vogl, C., Yang, Y., et al. 2023a, arXiv e-prints, arXiv:2304.06147
  * Vasylyev et al. (2023b) Vasylyev, S. S., Yang, Y., Patra, K. C., et al. 2023b, arXiv e-prints, arXiv:2303.06497
  * Virtanen et al. (2020) Virtanen, P., Gommers, R., Oliphant, T. E., et al. 2020, Nature Methods, 17, 261
  * Waxman & Katz (2017) Waxman, E., & Katz, B. 2017, in Handbook of Supernovae, ed. A. W. Alsabti & P. Murdin, 967
  * Weil et al. (2020) Weil, K. E., Subrayan, B. M., & Milisavljevic, D. 2020, Transient Name Server Classification Report, 2020-3912, 1
  * Yang et al. (2021) Yang, S., Sollerman, J., Strotjohann, N. L., et al. 2021, A&A, 655, A90
  * Yaron & Gal-Yam (2012) Yaron, O., & Gal-Yam, A. 2012, Publications of the Astronomical Society of the Pacific, 124, 668
  * Yaron et al. (2017) Yaron, O., Perley, D. A., Gal-Yam, A., et al. 2017, Nature Physics, 13, 510
  * York et al. (2000) York, D. G., Adelman, J., Anderson, Jr., J. E., et al. 2000, AJ, 120, 1579
  * Zackay et al. (2016) Zackay, B., Ofek, E. O., & Gal-Yam, A. 2016, ApJ, 830, 27
  * Zimmerman et al. (2023) Zimmerman, E. A., Irani, I., Chen, P., et al. 2023, arXiv e-prints, arXiv:2310.10727

## Appendix A

###  A.1 Shock-cooling model

####  A.1.1 Blackbody evolution

We fit SN light-curves to the shock-cooling model of Morag et al. (2022). This
model describes the blackbody evolution of a cooling envelope until
recombination or sufficient transparency of the envelope, using a set of four
free parameters: (1) $R_{13}$, the radius of the progenitor star in units of
$10^{13}$ cm. (2) $f_{\rho}M_{0}$ the product of the numeric factor
$f_{\rho}$, which describes the structure of the density near the edge of the
stellar envelope, and $M_{0}$ which is the progenitor mass prior to the SN in
units of $M_{\odot}$. (3) $v_{s*,8.5}$ the shock velocity parameter in units
of $10^{8.5}{\rm cm\ s^{-1}}$, which corresponds to
$v_{s*,8.5}=1.05f_{\rho}^{-0.19}\sqrt{(}E/M)$, roughly equal to $\sim
v_{ej}/5$ at early times. (4) $M_{\rm env}$, the envelope mass.
$\kappa_{0.34}$ is the opacity in units of $0.34\,\rm cm^{2}$ g-1 and is set
to 1 for all cases. $t_{d}/t_{hr}$ is the time since the explosion in units of
days or hours respectively. Following their notation, $L,T$ evolve according
to:

$L_{SC}=L_{\rm planar}+0.9\exp\left[-\left(\frac{2t}{t_{\rm
tr}}\right)^{0.5}\right]\,L_{\rm RW},$ (A1) $T_{\rm col}=1.1\min\left[T_{\rm
ph,planar}\,,\,T_{\rm ph,RW}\right]$ (A2)

which are valid during

$3R/c=17\,R_{13}\,{\rm min}<t<\min[t_{\rm 0.7eV},t_{\rm tr}/2].$ (A3)

Where the terms in Eqs. (A1 – A3) are

$\displaystyle\frac{L_{{\rm planar}}}{10^{42}\,{\rm
erg\,s^{-1}}}=3.01\,R_{13}^{2.46}v_{{\rm
s*,8.5}}^{0.60}(f_{\rho}M_{0})^{-0.06}t_{{\rm
hr}}^{-4/3}\kappa_{0.34}^{-1.06},$ (A4) $\displaystyle\frac{T_{{\rm
ph,planar}}}{\,{\rm eV\,}}=6.94\,R_{13}^{0.12}v_{{\rm
s*,8.5}}^{0.15}(f_{\rho}M_{0})^{-0.02}\kappa_{0.34}^{-0.27}t_{{\rm
hr}}^{-1/3},$ (A5) $\displaystyle\frac{L_{{\rm RW}}}{2.08\times 10^{42}\,{\rm
erg\,s}^{-1}}=\,R_{13}v_{{\rm
s*,8.5}}^{1.91}(f_{\rho}M_{0})^{0.09}\kappa_{0.34}^{-0.91}t_{{\rm
d}}^{-0.17},$ (A6) $\displaystyle\frac{T_{{\rm
ph,RW}}}{\,{\rm\,eV}}=1.66\,R_{13}^{1/4}v_{{\rm
s*,8.5}}^{0.07}(f_{\rho}M_{0})^{-0.03}\kappa_{0.34}^{-0.28}t_{{\rm
d}}^{-0.45},$ (A7) $t_{0.7\rm eV}=6.86\,R_{13}^{0.56}v_{\rm
s*,8.5}^{0.16}\kappa_{0.34}^{-0.61}(f_{\rho}M_{0})^{-0.06}\rm\,days$ (A8)
$\begin{split}\begin{aligned} t_{\rm
tr}&=19.5\,\sqrt{\frac{\kappa_{0.34}M_{\rm env,0}}{v_{\rm
s*,8.5}}}\,\text{days}.\end{aligned}\end{split}$ (A9)

####  A.1.2 Deviations from blackbody

M23 fully relax the assumption of LTE. A temperature, density and wavelength
dependent opacity is used to estimate the flux in every wavelength. a semi-
analytical model is constructed, and compared with a set of radiation
hydrodynamical simulations with multiple photon groups. M23 show that the SED
can be described using:

$L_{\nu}=\begin{cases}\left[L_{\rm BB}(0.85\,T_{\rm
col})^{-m}+L_{\nu,\epsilon}^{-m}\right]^{-1/m}&h\nu<3.5T_{\rm col}\\\
1.2\times L_{\rm BB}(0.85R_{13}^{0.13}t_{d}^{-0.13}\times T_{\rm
col})&h\nu>3.5T_{\rm col},\end{cases}$ (A10)

with $m=5$ and

$L_{\rm BB}=L\times\pi B_{\nu}(T_{\rm col})/\sigma T_{\rm col}^{4},$ (A11)
$L_{\nu,\epsilon}=\frac{\left(4\pi\right)^{2}}{\sqrt{3}}r_{col,\nu}^{2}\frac{\sqrt{\epsilon_{\nu}}}{1+\sqrt{\epsilon_{\nu}}}B_{\nu}(T_{col,\nu}),\quad\epsilon_{\nu}=\frac{\kappa_{\rm
ff,\nu}}{\kappa_{\rm ff,\nu}+\kappa_{\rm es}}$ (A12)

and

$r_{\rm col,\nu}=R+2.18\times 10^{13}L_{\rm br,42.5}^{0.48}T_{\rm
br,5}^{-1.97}\kappa_{0.34}^{-0.07}\tilde{t}^{0.80}\nu_{\rm eV}^{-0.08}\,\rm
cm,$ (A13) $T_{\rm col,\nu}=5.47\,L_{\rm br,42.5}^{0.05}T_{\rm
br,5}^{0.92}\kappa_{0.34}^{0.22}\tilde{t}^{-0.42}\nu_{\rm eV}^{0.25}\,\rm eV,$
(A14) $\kappa_{\rm ff}=0.03\,L_{\rm br,42.5}^{-0.37}T_{\rm
br,5}^{0.56}\kappa_{0.34}^{-0.47}\tilde{t}^{-0.19}\nu_{\rm eV}^{-1.66}\,\rm
cm^{2}\,g^{-1}.$ (A15)

Here $L_{\rm br}=L_{\rm br,42.5}10^{42.5}\rm\,erg\,s^{-1}$, $T_{col}=5T_{\rm
col,5}$ eV, and $\nu=\nu_{\rm eV}$ eV, and $R$ in terms of the break
parameters is:

$R=2.41\times 10^{13}\,t_{\rm
br,3}^{-0.1}\,L_{br,42.5}^{0.55}\,T_{br,5}^{-2.21}\,\text{cm}.$ (A16)

####  A.1.3 Fitting procedure

Since the validity of this model is dependent on the model parameters, a
$\chi^{2}$ minimization is not applicable. Instead, we fit this model with a
likelihood function adapted for a variable validity domain, as discussed in
detail in Soumagnac et al. (2020):

$\mathcal{L}={\rm
PDF}\left(\chi^{2},dof\right)=\frac{\left(\chi^{2}\right)^{\frac{N}{2}-1}\exp\left(\frac{\chi^{2}}{2}\right)}{2^{\frac{N}{2}}\Gamma\left(\frac{N}{2}\right)}$
(A17)

where $\chi^{2}$ is the $\chi^{2}$ statistic, PDF is the $\chi^{2}$
distribution given the number of degrees of freedom, and $\Gamma$ is the gamma
function. We calculate the $\chi^{2}$ statistic using the observational errors
and an empirical covariance matrix:

$\chi^{2}=\left(f_{i}-m_{i}\right)\left(COV_{ij}\right)^{-1}\left(f_{j}-m_{j}\right)$
(A18)

$f_{i}$ are the observed fluxes, $m_{i}$ are the integrated synthetic fluxes
for the model. The covariance matrix $COV_{ij}$ is calculated using the
observational errors $\sigma_{i}$ and an empirical covariance calculated over
the hydrodynamical simulation sample.

$COV=1.5COV_{sys}+\frac{1}{\boldsymbol{\sigma}_{obs}^{2}}$ (A19)
$COV_{sys,ij}=\left\langle r_{i}r_{j}\right\rangle-\left\langle
r_{i}\right\rangle\left\langle r_{j}\right\rangle;\,\,r_{i}=f_{i}-m_{i}$ (A20)

Here $\sigma_{i}$ include a 10 % systematic error to account for cross-
instrument calibration, and we scale $COV_{sys}$ by a factor 1.5 to account
for the theoretical uncertainty, assumed to have the same covariance structure
as the theoretical calibration uncertainty. This covariance matrix is
constructed for every SN data set separately. For every SN, a synthetic
dataset in created using the sampling and bands available in its individual
dataset. The average

###  A.2 Early-time Colors

Table 5: SNe II early-time colors

t [rest-frame days] | Filter |  $\lambda_{piv}$ [Å] |  $W_{eff}$ [Å] | Mean $m_{\lambda}-m_{r}$ [mag] | STD [mag] | Bluest color [mag] | Reddest color [mag] | $N_{SN}$
---|---|---|---|---|---|---|---|---
1 | UVW2 | 2055 | 305 | -0.70 | 0.27 | -1.13 | -0.49 | 5
1 | UVM2 | 2246 | 259 | -0.70 | 0.30 | -1.12 | -0.32 | 5
1 | UVW1 | 2580 | 397 | -0.57 | 0.25 | -0.97 | -0.35 | 5
1 | u | 3467 | 352 | -0.53 | 0.20 | -0.82 | -0.34 | 5
1 | g | 4702 | 641 | -0.24 | 0.09 | -0.43 | -0.05 | 18
1 | i | 7489 | 767 | 0.27 | 0.15 | 0.14 | 0.60 | 6
2 | UVW2 | 2055 | 305 | -0.67 | 0.27 | -1.30 | -0.18 | 23
2 | UVM2 | 2246 | 259 | -0.64 | 0.28 | -1.23 | -0.02 | 22
2 | UVW1 | 2580 | 397 | -0.59 | 0.22 | -1.17 | -0.20 | 23
2 | u | 3467 | 352 | -0.59 | 0.21 | -0.95 | -0.12 | 23
2 | g | 4702 | 641 | -0.27 | 0.11 | -0.44 | 0.06 | 30
2 | i | 7489 | 767 | 0.27 | 0.23 | 0.08 | 0.98 | 22
3 | UVW2 | 2055 | 305 | -0.33 | 0.30 | -0.89 | 0.24 | 30
3 | UVM2 | 2246 | 259 | -0.37 | 0.30 | -0.94 | 0.14 | 30
3 | UVW1 | 2580 | 397 | -0.36 | 0.24 | -0.93 | 0.12 | 30
3 | u | 3467 | 352 | -0.45 | 0.24 | -1.05 | 0.16 | 30
3 | g | 4702 | 641 | -0.18 | 0.12 | -0.45 | 0.10 | 31
3 | i | 7489 | 767 | 0.23 | 0.21 | 0.00 | 0.93 | 25
4 | UVW2 | 2055 | 305 | -0.01 | 0.35 | -0.57 | 0.68 | 29
4 | UVM2 | 2246 | 259 | -0.13 | 0.31 | -0.71 | 0.39 | 29
4 | UVW1 | 2580 | 397 | -0.17 | 0.28 | -0.73 | 0.29 | 29
4 | u | 3467 | 352 | -0.34 | 0.25 | -1.01 | 0.28 | 30
4 | g | 4702 | 641 | -0.14 | 0.10 | -0.39 | 0.02 | 31
4 | i | 7489 | 767 | 0.23 | 0.15 | -0.02 | 0.80 | 24
5 | UVW2 | 2055 | 305 | 0.31 | 0.35 | -0.29 | 0.98 | 27
5 | UVM2 | 2246 | 259 | 0.13 | 0.29 | -0.45 | 0.62 | 26
5 | UVW1 | 2580 | 397 | 0.01 | 0.22 | -0.45 | 0.47 | 28
5 | u | 3467 | 352 | -0.25 | 0.21 | -0.51 | 0.41 | 28
5 | g | 4702 | 641 | -0.12 | 0.09 | -0.28 | 0.10 | 29
5 | i | 7489 | 767 | 0.21 | 0.10 | -0.00 | 0.42 | 23

aafootnotetext:

Figure 23: The full ZTF $g$-band and $r$-band light curves of our sample of 34
SNe II.