Fine-Grained Complexity for Sparse Graphs
Udit Agarwal

⋆

and Vijaya Ramachandran∗

arXiv:1611.07008v3 [] 19 Oct 2017

October 20, 2017

Abstract
We consider the fine-grained complexity of sparse graph problems that currently have Õ(mn)
time algorithms, where m is the number of edges and n is the number of vertices in the input
graph. This class includes several important path problems on both directed and undirected
graphs, including APSP, MWC (minimum weight cycle), and Eccentricities, which is the problem
of computing, for each vertex in the graph, the length of a longest shortest path starting at that
vertex.
We introduce the notion of a sparse reduction which preserves the sparsity of graphs, and
we present near linear-time sparse reductions between various pairs of graph problems in the
Õ(mn) class. Surprisingly, very few of the known nontrivial reductions between problems in the
Õ(mn) class are sparse reductions. In the directed case, our results give a partial order on a
large collection of problems in the Õ(mn) class (along with some equivalences), and many of our
reductions are very nontrivial. In the undirected case we give two nontrivial sparse reductions:
from MWC to APSP, and from unweighted ANSC (all nodes shortest cycles) to a natural variant
of APSP. The latter reduction also gives an improved algorithm for ANSC (for dense graphs).
We propose the MWC Conjecture, a new conditional hardness conjecture that the weight of
a minimum weight cycle in a directed graph cannot be computed in time polynomially smaller
than mn. Our sparse reductions for directed path problems in the Õ(mn) class establish that
several problems in this class, including 2-SiSP (second simple shortest path), s-t Replacement
Paths, Radius, and Eccentricities, are MWCC hard. We also identify Eccentricities as a key
problem in the Õ(mn) class which is simultaneously MWCC-hard, SETH-hard and k-DSH-hard,
where SETH is the Strong Exponential Time Hypothesis, and k-DSH is the hypothesis that a
dominating set of size k cannot be computed in time polynomially smaller than nk .
Our framework using sparse reductions is very relevant to real-world graphs, which tend to
be sparse and for which the Õ(mn) time algorithms are the ones typically used in practice, and
not the Õ(n3 ) time algorithms.

∗

Dept.
of Computer Science, University of Texas, Austin TX 78712.
Email: udit@cs.utexas.edu,
vlr@cs.utexas.edu. This work was supported in part by NSF Grant CCF-1320675. The first author’s research
was also supported in part by a Calhoun Fellowship.

0

1

Introduction

In recent years there has been considerable interest in determining the ﬁne-grained complexity of
problems in P, see e.g. [40]. For instance, the 3SUM [15] and OV (Orthogonal Vectors) [41, 11]
problems have been central to the ﬁne-grained complexity of several problems with quadratic time
algorithms, in computational geometry and related areas for 3SUM and in edit distance and related
areas for OV. APSP (all pairs shortest paths) has been central to the ﬁne-grained complexity of
several path problems with cubic time algorithms on dense graphs [42]. 3SUM has a quadratic time
algorithm but no sub-quadratic (i.e., O(n2−ǫ ) for some constant ǫ > 0) time algorithm is known. It
has been shown that a sub-quadratic time algorithm for any of a large number of problems would
imply a sub-quadratic time algorithm for 3SUM [15, 41]. In a similar vein no sub-quadratic time
algorithm is known for OV, and it has been shown that a sub-quadratic time algorithm for LCS or
Edit Dis tance would imply a sub-quadratic time algorithm for ﬁnding orthogonal vectors (OV) [11].
For several graph problems related to shortest paths that currently have Õ(n3 ) 1 time algorithms,
equivalence under sub-cubic reductions has been shown in work starting with [42]: between all pairs
shortest paths (APSP) in either a directed or undirected weighted graph, ﬁnding a second simple
shortest path from a given vertex u to a given vertex v (2-SiSP) in a weighted directed graph,
ﬁnding a minimum weight cycle (MWC) in a directed or undirected graph, ﬁnding a minimum
weight triangle (Min-Wt-∆), and a host of other problems. This gives compelling evidence that a
large class of problems on dense graphs is unlikely to have sub-cubic algorithms as a function of n,
the number of vertices, unless fundamentally new algorithmic techniques are developed.
The Strong Exponential Time Hypothesis (SETH) [22] states that for every δ < 1, there is a k
such that k-SAT cannot be solved in O(2δ·n ) time. It has been shown that a sub-quadratic time
algorithm for OV would falsify SETH [41]. No hardness results relative to SETH are known for
either 3SUM or cubic APSP, and the latter problem, in fact, does not have a SETH hardness result
for deterministic algorithms unless NSETH, a nondeterministic version of SETH, is falsiﬁed [13].
Other hardness conjectures have been proposed, for instance, for k Clique [1] and for k Dominating
Set (k-DSH) [31].
In this paper we consider a central collection of graph problems related to APSP, which reﬁnes the
subcubic equivalence class. We let n be the number of vertices and m the number of edges. All of
the sub-cubic equivalent graph problems mentioned above (and several others) have Õ(mn) time
algorithms; additionally, many sub-cubic equivalent problems related to minimum triangle detection
and triangle listing have lower O(m3/2 ) time complexities for sparse graphs [23]. (Checking whether
a graph contains a triangle has an even faster O(m1.41 ) time algorithm [9] but can also be computed
in sub-cubic time using fast matrix multiplication.) For APSP with arbitrary edge weights, there is
an O(mn+n2 log log n) time algorithm for directed graphs [32] and an even faster O(mn log α(m, n))
time algorithm for undirected graphs [33], where α is a certain natural inverse of the Ackermann’s
function. (For integer weights, there is an O(mn) time algorithm for undirected graphs [39] and
an O(mn + n2 log log n) time algorithm for directed graphs [19].) When a graph is truly sparse
with m = O(n) these bounds are essentially optimal or very close to optimal, since the size of the
output for APSP is n2 . Thus, a cubic in n bound for APSP does not fully capture what is currently
achievable by known algorithms, especially since graphs that arise in practice tend to have m close
to linear in n or at least are sparse, i.e., have m = O(n1+δ ) for δ < 1. This motivates our study of
the ﬁne-grained complexity of graph path problems that currently have Õ(mn) time algorithms.
1

Õ and Θ̃ can hide sub-polynomial factors; in our new results they only hide polylog factors.

1

Another fundamental problem in the Õ(mn) class is MWC (Minimum Weight Cycle). In both
directed and undirected graphs, MWC can be computed in Õ(mn) time using an algorithm for
APSP. Very recently Orlin and Sedeno-Noda gave an improved O(mn) time algorithm [29] for
directed MWC. This is an important result but the bound still remains Ω(mn). Finding an MWC
algorithm that runs faster than mn time is a long-standing open problem in graph algorithms.
Fine-grained reductions and hardness results with respect to time bounds that consider only n or
only m, such as bounds of the form m2 , n2 , nc , m1+δ , are given in [34, 6, 4, 5, 21]. One exception is
in [3] where some reductions are given for problems with Õ(mn) time algorithms, such as diameter
and some betweenness centrality problems, that preserve graph sparsity. Several other related
results on ﬁne-grained complexity are in [21, 43, 30, 27, 24, 10, 5, 4, 6, 40].
In this paper we present both ﬁne-grained reductions and hardness results for graph problems with
Õ(mn) time algorithms, most of which are equivalent under sub-cubic reductions on dense graphs,
but now taking sparseness of edges into consideration. We use the current long-standing upper
bound of Õ(mn) for these problems as our reference, both for our ﬁne-grained reductions and for
our hardness results. Our results give a partial order on hardness of several problems in the Õ(mn)
class, with equivalence within some subsets of problems, and a new hardness conjecture (MWCC)
for this class.
Our results appear to the ﬁrst that consider a hardness class with respect to two natural parameters
in the input (the Õ(mn) class in our case). Further, the Õ(mn) time bound has endured for a long
time for a large collection of important problems, and hence merits our detailed study.

2

Our Contributions

We will deal with either an unweighted graph G = (V, E) or a weighted graph G = (V, E, w), where
the weight function is w : E → R+ . We assume that the vertices have distinct labels with ⌈log n⌉
bits. Let M and m denote the largest and the smallest edge weight, and let the edge weight ratio
be ρ = M /m . Let dG (x, y) denote the length (or weight) of a shortest path from x to y in G, and
for a cycle C in G, let dC (x, y) denote the length of the shortest path from x to y in C. We deal
with the APSP problem2 whose output is the shortest path weights for all pairs of vertices, together
with a concise representation of the shortest paths, which in our case is an n × n matrix, LastG ,
that contains, in position (x, y), the predecessor vertex of y on a shortest path from x to y. We also
consider the APSD (All Pairs Shortest Distances) problem [16] 2 which only involves computing
the weights of the shortest paths. Most of the currently known APSD algorithms, including matrix
multiplication based methods for small integer weights [37, 38, 45], can compute APSP in the same
bound as APSD. We deal with only simple graphs in this paper.
I. Sparse Reductions and the mn Partial Order. In Deﬁnition 2.1 below, we deﬁne the notion of a sparsity preserving reduction (or sparse reduction for short) from a graph problem P to
a graph problem Q that allows P to inherit Q’s time bound for the graph problem as a function
of both m and n, as long as the reduction is eﬃcient. Our deﬁnition is in the spirit of a Karp
reduction [25], but slightly more general, since we allow a constant number of calls to Q instead of
just one call in a Karp reduction (and we allow polylog calls for Õ(·) bounds).
2

In an earlier version of this write-up, we used APSP′ for APSP, and APSP for APSD, respectively.

2

Reduction
MWC
≤ APSD
ANSC
(Unweighted)
APSP

Prior Results (Undirected)
2

Õ(n ) reduction [35]
a. goes through Min-Wt-∆
b. Θ(n2 ) edges in reduced graphs
3−ω
Sparse Õ(mn 2 ) reduction [44]
a. randomized
b. polynomial calls to APSP
ω+3
c. gives randomized Õ(n 2 )
time algorithm [44]

New Results (Undirected)
Sparse Õ(n2 ) Reduction
a. no intermediate problem
b. Θ(m) edges in reduced graphs
Sparse Õ(n2 ) Reduction
a. deterministic
b. Õ(1) calls to APSP
c. gives deterministic Õ(nω )
time algorithm

Table 1: Our sparse reduction results for undirected graphs. These results are in Sections 3 and 7. Note
that Min-Wt-∆ can be solved in m3/2 time.

One could consider a more general notion of a sparsity preserving reduction in the spirit of Turing
reductions as in [17] (which considers functions of a single variable n). However, for all of the
many sparsity preserving reductions we present here, the simpler notion deﬁned below suﬃces. It
should also be noted that the simple and elegant deﬁnition of a Karp reduction suﬃces for the
vast majority of known NP-completeness reductions. The key diﬀerence between our deﬁnition and
other deﬁnitions of ﬁne-grained reductions is that it is ﬁne-grained with regard to both m and n,
and respects the dependence on both parameters.
It would interesting to see if some of the open problems left by our work on ﬁne-grained reductions
for the mn class can be solved by moving to a more general sparsity preserving reduction in the
spirit of a Turing reduction applied to functions of both m and n. We do not consider this more
general version here since we do not need it for our reductions.
Definition 2.1 (Sparsity Preserving Graph Reductions). Given graph problems P and Q,
sprs
there is a sparsity preserving f (m, n) reduction from P to Q, denoted by P ≤f (m,n) Q, if given an
algorithm for Q that runs in TQ (m, n) time on graphs with n vertices and m edges, we can solve P
in O(TQ (m, n) + f (m, n)) time on graphs with n vertices and m edges, by making a constant number
of oracle calls to Q.
For simplicity, we will refer to a sparsity preserving graph reduction as a sparse reduction, and we
will say that P sparse reduces to Q . Similar to Deﬁnition 2.1, we will say that P tilde-f (m, n)
sparse reduces to Q, denoted by P .sprs
f (m,n) Q, if, given an algorithm for Q that runs in TQ (m, n)
time, we can solve P in Õ(TQ (m, n) + f (m, n)) time (by making polylog oracle calls to Q on graphs
sprs
∼sprs
with Õ(n) vertices and Õ(m) edges). We will also use ≡sprs
f (m,n) and =f (m,n) in place of ≤f (m,n) and
sprs

.sprs
f (m,n) when there are reductions in both directions. In a weighted graph we allow the Õ term to
have a log ρ factor. (Recall that ρ = M/m.)
We present several sparse reductions for problems that currently have Õ(mn) time algorithms. This
gives rise to a partial order on problems that are known to be sub-cubic equivalent, and currently
have Õ(mn) time algorithms. For the most part, our reductions take Õ(m+n) time (many are in fact
O(m + n) time), except reductions to APSP take Õ(n2 ) time. This ensures that any improvement in
the time bound for the target problem will give rise to the same improvement to the source problem,
to within a polylog factor. Surprisingly, very few of the known sub-cubic reductions carry over to
the sparse case due to one or both of the following features.
1. A central technique used in many of these earlier reductions has been to reduce to or from a
suitable triangle ﬁnding problem. As noted above, in the sparse setting, all triangle ﬁnding and
3

Reduction
MWC
≤ 2-SiSP
2-SiSP
≤ Radius;
≤ BC
Replacement
paths
≤ ANSC;
≤ Eccentricities
ANSC
≤ ANBC

Prior Results (Directed)
Õ(n2 ) reduction [35, 42]
a. goes through Min-Wt-∆
b. Θ(n2 ) edges in reduced graphs
Õ(n2 ) reductions [18, 42, 3]
a. goes through Min-Wt-∆
and a host of other problems
b. Θ(n2 ) edges in reduced graphs
Õ(n2 ) reductions [18, 42, 3]
a. goes through Min-Wt-∆
and a host of other problems
b. Θ(n2 ) edges in reduced graphs
Õ(n2 ) reduction [42, 3]
a. goes through Min-Wt-∆
and a host of other problems
b. Θ(n2 ) edges in reduced graphs

New Results (Directed)
Sparse O(m) Reduction
a. no intermediate problem
b. O(m) edges in reduced graph
Sparse Õ(m) Reduction
a. no intermediate problem
b. Õ(m) edges in reduced graph
Sparse O(m) (Õ(m)) Reduction
to ANSC (Eccentricities)
a. no intermediate problem
b. O(m) edges for ANSC &
Õ(m) edges for Eccentricities in
reduced graph
Sparse Õ(m) Reduction
a. no intermediate problem
b. Õ(m) edges in reduced graphs

Table 2: Our sparse reduction results for directed graphs. These results are in Sections 4, 8 and 9. The
definitions for these problems are in Appendix A.1. Note that Min-Wt-∆ can be solved in m3/2 time.
2SiSC

ANSC

[7]
MWC

2SiSP

s-t replacement
paths

n2
Eccentricities

APSP

Radius

Figure 1: Our sparse reductions for weighted directed graphs (reductions related to centrality problems are in
Figure 8). The regular edges represent sparse O(m + n) reductions, the squiggly edges represent tilde-sparse
O(m + n) reductions, and the dashed edges represent reductions that are trivial. The n2 label on dashed
edge to APSP denotes an O(n2 ) time reduction.

enumeration problems can be computed in Õ(m3/2 ) time, which is an asymptotically smaller bound
than mn when the graph is sparse.
2. Many of the known sub-cubic reductions convert a sparse graph into a dense one, and all known
subcubic reductions from a problem in the mn class to a triangle ﬁnding problem create a dense
graph. If any such reduction had been sparse, it would have given an O(m3/2 ) time algorithm for
a problem whose current fastest algorithm is in the mn class, a major improvement.
We present a suite of new sparse reductions for the Õ(mn) time class. Many of our reductions
are quite intricate, and for some of our reductions we introduce a new technique of bit-sampling
(previously called ‘bit-ﬁxing’ but re-named here to avoid confusion with an un-named technique
used in [3]). The full deﬁnitions of the problems we consider are in the Appendix. Tables 1 and 2
summarize the improvements our reductions achieve over prior results. We now give some highlights
of our results.

4

(a) Sparse Reductions for Undirected Graphs: Finding the weight of a minimum weight
cycle (MWC) is a fundamental problem. A simple sparse O(m + n) reduction from MWC to APSD
is known for directed graph but it does not work in the undirected case mainly because an edge can
be traversed in either direction in an undirected graph, and known algorithms for the directed case
would create non-simple paths when applied to an undirected graph. Roditty and Williams [35],
in a follow-up to [42], pointed out the challenges of reducing from undirected MWC to APSD in
sub-nω time, where ω is the matrix multiplication exponent, and then gave a Õ(n2 ) reduction
from undirected MWC to undirected Min-Wt-∆ in a dense bipartite graph. But a reduction that
increases the density of the graph is not helpful in our sparse setting. Instead, in this paper we
give a sparse Õ(n2 ) time reduction from undirected MWC to APSD. Similar techniques allow us to
obtain a sparse Õ(n2 ) time reduction from undirected ANSC (All Nodes Shortest Cycles) [44, 36],
which asks for a shortest cycle through every vertex) to APSP. This reduction improves the running
time for unweighted ANSC in dense graphs [44], since we can now solve it in Õ(nω ) time using the
unweighted APSP algorithm in [37, 8]. Our ANSC reduction and resulting improved algorithm is
only for unweighted graphs and extending it to weighted graphs appears to be challenging.
We introduce a new bit-sampling technique 3 in these reductions. This technique contains a simple
construction with exactly log n hash functions for Color Coding [9] with 2 colors (described in detail
in Section 3). Our bit-sampling method also gives the ﬁrst near-linear time algorithm for k-SiSC
in weighted undirected graphs. k-SiSC is the cycle variant of k-SiSP [26], and our reduction that
gives a fast algorithm for k-SiSC in weighted undirected graphs is given in Appendix A.2.
Section 3 summarizes the proof of Theorem 2.2 below, and Section 7 proves Theorems 2.2 and 2.3
in full.
Theorem 2.2. In a weighted undirected n-node m-edge graph with edge weight ratio ρ, MWC can
be computed with 2 · log n · log ρ calls to APSD on graphs with 2n nodes, at most 2m edges, and edge
weight ratio at most ρ, with O(n + m) cost for constructing each reduced graph, and with additional
O(n2 · log n · log(nρ)) processing time. Additionally, edge weights are preserved, and every edge in
the reduced graph retains its corresponding edge weight from the original graph. Hence, MWC .sprs
n2
APSD.
In undirected graphs with integer weights at most M , APSD can be computed in Õ(M · nω )
time [37, 38]. In [35], the authors give an Õ(M · nω ) time algorithm for undirected MWC in such
graphs by preprocessing using a result in [28] and then making Õ(1) calls to an APSD algorithm.
By applying our sparse reduction in Theorem 2.2 we can get an alternate simpler Õ(M · nω ) time
algorithm for MWC in undirected graphs (the sparsity of our reduction is not relevant here except
for the fact that it is also an Õ(n2 ) reduction).
The following result gives an improved algorithm for ANSC in undirected unweighted graphs.
sprs

Theorem 2.3. In undirected unweighted graphs, ANSC .sprs
APSP and ANSC can be computed
n2
ω
in Õ(n ) time.
(b) Directed Graphs. We give several nontrivial sparse reductions starting from MWC in directed graphs, as noted in the following theorem (also highlighted in Figure 1).
Theorem 2.4 (Directed Graphs.). In weighted directed graphs:
3

In an earlier version, we called this bit-fixing but that term was often confused with a ‘bit-encoding’ technique
used in [3].

5

sprs

sprs

sprs

sprs

sprs
sprs
sprs
(i) MWC ≤sprs
m+n 2-SiSP ≤m+n s-t replacement paths ≡m+n ANSC .m+n Eccentricities
sprs

sprs

sprs
(ii) 2-SiSP .sprs
m+n Radius ≤m+n Eccentricities
sprs

(iii) 2-SiSP .sprs
m+n Betweenness Centrality
In Section 4 we present a brief overview of our sparse reduction from 2-SiSP to Radius for directed
graphs. The remaining reductions are in Section 8, and in Section 9 we also present nontrivial sparse
reductions from 2-SiSP and ANSC to versions of the betweenness centrality problem, to complement
a collection of sparse reductions in [3] for betweenness centrality problems.
II. Conditional Hardness Results. Conditional hardness under ﬁne-grained reductions falls
into several categories: For example, 3SUM hardness [15] holds for several problems to which
3SUM reduces in sub-quadratic time, and OV-hardness holds for several problems to which OV
has sub-quadratic reductions. By a known reduction from SETH to OV [41] OV-hardness implies
SETH-hardness as well. The n3 equivalence class for path problems in dense graphs [42] gives
sub-cubic hardness for APSP in dense graphs and for the other problems in this class.
In this paper our focus is on the mn class, the class of graph path problems for which the current
best algorithms run in Õ(mn) time. This class diﬀers from all previous classes considered for ﬁnegrained complexity since it depends on two parameters of the input, m and n. To formalize hardness
results for this class we ﬁrst make precise the notion of a sub-mn time bound, which we capture
with the following deﬁnition.
Definition 2.5 (Sub-mn). A function g(m, n) is sub-mn if g(m, n) = O(mα · nβ ), where α, β are
constants such that α + β < 2.
A straightforward application of the notions of sub-cubic and sub-quadratic to the two-variable
function mn would have resulted in a simpler but less powerful deﬁnition for sub-mn, namely that
of requiring a time bound O((mn)δ ), for some δ < 1. Another weaker form of the above deﬁnition
would have been to require α ≤ 1 and β ≤ 1 with at least one of the two being strictly less than 1.
The above deﬁnition is more general than either of these. It considers a bound of the form m3 /n2
to be sub-mn even though such a bound for the graph problem with be larger than n3 for dense
graphs. Thus, it is a very strong deﬁnition of sub-mn when applied to hardness results. (Such a
deﬁnition could be abused when giving sub-mn reductions, but as noted in part I above, all of our
sub-mn reductions are linear or near-linear in the sizes of input and output, and thus readily satisfy
the sub-mn deﬁnition while being very eﬃcient.)
Based on our ﬁne-grained reductions for directed graphs, we propose the following conjecture:
Conjecture 1. (MWCC: Directed Min-Wt-Cycle Conjecture) There is no sub-mn time algorithm
for MWC (Minimum Weight Cycle) in directed graphs.
Directed MWC is a natural candidate for hardness for the mn class since it is a fundamental
problem for which a simple Õ(mn) time algorithm has been known for many decades, and very
recently, an O(mn) time algorithm [29]. But a sub-mn time algorithm remains as elusive as ever.
Further, through the ﬁne-grained reductions that we present in this paper, many other problems in
the mn class have MWCC hardness for sub-mn time as noted in the following theorem.

6

Theorem 2.6. Under MWCC, the following problems on directed graphs do not have sub-mn time
algorithms: 2-SiSP, 2-SiSC, s-t Replacement Paths, ANSC, Radius, Betweenness Centrality, and
Eccentricities.
The problems in the above theorem are a subset of the problems that are sub-cubic equivalent to
directed MWC, and hence one could also strengthen the MWCC conjecture to state that directed
MWC has neither a sub-mn time algorithm nor a subcubic (in n) time algorithm. As noted above,
these two classes of time bounds are incomparable as neither one is contained in the other.
SETH and Related Problems. Recall that SETH conjectures that for every δ < 1 there exists
a k such that there is no ‘2δ·n ’ time algorithm for k-SAT. No SETH-based conditional lower bound
is known for either 3SUM or for dense APSP. In fact, it is unlikely that dense APSP would have
a hardness result for deterministic sub-cubic algorithms, relative to SETH, since this would falsify
NSETH [13].
Despite the above-mentioned negative result in [13] for SETH hardness for sub-cubic equivalent
problems, we now observe that SETH-hardness does hold for a key MWCC-hard problem in the mn
class. In particular we observe that a SETH hardness construction, used in [34] to obtain sub-m2
hardness for Eccentricities in graphs with m = O(n), can be used to establish the following result.
Theorem 2.7 (Sub-mn Hardness Under SETH). Under SETH, Eccentricities does not have a
sub-mn time algorithm in an unweighted or weighted graph, either directed or undirected.
The k Dominating Set Hypothesis (k-DSH) [31] states that there exists k0 (k0 = 3 in [31]) such
that for all k ≥ k0 , a dominating set of size k in an undirected graph on n vertices cannot be found
in O(nk−ǫ ) for any constant ǫ > 0. This conjecture formalizes a long-standing open problem, and
it was shown in [31] that falsifying k-DSH would falsify SETH.
For even values of k, it was shown in [34] that solving Eccentricities in O(m2−ǫ ) time, for any
constant ǫ > 0, would falsify k-DSH. We extend this result to all values of k, both odd and even,
and establish it for the sub-mn class (which includes O(m2−ǫ )), to obtain the following theorem.
Theorem 2.8 (Conditional Hardness Under k-DSH). Under k-DSH, Eccentricities does not
have a sub-mn time algorithm in an unweighted or weighted graph, either directed or undirected.
More precisely, if Eccentricities can be solved in O(mα n2−α−ǫ ) time, then for any k ≥ 3 + (2α/ǫ),
a dominating set of size k can be found in O(nk−ǫ ) time.
We give the proof of Theorem 2.8 in Section 5, and this also establishes Theorem 2.7, since hardness
under k-DSH implies hardness under SETH.
Eccentricities as a Central Problem for mn. We observe that directed Eccentricities is a
central problem in the mn class: If a sub-mn time algorithm is obtained for directed Eccentricities,
not only would it refute k-DSH, SETH and MWCC (Conjecture 1), it would also imply sub-mn time
algorithms for several MWCC-hard problems: 2-SiSP, 2-SiSC, s-t Replacement Paths, ANSC and
Radius in directed graphs as well as Radius and Eccentricities in undirected graphs. (The undirected
versions of 2-SiSP, 2-SiSC, and s-t Replacement Paths have near-linear time algorithms and are not
relevant, and there is no known sparse reduction from undirected ANSC to Eccentricities.)
APSP. APSP has a special status in the mn class. Since its output size is n2 , it has near-optimal
algorithms [39, 19, 32, 33] for graphs with m = O(n). Also, the n2 size for the APSP output means
7

that any inference made through sparse reductions to APSP will not be based on a sub-mn time
bound but instead on a sub-mn + n2 time bound. It also turns out that the SETH and k-DSH
hardness results for Eccentricities depend crucially on staying with a purely sub-mn bound, and
hence even though Eccentricities has a simple sparse n2 reduction to APSP, we do not have SETH
or k-DSH hardness for computing APSP in sub-mn + n2 time.
Betweenness Centrality (BC). We discuss this problem in Section 9. Sparse reductions for
several variants of BC were given in [3] but none established MWCC-hardness. In Section 9 we give
nontrivial sparse reductions to establish MWCC hardness for some important variants of BC.
Time Bounds for Sparse Graphs and their Separation under SETH. It is readily seen
that the Õ(m3/2 ) bound for triangle ﬁnding problems is a better bound than the Õ(mn) bound for
the mn class. But imposing a total ordering on functions of two variables requires some care. For
example, maximal 2-connected subgraphs of a given directed graph can be computed in O(m3/2 )
time [14] as well as in O(n2 ) time [20]. Here, m3/2 is a better bound for very sparse graphs, and
n2 for very dense graphs. In Section 6 we give natural deﬁnition of what it means for for one time
bound to be smaller than another time bound for sparse graphs. By our deﬁnitions in Section 6,
m3/2 is a smaller time bound than both mn and n2 for sparse graphs. Our deﬁnitions in Section 6,
in conjunction with Theorem 2.7, establish that the problems related to triangle listing must have
provably smaller time bounds for sparse graphs than Eccentricities under k-DSH or SETH.
Sub-cubic equivalence for Õ(n3 ) versus the sub-mn Partial Order for Õ(mn). Our sparse
reductions give a partial order on hardness for several graph problems with Õ(mn) time bounds,
and a hardness conjecture for directed graphs relative to a speciﬁc problem MWC. While this
partial order may appear to be weaker than the sub-cubic equivalence class of problems with Õ(n3 )
time bound for n-node graphs [42], we also show that under SETH or k-DSH there is a provable
separation between Eccentricities, a problem in the Õ(mn) partial order, and the O(m3/2 ) class
of triangle ﬁnding problems, even though all of these problems are equivalent under sub-cubic
reductions. Thus, if we assume SETH, the equivalences achieved under sub-cubic reductions cannot
hold for the sparse versions of the problems (i.e., when parameterized by both m and n).
The results for conditional hardness relative to SETH and k-DSH are fairly straightforward, and
they adapt earlier hardness results to our framework. The signiﬁcance of these hardness results is
in the new insights they give into our inability to make improvements to some long-standing time
bounds for important problems on sparse graphs. On the other hand, many of our sparse reductions
are highly intricate, and overall these reductions give a partial order (with several equivalences) on
the large class of graph problems that currently have Õ(mn) time algorithms.
Roadmap. The rest of the paper is organized as follows. Sections 3 and 4 present key examples
of our sparse reductions for undirected and directed graphs, with full details in Sections 7 and 8.
In Sections 5 and 6 we present SETH and k-DSH hardness results, and the resulting provable split
of the sub-cubic equivalence class under these hardness results for sparse time bounds. Section 9
discusses betweenness centrality. The Appendix gives the deﬁnitions of the problems we consider.

3

sprs

Weighted Undirected Graphs: MWC .sprs
n2 APSD

In undirected graphs, the only known sub-cubic reduction from MWC to APSD [35] uses a dense
reduction to Min-Wt-∆. Described in [35] for integer edge weights of value at most M , it ﬁrst uses
8

an algorithm in [28] to compute, in O(n2 · log n log nM ) time, a 2-approximation W to the weight
of a minimum weight cycle as well as shortest paths between all pairs of vertices with pathlength
at most W/2. The reduced graph for Min-Wt-∆ is constructed as a (dense) bipartite graph with
edges to represent all of these shortest paths, together with the edges of the original graph in one
side of the bipartition. This results in each triangle in the reduced graph corresponding to a cycle
in the original graph, and with a minimum weight cycle guaranteed to be present as a triangle. An
MWC is then constructed using a simple explicit construction for Color Coding [35] with 2 colors.
The approach in [35] does not work in our case, as we are dealing with sparse reductions. Instead,
we give a sparse reduction directly from MWC to APSD. In contrast to [35], where ﬁnding a
minimum weight 3-edge triangle gives the MWC in the original graph, in our reduction the MWC
is constructed as a path P in a reduced graph followed by a shortest path in the original graph.
One may ask if we can sparsify the dense reduction from MWC to Min-Wt-∆ in [35], but such
a reduction, though very desirable, would immediately refute MWCC and would achieve a major
breakthrough by giving an Õ(m3/2 ) time algorithm for undirected MWC.
We now sketch our sparse reduction from undirected MWC to APSP. (In Section 7 we reﬁne this
to a sparse reduction to APSD.) It is well known that in any cycle C = hv1 , v2 , . . . , vl i in a weighted
undirected graph G = (V, E, w) there exists an edge (vi , vi+1 ) on C such that ⌈ w(C)
2 ⌉ − w(vi , vi+1 ) ≤
w(C)
w(C)
w(C)
dC (v1 , vi ) ≤ ⌊ 2 ⌋ and ⌈ 2 ⌉ − w(vi , vi+1 ) ≤ dC (vi+1 , v1 ) ≤ ⌊ 2 ⌋. The above edge, (vi , vi+1 ), is
called the critical edge of C with respect to the start vertex v1 in [35].
We will make use of the following simple observation proved in Section 7.
Observation 3.1. Let G = (V, E, w) be a weighted undirected graph. Let C = hv1 , v2 , . . . , vl i be a
minimum weight cycle in G, and let (vp , vp+1 ) be its critical edge with respect to v1 . WLOG assume
that dG (v1 , vp ) ≥ dG (v1 , vp+1 ). If G′ is obtained by removing edge (vp−1 , vp ) from G, then the path
P = hv1 , vl , . . . , vp+1 , vp i is a shortest path from v1 to vp in G′ .
In our reduction we construct a collection of graphs Gi,j,k , each with 2n vertices (containing 2 copies
of V ) and O(m) edges, with the guarantee that, for the minimum weight cycle C, in at least one of
the graphs the edge (vp−1 , vp ) (in Observation 3.1) will not connect across the two copies of V and
the path P of Observation 3.1 will be present. Then, if a call to APSP computes P as a shortest
path from v1 to vp (across the two copies of V ), we can verify that edge (vp , vp+1 ) is not the last
edge on the computed shortest path from v1 to vp in G, and so we can form the concatenation of
these two paths as a possible candidate for a minimum weight cycle. The challenge is to construct
a small collection of graphs where we can ensure that the path we identify in one of the derived
graphs is in fact the simple path P in the input graph.
Each Gi,j,k has two copies of each vertex u ∈ V , u1 ∈ V1 and u2 ∈ V2 . All edges in G are present on
the vertex set V1 , but there is no edge that connects any pair of vertices within V2 . In Gi,j,k there
is an edge from u1 ∈ V1 to v 2 ∈ V2 iﬀ there is an edge from u to v in G, and u’s i-th bit is j, and
M
M
< w(u, v) ≤ 2k−1
. All the edges in Gi,j,k retain their weights from G. Thus, the edge (u1 , v 2 ) is
2k
present in Gi,j,k with weight w only if (u, v) is an edge in G with the same weight w and further,
certain conditions (as described above) hold for the indices i, j, k. Here, 1 ≤ i ≤ ⌈log n⌉, j ∈ {0, 1}
and k ∈ {1, 2, . . . , ⌈log ρ⌉}, so we have 2 · log n · log ρ graphs. Figure 2 depicts the construction of
graph Gi,j,k .
The ﬁrst condition for an edge (u1 , v 2 ) to be present in Gi,j,k is that u’s i-th bit must be j. This
1 , v 2 ) is absent and the edge (v 1 , v 2 ) is present
ensures that there exist a graph where the edge (vp−1
p
p+1 p
9

u1
w(u, a)

all
edges
from
E

(u1 , v2 ) present if (u, v) ∈ E
and u’s i-th bit is j
M
and 2Mk < w(u, v) ≤ 2k−1

v2

a1
c1
f1

V1

w(f, g)

g2
V2

no edges
between
vertices in
V2

Figure 2: Construction of Gi,j,k .

(as vp−1 and vp+1 diﬀer on at least 1 bit). To contrast with a similar step in [35], we need to ﬁnd
the path P in the sparse derived graph, while in [35] it suﬃces to look for the 2-edge path that
represents P in a triangle in their dense reduced graph.
M
< w(u, v) ≤ 2k−1
— ensures that
The second condition — that an edge (u1 , v 2 ) is present only if M
2k
2
1 , v 2 ) is absent
1
there is a graph Gi,j,k in which, not only is edge (vp+1 , vp ) is present and edge (vp−1
p
as noted by the ﬁrst condition, but also the shortest path from v11 to vp2 is in fact the path P in
Observation 3.1, and does not correspond to a false path where an edge in G is traversed twice. In
particular, we show that this second condition allows us to exclude a shortest path from v11 to vp2 of
the following form: take the shortest path from v1 to vp in G on vertices in V1 , then take an edge
(vp1 , x1 ), and then the edge (x1 , vp2 ). Such a path, which has weight dC (v1 , vp ) + 2w(x, vp ), could
be shorter than the desired path, which has weight dC (v1 , vp+1 ) + w(vp+1 , vp ). In our reduction
we avoid selecting this ineligible path by requiring that the weight of the selected path should not
exceed dG (v1 , vp ) by more than M/2k−1 . We show that these conditions suﬃce to ensure that P is
identiﬁed in one of the Gi,j,k , and no spurious path of shorter length is identiﬁed. Notice that, in
contrast to [35], we do not estimate the MWC weight by computing a 2-approximation. Instead,
this second condition allows us to identify the critical edge in the appropriate graph.

The following lemma establishes the correctness of the resulting sparse reduction described in
Algorithm MWC-to-APSP. The proof and full details are in Section 7, where Figure 4 illustrates
how Observation 3.1 applies to the MWC in a suitable Gi,j,k .
Lemma 3.2. Let C = hv1 , v2 , . . . , vl i be a minimum weight cycle in G and let (vp , vp+1 ) be its
critical edge with respect to the start vertex v1 . Assume dG (v1 , vp ) ≥ dG (v1 , vp+1 ). Then there exist
i ∈ {1, . . . , ⌈log n⌉}, j ∈ {0, 1} and k ∈ {1, 2, . . . , ⌈log ρ⌉} such that the following conditions hold:
(i) dGi,j,k (v11 , vp2 ) + dG (v1 , vp ) = w(C);
(ii) LastGi,j,k (v11 , vp2 ) 6= LastG (v1 , vp );
M
.
(iii) dGi,j,k (v11 , vp2 ) ≤ dG (v1 , vp ) + 2k−1
The converse also holds: If there exist vertices y, z in G with the above three properties satisfied for
y = v1 , z = vp for one of the graphs Gi,j,k using a weight wt in place of w(C) in part 1, then there
exists a cycle in G that passes through z of weight at most wt.

10

MWC-to-APSP(G)
1: wt ← ∞
2: for 1 ≤ i ≤ ⌈log n⌉, j ∈ {0, 1}, and 1 ≤ k ≤ ⌈log ρ⌉ do
3:
Compute APSP on Gi,j,k
4:
for y, z ∈ V do
M
5:
if dGi,j,k (y 1 , z 2 ) ≤ dG (y, z) + 2k−1
then check if LastGi,j,k (y 1 , z 2 ) 6= LastG (y, z)
6:
if both checks in Step 5 hold then wt ← min(wt, dGi,j,k (y 1 , z 2 ) + dG (y, z))
7: return wt

Bit-sampling and Color Coding: Color Coding is a method introduced by Alon, Yuster and
Zwick [9]. For the special case of 2 colors, the method constructs a collection C of O(log n) diﬀerent
2-colorings on an n-element set V , such that for every pair {x, y} in V , there is a 2-coloring in C
that assigns diﬀerent colors to x and y. When the elements of V have unique log n-bit labels, e.g.,
by numbering them from 0 to n − 1, our bit-sampling method on index i (ignoring indices j and
k) can be viewed as an explicit construction of exactly ⌈log n⌉ hash functions for the 2-perfect hash
family: the i-th hash function assigns to each element the i-th bit in its label as its color.
In our construction we actually use 2 log n functions (using both i and j) since we need a stronger
version of color coding where, for any pair of vertices x, y, there is a hash function that assigns
color 0 to x and 1 to y and another that assigns 1 to x and 0 to y. This is needed in order to
1 , v 2 ) is absent and the edge (v 1 , v 2 ) is
ensure that when x = vp−1 and y = vp+1 , the edge (vp−1
p
p+1 p
present. A diﬀerent variant of Color Coding with 2 colors is used in [35] in their dense reduction
from undirected MWC to Min-Wt-∆, and we do not immediately see how to apply our bit-sampling
technique there.
Our bit-sampling method diﬀers from a ‘bit-encoding’ technique used in some reductions in [3, 2],
where the objective is to preserve sparsity in the constructed graph while also preserving paths
from the original graph G = (V, E). This technique creates paths between two copies of V by
adding Θ(log n) new vertices with O(log n) bit labels, and using the O(log n) bit labels on these
new vertices to induce the desired paths in the constructed graph. The bit-encoding technique
(from [3]) is useful for certain types of reductions, and we use it in our sparse reduction from 2-SiSP
to Radius in Section 4, and from 2-SiSP to BC in Section 9.
However, the bit-sampling technique we use in our reduction here is diﬀerent. Here the objective
is to selectively sample the edges from the original graph to be placed in the reduced graph, based
on the bit-pattern of the end points and the edge weight. In our construction, we create Θ(log n)
diﬀerent graphs, where in each graph the copies of V are connected by single-edge paths, without
requiring additional intermediate vertices.

4

Weighted Directed Graphs: 2-SiSP .sprs
m+n Radius

A sparse O(n2 ) reduction from 2-SiSP to APSP was given in [18]. Our sparse reduction from 2-SiSP
to Radius reﬁnes this result and the sub-mn partial order by plugging the Radius and Eccentricities
problems within the sparse reduction chain from 2-SiSP to APSP. Also, in Section 8 we show MWC
≤sprs
m+n 2-SiSP, thus establishing MWC-hardness for both 2-SiSP and Radius. Our 2-SiSP to Radius
reduction here is unrelated to the sparse reduction in [18] from 2-SiSP to APSP.
A sub-cubic reduction from Min-Wt-∆ to Radius is in [3]. This reduction transforms the problem
of ﬁnding a minimum weight triangle to the problem of computing Radius by creating a 4-partite
11

dG (s, v1 )

dG (v2 , t)

v1
G

v2

v0 (s)

v3 (t)
dG (v1z, t)

0
z0o

z1o

0i

0

0

0

z1i
0

0

0

y0o

0

0
z2i

0
y1o

y0i

A

(s, v2 )
zd2G
o

y1i

y2o

y2i

B

C1,0

C1,1

C2,0

C2,1

1
′
′
Figure 3: G′′ for l = 3. The gray and the bold edges have weight 11
9 M and 3 M respectively. All the
outgoing (incoming) edges from (to) A have weight 0 and the outgoing edges from B have weight M ′ .

graph. However, in order to use this reduction to show MWC hardness of the Radius problem we
would need to show that Min-Wt-∆ is MWC-hard. But such a reduction would give an O(m3/2 )
time algorithm for MWC, thus refuting the MWC Conjecture. Instead, we present a more complex
reduction from 2-SiSP, which is MWC-hard (as shown in Section 8).
The input is G = (V, E, w), with source s and sink t in V , and a shortest path P (s = v0 → v1
vl−1 → vl = t). We need to compute a second simple s-t shortest path.

Figure 3 gives an example of our reduction to an input G′′ to the Radius problem for l = 3. In
G′′ we ﬁrst map every edge (vj , vj+1 ) lying on P to the vertices zjo and zji such that the shortest
path from zjo to zji corresponds to the shortest path from s to t avoiding the edge (vj , vj+1 ). We
then add vertices yjo and yji in the graph and connect them to vertices zjo and zji by adding edges
(yjo , zjo ) and (yji , zji ), and then additional edges from yjo to other yko and yki vertices such that the
longest shortest path from yjo is to the vertex yji , which in turn corresponds to the shortest path
from zjo to zji . In order to preserve sparsity, we have an interconnection from each yjo vertex to all
yki vertices (except for k = j) with a sparse construction by using 2 log n additional vertices Cr,s
in a manner similar to a bit-encoding technique used in [3] in their reduction from Min-Wt-∆ to
Betweenness Centrality (this technique however, is diﬀerent from the new ‘bit-ﬁxing’ technique used
in Section 3), and we have two additional vertices A, B with suitable edges to induce connectivity
among the yjo vertices. In our construction, we ensure that the center is one of the yjo vertices and
hence computing the Radius in the reduced graph gives the minimum among all the shortest paths
from zjo to zji . This corresponds to a shortest replacement path from s to t. Further details are in
Section 8, where the following three claims are proved.
(i) For each 0 ≤ j ≤ l − 1, the longest shortest path in G′′ from yjo is to the vertex yji .
(ii) A shortest path from zjo to zji corresponds to a replacement path for the edge (vj , vj+1 ).
(iii) One of the vertices among yjo ’s is a center of G′′ .
Thus after computing the radius in G′′ , we can use (i), (ii), and (iii) to compute the weight of a
shortest replacement path from s to t, which is a second simple shortest path from s to t. The cost
of this reduction is O(m + n log n). For full details see Section 8.
12

5

Conditional Hardness Under k-DSH

The following lemma shows that a sub-mn time algorithm for Diameter in an unweighted graph,
either undirected or directed, would falsify k-DSH. This proves Theorems 2.8 and Theorem 2.7 since
the Diameter of a graph can be computed in O(n) time after one call to Eccentricities on the same
graph. Diameter is in the Õ(mn) class, but at this time we do not know if Diameter is MWCC-hard.
Lemma 5.1. Suppose for some constant α there is an O(mα · n2−α−ǫ ) time algorithm, for some
ǫ > 0, for solving Diameter in an unweighted m-edge n-node graph, either undirected or directed.
Then there exists a k′ > 0 such that for all k ≥ k′ , the k-Dominating Set problem can be solved in
O(nk−ǫ ) time.
Proof. When k is even we use a construction in [34]. To determine if undirected graph G = (V, E)
has a k-dominating set we form G′ = (V ′ , E ′ ), where V ′ = V1 ∪ V2 , with V1 containing a vertex for
each subset of V of size k/2 and V2 = V . We add an edge from a vertex v ∈ V1 to a vertex x ∈ V2
if the subset corresponding to v does not dominate x. We induce a clique in the vertex partition
V2 . As shown in [34], G′ has diameter 3 if G has a dominating set of size k and has diameter 2
otherwise, and this gives the reduction when k is even.
If k is odd, so k = 2r + 1, we make n calls to graphs derived from G′ = (V ′ , E ′ ) as follows, where
now each vertex in V1 represents a subset of r vertices in V . For each x ∈ V let Vx be the set
{x} ∪ {neighbors of x in G}, and let Gx be the subgraph of G′ induced on V − Vx . If G has a
dominating set D of size k that includes vertex x then consider any partition of the remaining 2r
vertices in D into two subsets of size r each, and let u and v be the vertices corresponding to these
two sets in V1 . Since all paths from u to v in Gx pass through V2 − Vx , there is no path of length
2 from u to v since every vertex in V2 − Vx is covered by either u or v. Hence the diameter of Gx
is greater than 2 in this case. But if there is no dominating set of size k that includes x in G, then
for any u, v ∈ V1 , at least one vertex in V2 − Vx is not covered by both u and v and hence there is
a path of length 2 from u to v. If we now compute the diameter in each of graphs Gx , x ∈ V , we
will detect a graph with diameter greater than 2 if and only if G has a dominating set of size k.
Each graph Gx has N = O(nr ) vertices and M = O(nr+1 ) edges. If we now assume that Diameter
can be computed in time O(M α · N 2−α−ǫ ), then the above algorithm for k Dominating Set runs in
time O(n · M α · N 2−α−ǫ ) = O(n2r+1−ǫr+α ), which is O(nk−ǫ ) time when k ≥ 3 + 2α
ǫ . The analysis is
similar for k even. In the directed case, we get the same result by replacing every edge in G′ with
two directed edges in opposite directions.

6

Time Bounds for Sparse Graphs

Let T (m, n) be a function which is deﬁned for m ≥ n − 1. We will interpret T (m, n) as a time for an
algorithm on a connected graph and we will refer to T (m, n) as a time bound for a graph problem.
We now focus on formalizing the notion of a time bound T (m, n) being smaller than another time
bound T ′ (m, n) for sparse graphs.
If the time bounds T (m, n) and T ′ (m, n) are of the form mα nβ , then one possible way to check if
T (m, n) is smaller than T ′ (m, n) is to check if the exponents of m and n in T (m, n) are individually
smaller than the corresponding exponents in T ′ (m, n). But using this approach, we would not
be able to compare between time bounds m1/2 n and mn1/2 . Another possible way is to use a
13

direct extrapolation from the single variable case and deﬁne T (m, n) to be (polynomially) smaller
than T ′ (m, n) if T (mn) = O((T ′ (m, n))1−ǫ ) for some constant ǫ > 0. But such a deﬁnition would
completely ignore the dependence of the functions on each of their two variables. We would want
our deﬁnition to take into account the sparsity of the graph, i.e., as a graph becomes sparser, the
smaller time bound has smaller running time. To incorporate this idea, our deﬁnition below asks
for T (m, n) to be a factor of mǫ smaller than T ′ (m, n), for some ǫ > 0. Further, this requirement
is placed only on sufficiently sparse graphs (and for a weakly smaller time bound, we also require a
certain minimum edge density). The consequence of this deﬁnition is that when one time bound is
not dominated by the other for all values of m, the domination needs to hold for suﬃciently sparse
graphs in order for the dominated function to be a smaller time bound for sparse graphs.
Definition 6.1 (Comparing Time Bounds for Sparse Graphs). Given two time bounds
T (m, n) and T ′ (m, n),
(i) T (m, n) is a smaller time bound than T ′ (m,
 n) for sparse graphs if there exist constants
γ, ǫ > 0 such that T (m, n) = O m1ǫ · T ′ (m, n) for all values of m = O(n1+γ ).
(ii) T (m, n) is a weakly smaller time bound than T ′ (m, n) for sparse graphs if there exists a
positive constant γ such that for any constant δ with γ > δ > 0, there exists an ǫ > 0 such that
T (m, n) = O m1ǫ · T ′ (m, n) for all values of m in the range m = O(n1+γ ) and m = Ω(n1+δ ).
Part (i) in above deﬁnition requires a polynomially smaller (in m) bound for T (m, n) relative to
3
T ′ (m, n) for suﬃciently sparse graphs. For example, m
is a smaller time bound than m3/2 , which
n2
in turn is a smaller time bound than mn; m2 is a smaller time bound than n3 . A time bound of
√
√
n m is a weakly smaller bound than m n for sparse graphs by part (ii) but not a smaller bound
since the two bounds coincide when m = O(n).
Our deﬁnition for comparing time bounds for sparse graphs is quite strong as it allows us to compare
√
a wide range of time bounds. For example, using this deﬁnition we can say that n m is a weakly
√
smaller bound than m n for sparse graphs. Whereas if we use the possible approaches that we
discussed before then we would not be able to compare these two time bounds.
With Deﬁnition 6.1 in hand, the following lemma is straightforward.
Lemma 6.2. Let T1 (m, n) = O(mα1 nβ1 ) and T2 (m, n) = O(mα2 nβ2 ) be two time bounds, where
α1 , β1 , α2 , β2 are constants.
(i) T1 (m, n) is a smaller time bound than T2 (m, n) for sparse graphs if α2 + β2 > α1 + β1 .
(ii) T1 (m, n) is a weakly smaller time bound than T2 (m, n) for sparse graphs if α2 + β2 = α1 + β1 ,
and α2 > α1 .
Deﬁnition 6.1, in conjunction with Lemma 6.2 and Theorem 2.7, lead to the following provable
separation of time bounds for sparse graph problems in the sub-cubic equivalence class:
Theorem 6.3 (Split of Time Bounds for Sparse Graphs.). Under either SETH or k-DSH,
triangle finding problems in the sub-cubic equivalence class have algorithms with a smaller time
bound for sparse graphs than any algorithm we can design for Eccentricities.

7

Reduction Details for Undirected Graphs

In Section 3, we gave an overview of our sparse reduction from MWC to APSP. Here in Section 7.1,
we provide full details of this reduction, and reﬁne it to a reduction to APSD. We then describe a
14

• i, j, k are such that:
1. i-th bit of vp+1 is j,
2. i-th bit of vp−1 is j and
M
.
3. 2Mk < w(vp , vp+1 ) ≤ 2k−1

Gi,j,k

G
vp+1

1
vp+1

vp

v1

vp2 (z 2 )

v11 (y 1 )
vp−1

• Alg. MWC-to-APSP’ will
compute w(C) in this Gi,j,k
in wt (line 6)

1
vp−1

(a) MWC C in G. Shortest path
from v1 to vp is highlighted.

(b) Shortest path from
y 1 to z 2 in Gi,j,k .

Figure 4: Here Figure (a) represent the MWC C in G. The path πy,z (in bold) is the shortest path from y to
z in G. The path πy1 ,z2 (in bold) in Figure (b) is the shortest path from y 1 to z 2 in Gi,j,k : where the edge
1
(vp−1
, vp2 ) is absent due to i, j bits. The paths πy,z in G and πy1 ,z2 in Gi,j,k together comprise the MWC C.

Õ(n2 ) sparse reduction from ANSC to APSP in unweighted undirected graphs in Section 7.2.
We start with stating from [35] the notion of a ‘critical edge’.
Lemma 7.1 ([35]). Let G = (V, E, w) be a weighted undirected graph, where w : E → R+ , and
let C = hv1 , v2 , . . . , vl i be a cycle in G. There exists an edge (vi , vi+1 ) on C such that ⌈ w(C)
2 ⌉−
w(C)
w(C)
w(C)
w(vi , vi+1 ) ≤ dC (v1 , vi ) ≤ ⌊ 2 ⌋ and ⌈ 2 ⌉ − w(vi , vi+1 ) ≤ dC (vi+1 , v1 ) ≤ ⌊ 2 ⌋.
The edge (vi , vi+1 ) is called the critical edge of C with respect to the start vertex v1 .

7.1

Reducing Minimum Weight Cycle to APSD

We ﬁrst describe a useful property of a minimum weight cycle.
Lemma 7.2. Let C be a minimum weight cycle in weighted undirected graph G. Let x and y be two
1 and π 2 be the paths from x to y in C. WLOG assume
vertices lying on the cycle C and let πx,y
x,y
1
2
1
2 is a second simple shortest
that w(πx,y ) ≤ w(πx,y ). Then πx,y is a shortest path from x to y and πx,y
path from x to y, i.e. a path from x to y that is shortest among all paths from x to y that are not
1 .
identical to πx,y
3 is a second simple shortest path from x to y of weight less
Proof. Assume to the contrary that πx,y
2 ). Let the path π 3 deviates from the path π 1 at some vertex u and then it merges
than w(πx,y
x,y
x,y
1 and π 3 together form a cycle of
back at some vertex v. Then the subpaths from u to v in πx,y
x,y
weight strictly less than w(C), resulting in a contradiction as C is a minimum weight cycle in G.

Observation 3.1 follows, since the path P there must be either a shortest path or a second simple
shortest path in G by the above lemma, so in G′ it must be a shortest path.
Consider the graphs Gi,j,k as described in Section 3. In the following two lemmas we identify three
key properties of a path π from y 1 to z 2 (y 6= z) in a Gi,j,k that (I) will be satisﬁed by the path P
in Observation 3.1 for y 1 = v11 and z 2 = vp2 in some Gi,j,k (Lemma 7.3), and (II) will cause a simple
cycle in G to be contained in the concatenation of π with the shortest path from y to z computed
by APSP (Lemma 7.4). Once we have these two Lemmas in hand, it gives us a method to ﬁnd a
minimum weight cycle in G by calling APSP on each Gi,j,k and then identifying all pairs y 1 , z 2 in
each graph that satisfy these properties. Since the path P is guaranteed to be one of the pairs, and
no spurious path will be identiﬁed, the minimum weight cycle can be identiﬁed. We now ﬁll in the
details.
15

Lemma 7.3. Let C = hv1 , v2 , . . . , vl i be a minimum weight cycle in G and let (vp , vp+1 ) be its
critical edge with respect to the start vertex v1 . WLOG assume that dG (v1 , vp ) ≥ dG (v1 , vp+1 ). Then
there exists an i ∈ {1, . . . , ⌈log n⌉}, j ∈ {0, 1} and k ∈ {1, 2, . . . , ⌈log ρ⌉} such that the following
conditions hold:
(i) dGi,j,k (v11 , vp2 ) + dG (v1 , vp ) = w(C)
(ii) LastGi,j,k (v11 , vp2 ) 6= LastG (v1 , vp )

(iii) dGi,j,k (v11 , vp2 ) ≤ dG (v1 , vp ) +

M
2k−1

Proof. Let i, j and k be such that: vp−1 and vp+1 diﬀer on i-th bit and j be the i-th bit of vp+1 and k
M
1 , v 2 ) is not present and the edge (v 1 , v 2 )
< w(vp , vp+1 ) ≤ 2k−1
. Hence, edge (vp−1
be such that M
p
p+1 p
2k
is present in Gi,j,k and so LastGi,j,k (v11 , vp2 ) 6= LastG (v1 , vp ), satisfying part 2 of the lemma.

Let us map the path P in Observation 3.1 to the path P ′ in Gi,j,k , such that all vertices except vp
are mapped to V1 and vp is mapped to V2 (bold path from v11 to vp2 in Figure 4b). Then, if P ′ is a
shortest path from v11 to vp2 in Gi,j,k , both parts 1 and 3 of the lemma will hold. So it remains to
show that P ′ is a shortest path. But if not, an actual shortest path from v11 to vp2 in Gi,j,k would
create a shorter cycle in G than C, and if that cycle were not simple, one could extract from it an
even shorter cycle, contradicting the fact that C is a minimum weight cycle in G.
Lemma 7.4. If there exists an i ∈ {1, . . . , ⌈log n⌉}, j ∈ {0, 1} and k ∈ {1, 2, . . . , ⌈log ρ⌉} and
y, z ∈ V such that the following conditions hold:
(i) dGi,j,k (y 1 , z 2 ) + dG (y, z) = wt for some wt

(ii) LastGi,j,k (y 1 , z 2 ) 6= LastG (y, z)

(iii) dGi,j,k (y 1 , z 2 ) ≤ dG (y, z) +

M
2k−1

Then there exists a simple cycle C containing z of weight at most wt in G.
Proof. Let πy,z be a shortest path from y to z in G (see Figure 4a) and let πy1 ,z 2 be a shortest path
′
from y 1 to z 2 in Gi,j,k (Figure 4b). Let πy,z be the path corresponding to πy1 ,z 2 in G.
′

′

Now we need to show that the path πy,z is simple. Assume that πy,z is not simple. It implies that
the path πy1 ,z 2 must contain x1 and x2 for some x ∈ V . Now if x 6= z, then we can remove the
subpath from x1 to x2 (or from x2 to x1 ) to obtain an even shorter path from y 1 to z 2 .
It implies that the path πy1 ,z 2 contains z 1 as an internal vertex. Let πz 1 ,z 2 be the subpath of πy1 ,z 2
from vertex z 1 to z 2 . If πz 1 ,z 2 contains at least 2 internal vertices then this would be a simple cycle
of weight less than wt, and we are done. Otherwise, the path πz 1 ,z 2 contains exactly one internal
vertex (say x1 ). Hence path πz 1 ,z 2 corresponds to the edge (z, x) traversed twice in graph G. But
the weight of the edge (x, z) must be greater than M
(as the edge (x1 , z 2 ) is present in Gi,j,k ).
2k
M
M
Hence w(πz 1 ,z 2 ) > 2k−1
and hence dGi,j,k (y 1 , z 2 ) ≥ dG (y, z) + w(πz 1 ,z 2 ) > dG (y, z) + 2k−1
, resulting
in a contradiction as condition 3 states otherwise. (It is for this property that the index k in Gi,j,k
′
is used.) Thus path πy1 ,z 2 does not contain z 1 as an internal vertex and hence πy,z is simple.
′

′

If the paths πy,z and πy,z do not have any internal vertices in common, then πy,z ◦ πy,z corresponds
to a simple cycle C in G of weight wt that passes through y and z. Otherwise, we can extract from
′
πy,z ◦ πy,z a cycle of weight smaller than wt. This establishes the lemma.
Proof of Theorem 2.2: To compute the weight of a minimum weight cycle in G in Õ(n2 + TAP SP ),
we use the procedure MWC-to-APSP described in Section 3. By Lemmas 7.3 and 7.4, the value wt
returned by this algorithm is the weight of a minimum weight cycle in G.
16

Sparse Reduction to APSD: We now describe how to avoid using the Last matrix in the
reduction. A 2-approximation algorithm for ﬁnding a cycle of weight at most 2t, where t is such
that the minimum-weight cycle’s weight lies in the range (t, 2t], as well as distances between pairs
of vertices within distance at most t, was given by Lingas and Lundell [28]. This algorithm can also
compute the last edge on each shortest path it computes, and its running time is Õ(n2 log(nρ)).
For a minimum weight cycle C = hv1 , v2 , . . . , vl i where the edge (vp , vp+1 ) is a critical edge with
respect to the start vertex v1 , the shortest path length from v1 to vp or to vp+1 is at most t. Thus
using this algorithm, we can compute the last edge on a shortest path for such pair of vertices in
Õ(n2 log(nρ)) time.
In our reduction to APSD, we ﬁrst run the 2-approximation algorithm on the input graph G to
obtain the Last(y, z) for certain pairs of vertices. Then, in Step 5 we check if LastGi,j,k (y 1 , z 2 ) 6=
LastG (y, z) only if LastG (y, z) has been computed (otherwise the current path is not a candidate
for computing a minimum weight cycle). It appears from the algorithm that the Last values are
also needed in the Gi,j,k . However, instead of computing the Last values in each Gi,j,k , we check for
the shortest path from y to z only in those Gi,j,k graphs where the LastG (y, z) has been computed,
and the edge is not present in Gi,j,k . In other words, if Last(y, z) = q, we will only consider the
shortest paths from y 1 to z 2 in those graphs Gi,j,k where q’s i-th bit is not equal to j. Thus our
reduction to APSD goes through without needing APSP to output the Last matrix. 

7.2

Reducing ANSC to APSP in Unweighted Undirected Graphs

For our sparse Õ(n2 ) reduction from ANSC to APSP in unweighted undirected graphs, we use the
graphs from the previous section, but we do not use the index k, since the graph is unweighted.
Our reduction exploits the fact that in unweighted graphs, every edge in a cycle is a critical edge
with respect to some vertex. Thus we construct 2⌈log n⌉ graphs Gi,j , and in order to construct a
shortest cycle through vertex z in G, we will set z = vp2 in the reduction in the previous section.
Then, by letting one of the two edges incident on z in the shortest cycle through z be the critical
edge for the cycle, the construction from the previous section will allow us to ﬁnd the length of a
minimum length cycle through z, for each z ∈ V , with the following post-processing algorithm.
ANSC-to-APSP
1: for each vertex z ∈ V do
2:
wt[z] ← ∞
3: for 1 ≤ i ≤ ⌈log n⌉, j ∈ {0, 1} do
4:
Compute APSP′ on Gi,j,
5:
for y, z ∈ V do
6:
if dGi,j, (y 1 , z 2 ) ≤ dG (y, z) + 1 then check if LastGi,j, (y 1 , z 2 ) 6= LastG (y, z)
7:
if both checks in Step 6 hold then wt[z] ← min(wt[z], dGi,j, (y 1 , z 2 ) + dG (y, z))
8: return wt array

Correctness of the above sparse reduction follows from the following two lemmas, which are similar
to Lemmas 7.3 and 7.4.
Lemma 7.5. Let C = hz, v2 , v3 , . . . , vq i be a minimum length cycle passing through vertex z ∈ V .
Let (vp , vp+1 ) be its critical edge such that p = ⌊ 2q ⌋ + 1. Then there exists an i ∈ {1, . . . , ⌈log n⌉}
and j ∈ {0, 1} such that the following conditions hold:
(i) dGi,j (vp1 , z 2 ) + dG (vp , z) = len(C)
(ii) LastGi,j (vp1 , z 2 ) 6= LastG (vp , z)
17

(iii) dGi,j (vp1 , z 2 ) ≤ dG (vp , z) + 1
Lemma 7.6. If there exists an i ∈ {1, . . . , ⌈log n⌉} and j ∈ {0, 1} and y, z ∈ V such that the
following conditions hold:
(i) dGi,j (y 1 , z 2 ) + dG (y, z) = q for some q where dG (y, z) = ⌊ 2q ⌋
(ii) LastGi,j (y 1 , z 2 ) 6= LastG (y, z)

(iii) dGi,j (y 1 , z 2 ) ≤ dG (y, z) + 1

Then there exists a simple cycle C passing through z of length at most q in G.
Proof of Theorem 2.3: We now show that the entries in the wt array returned by the above algorithm
correspond to the ANSC output for G. Let z ∈ V be an arbitrary vertex in G and let q = wt[z].
Let y ′ be the vertex in Step 5 for which we obtain this value of q. Hence by Lemma 7.6, there exists
a simple cycle C passing through z of length at most q in G. If there were a cycle through z of
length q ′ < q then by Lemma 7.5, there exists a vertex y ′′ such that conditions in Step 6 hold for q ′ ,
and the algorithm would have returned a smaller value than wt[z], which is a contradiction. This
is a sparse Õ(n2 ) reduction since it makes O(log n) calls to APSP, and spends Õ(n2 ) additional
time.
It would be interesting to see if we can obtain a reduction from weighted ANSC to APSD or APSP.
The above reduction does not work for the weighted case since it exploits the fact that for any cycle
C through a vertex z, an edge in C that is incident on z is a critical edge for some vertex in C.
However, this property need not hold in the weighted case.

8

Fine-grained Reductions for Directed Graphs

In Section 4, we gave an overview of our tilde-sparse O(m + n log n) reduction from directed 2-SiSP
to the Radius problem. Here we give full details of this reduction along with the rest of our sparse
reductions for directed graphs (except for the reductions related to Centrality problems which are
described in Section 9).
I. 2-SiSP to Radius and s-t Replacement Paths to Eccentricities: Here we give the details of the sparse reduction from 2SiSP to Radius described in Section 4 and a related sparse
reduction from s-t Replacement Paths to Eccentricities.
We start by pointing out some diﬀerences between the sparse reduction we give below and an earlier
sub-cubic reduction to Radius in [3]. In that sub-cubic reduction to Radius, the starting problem
is Min-Wt-∆. This reduction constructs a 4-partite graph that contains paths that correspond to
triangles in the original graph. However, Min-Wt-∆ can be solved in O(m3/2 ) time and hence to use
this reduction to show MWC hardness for Radius, we ﬁrst need to show that Min-Wt-∆ is MWC
Hard. But this would achieve a major breakthrough by giving an Õ(m3/2 ) time algorithm for MWC
(and would refute MWCC). If we tried to adapt this reduction in [3] to the mn class by starting
from MWC instead of Min-Wt-∆, it appears that we would need to have an n-partite graph, since
a minimum weight cycle could pass through all n vertices in the graph. This would not be a sparse
reduction. Hence, here we instead present a more complex reduction from 2-SiSP. As in [3], we also
use bit-encoding to preserve sparsity in the reduced graph. However the rest of the reduction is
diﬀerent.
18

sprs

sprs

sprs
Lemma 8.1. In weighted directed graphs, 2-SiSP .sprs
m+n Radius and s-t Replacement Paths .m+n
Eccentricities

Proof. We are given an input graph G = (V, E), a source vertex s and a sink/target vertex t and we
wish to compute the second simple shortest path from s to t. Let P (s = v0 → v1
vl−1 → vl = t)
be the shortest path from s to t in G.
Constructing the reduced graph G′′ : We ﬁrst create the graph G′ , which contain G and l additional
vertices z0 ,z1 ,. . .,zl−1 . We remove the edges lying on P from G′ . For each 0 ≤ i ≤ l − 1, we add
an edge from zi to vi of weight dG (s, vi ) and an edge from vi+1 to zi of weight dG (vi+1 , t). Also for
each 1 ≤ i ≤ l − 1, we add a zero weight edge from zi to zi−1 .
Now form G′′ from G′ . For each 0 ≤ j ≤ l − 1, we replace vertex zj by vertices zji and zjo and
we place a directed edge of weight 0 from zji to zjo , and we also replace each incoming edge to
(outgoing edge from) zj with an incoming edge to zji (outgoing edge from zjo ) in G′ .
Let M be the largest edge weight in G and let M ′ = 9nM . For each 0 ≤ j ≤ l−1, we add additional
vertices yji and yjo and we place a directed edge of weight 0 from yjo to zjo and an edge of weight
11
′
9 M from zji to yji .
We add 2 additional vertices A and B, and we place a directed edge from A to B of weight 0. We
also add l incoming edges to A (outgoing edges from B) from (to) each of the yj′ o s of weight 0 (M ′ ).
′

2
We also add edges of weight 2M
3 from yjo to yki (for each k 6= j). But due to the addition of O(n )
′
edges, graph G becomes dense. To solve this problem, we add a gadget in our construction that
′
ensures that ∀0 ≤ j ≤ l − 1, we have at least one path of length 2 and weight equal to 2M
3 from yjo
to yki (for each k 6= j) (similar to [3]). In this gadget, we add 2⌈log n⌉ vertices of the form Cr,s for
1 ≤ r ≤ ⌈log n⌉ and s ∈ {0, 1}. Now for each 0 ≤ j ≤ l − 1, 1 ≤ r ≤ ⌈log n⌉ and s ∈ {0, 1}, we add
′
′
an edge of weight M3 from yjo to Cr,s if j ′ s r-th bit is equal to s. We also add an edge of weight M3
from Cr,s to yji if j’s r-th bit is not equal to s. So overall we add 2n log n edges that are incident to
Cr,s vertices; for each yjo we add log n outgoing edges to Cr,s vertices and for each yji we add log n
incoming edges from Cr,s vertices.
′

We can observe that for 0 ≤ j ≤ l − 1, there is at least one path of weight 2M
3 from yjo to yki (for
each k 6= j) and the gadget does not add any new paths from yjo to yji . The reason is that for
every distinct j, k, there is at least one bit (say r) where j and k diﬀer and let s be the r-th bit of
j. Then there must be an edge from yjo to Cr,s and an edge from Cr,s to yki , resulting in a path of
′
weight 2M
3 from yjo to yki . And by the same argument we can also observe that this gadget does
not add any new paths from yjo to yki .
We call this graph as G′′ . Figure 3 depicts the full construction of G′′ for l = 3. We now establish
the following three properties.
(i) For each 0 ≤ j ≤ l − 1, the longest shortest path in G′′ from yjo is to the vertex yji . It is easy to
see that the shortest path from yjo to any of the vertices in G or any of the z’s has weight at most
nM . And the shortest paths from yjo to the vertices A and B have weight 0. For k 6= j, the shortest
path from yjo to yko and yki has weight M ′ and 23 M ′ respectively. Whereas the shortest path from
′
yjo to yji has weight at least 10nM as it includes the last edge (zji , yji ) of weight 11
9 M = 11nM .
It is easy to observe that the shortest path from yjo to yji corresponds to the shortest path from
zjo to zji .
(ii) The shortest path from zjo to zji corresponds to the replacement path for the edge (vj , vj+1 )
lying on P . Suppose not and let Pj (s
vh
vk
t) (where vh is the vertex where Pj separates
19

from P and vk is the vertex where it joins P ) be the replacement path from s to t for the edge
zji )
(vj , vj+1 ). But then the path πj (zjo → zj−1i
zho → vh ◦ Pj (vh , vk ) ◦ vk → zki → zko
(where Pj (vh , vk ) is the subpath of Pj from vj to vk ) from zjo to zji has weight equal to wt(Pj ),
resulting in a contradiction as the shortest path from zjo to zji has weight greater than that of Pj .
(iii) One of the vertices among yjo ’s is a center of G′′ . It is easy to see that none of the vertices
in G could be a center of the graph G′′ as there is no path from any v ∈ V to any of the yjo ’s in
G′′ . Using a similar argument, we can observe that none of the z’s, or the vertices yji ’s could be a
potential candidate for the center of G′′ . For vertices A and B, the shortest path to any of the yji ’s
has weight exactly 53 M ′ = 15nM , which is strictly greater than the weight of the largest shortest
path from any of the yjo ’s. Thus one of the vertices among yjo ’s is a center of G′′ .
Thus by computing the radius in G′′ , from (i), (ii), and (iii), we can compute the weight of the
shortest replacement path from s to t, which by deﬁnition of 2-SiSP, is the second simple shortest
path from s to t. This completes the proof of 2-SiSP .sprs
m+n Radius.
Now, if instead of computing Radius in G′′ we compute the Eccentricities of all vertices in G′′ , then
from (i) and (ii) we can compute the weight of the replacement path for every edge (vj , vj+1 ) lying
on P , thus solving the replacement paths problem. So s-t Replacement Paths .sprs
m+n Eccentricities.
Constructing G′′ takes O(m+n log n) time since we add O(n) additional vertices and O(m+n log n)
additional edges, and given the output of Radius (Eccentricities), we can compute 2-SiSP (s-t
Replacement Paths) in O(1) (O(n)) time and hence the cost of both reductions is O(m+n log n).
II. ANSC and Replacement Paths: We ﬁrst describe a sparse reduction from directed MWC
to 2-SiSP, which we will use for reducing ANSC to the s-t replacement paths problem. This reduction
is adapted from a sub-cubic non-sparse reduction from Min-Wt-∆ to 2-SiSP in [42]. The reduction
in [42] reduces Min-Wt-∆ to 2-SiSP by creating a tripartite graph. Since starting from Min-Wt-∆
is not appropriate for our results (as discussed in our sparse reduction to directed Radius), we start
instead from MWC, and instead of the tripartite graph used in [42] we use the original graph G
with every vertex v replaced with 2 copies, vi and vo .
In this reduction, as in [42], we ﬁrst create a path of length n with vertices labeled from p0 to pn ,
which will be the initial shortest path. We then map every edge (pi , pi+1 ) to the vertex i in the
original graph G such that the replacement path from p0 to pn for the edge (pi , pi+1 ) corresponds
to the shortest cycle passing through i in G. Thus computing 2-SiSP (i.e., the shortest replacement
path) from p0 to pn in the constructed graph corresponds to the minimum weight cycle in the
original graph. The details of the reduction are in the proof of the lemma below.
sprs

Lemma 8.2. In weighted directed graphs, MWC ≤sprs
m+n 2-SiSP
Proof. To compute MWC in G, we ﬁrst create the graph G′ , where we replace every vertex z by
vertices zi and zo , and we place a directed edge of weight 0 from zi to zo , and we replace each
incoming edge to (outgoing edge from) z with an incoming edge to zi (outgoing edge from zo ). We
also add a path P (p0 → p1
pn−1 → pn ) of length n and weight 0.

Let Q = n· M , where M is the maximum weight of any edge in G. For each 1 ≤ j ≤ n, we add an
edge of weight (n − j + 1)Q from pj−1 to jo and an edge of weight jQ from ji to pj in G′ to form
G′′ . Figure 5 depicts the full construction of G′′ for n = 3. This is an (m + n) reduction, and it can
be seen that the second simple shortest path from p0 to pn in G′′ corresponds to a minimum weight
cycle in G.
20

1o 1i
2o 2i
G′
3W
p0

W

3o 3i

2W

2W
W
p1
p2

0

0

p3

3W

0

Figure 5: G′′ for n = 3 in the reduction: directed MWC ≤sprs
m+n 2-SiSP
G
v1

v0 = s

v2
v3 = t

0
dG (v1 , t)

0

z0 0 z1 0 z2
dG (s, v1 )
dG (v2 , t)

dG (s, v2 )
sprs

Figure 6: G for l = 3 in the reduction: directed s-t Replacement Paths ≤sprs
m+n ANSC
′

We now establish the equivalence between ANSC and the s-t replacement paths problem under
(m + n)-reductions by ﬁrst showing an (m + n)-sparse reduction from s-t replacement paths problem
to ANSC. We then describe a sparse reduction from ANSC to the s-t replacement paths problem,
which is similar to the reduction from MWC to 2-SiSP as described in Lemma 8.2.
sprs

Lemma 8.3. In weighted directed graphs, s-t replacement paths ≡sprs
m+n ANSC
Proof. We are given an input graph G = (V, E), a source vertex s and a sink vertex t and we wish
to compute the replacement paths for all the edges lying on the shortest path from s to t. Let
P (s = v0 → v1
vl−1 → vl = t) be the shortest path from s to t in G.

(i) Constructing G′ : We ﬁrst create the graph G′ , as described in the proof of Lemma 8.1. Figure 6
depicts the full construction of G′ for l = 3.

(ii) We now show that for each 0 ≤ i ≤ l − 1, the replacement path from s to t for the edge (vi , vi+1 )
lying on P has weight equal to the shortest cycle passing through zi . If not, assume that for some i
(0 ≤ i ≤ l − 1), the weight of the replacement path from s to t for the edge (vi , vi+1 ) is not equal
to the weight of the shortest cycle passing through zi .
Let Pi (s
vj
vk
t) (where vj is the vertex where Pi separates from P and vk is the
vertex where it joins P ) be the replacement path from s to t for the edge (vi , vi+1 ) and let Ci
(zi
zp → vp
vq → zq
zi ) be the shortest cycle passing through zi in G′ .

If wt(Pi ) < wt(Ci ), then the cycle Ci′ (zi → zi−1
zj → vj ◦ Pi (vj , vk ) ◦ vk → zk → zk−1
zi )
(where Pi (vj , vk ) is the subpath of Pi from vj to vk ) passing through zi has weight equal to wt(Pi ) <
wt(Ci ), resulting in a contradiction as Ci is the shortest cycle passing through zi in G′ .
Now if wt(Ci ) < wt(Pi ), then the path Pi′ (s
vp ◦ Ci (vp , vq ) ◦ vq
vl ) where Ci (vp , vq ) is the
subpath of Ci from vp to vq , is also a path from s to t avoiding the edge (vi , vi+1 ), and has weight
equal to wt(Ci ) < wt(Pi ), resulting in a contradiction as Pi is the shortest replacement path from
s to t for the edge (vi , vi+1 ).
We then compute ANSC in G′ . And by (ii), the shortest cycles for each of the vertices z0 , z1 , . . . , zl−1
gives us the replacement paths from s to t. This leads to an (m + n) sparse reduction from s-t
replacement paths problem to ANSC.
21

BC

RC

Diameter

Pos BC

ANBC

Pos ANBC

Min-Wt-∆

Figure 7: Known sparse reductions for centrality problems, all from [3]. The regular edges represent sparse
O(m + n) reductions, the squiggly edges represent tilde-sparse O(m + n) reductions, and the dashed edges
represent reductions that are trivial. BC and Min-Wt-∆ (shaded with gray) are known to be sub-cubic
equivalent to APSP [3, 42].

Now for the other direction, we are given an input graph G = (V, E) and we wish to compute the
′′
ANSC in G. We ﬁrst create the graph G , as described in Lemma 8.2. We can see that the shortest
path from p0 to pn avoiding edge (pj−1 , pj ) corresponds to a shortest cycle passing through j in G.
This gives us an (m + n)-sparse reduction from ANSC to s-t replacement paths problem.

9

Betweenness Centrality: Reductions

In this section, we consider sparse reductions for Betweenness Centrality and related problems. In
its full generality, the Betweenness Centrality of a vertex v is the sum, across all pairs of vertices s, t,
of the fraction of shortest paths from s to t that contain v as an internal vertex. This problem has
a Õ(mn) time algorithm due to Brandes [12]. Since there can be an exponential (in n) number of
shortest paths from one vertex to another, this general problem can deal with very large numbers.
In [3], a simpliﬁed variant was considered, where it is assumed that there is a unique shortest path
for each pair of vertices, and the Betweenness Centrality of vertex v, BC(v), is deﬁned as the
number of vertex pairs s, t such that v is an internal vertex on the unique shortest path from s to
t. We will also restrict our attention to this variant here.
A number of sparse reductions relating to the following problems were given in [3].
• Betweenness Centrality (BC) of a vertex v, BC(v).
• Positive Betweenness Centrality (Pos BC) of v: determine whether BC(v) > 0.
• All Nodes Betweenness Centrality (ANBC): compute, for each v, the value of BC(v).
• Positive All Nodes Betweenness Centrality (Pos ANBC): determine, for each v, whether
BC(v) > 0.
• Reach Centrality (RC) of v: compute maxs,t∈V :dG (s,v)+dG (v,t)=dG (s,t) min(dG (s, v), dG (v, t)).
Figure 7 gives an overview of the previous ﬁne-grained results given in [3] for Centrality problems.
In this ﬁgure, BC is the only centrality problem that is known to be sub-cubic equivalent to APSP,
and hence is shaded in the ﬁgure (along with Min-Wt-∆). None of these sparse reductions in [3]
imply MWCC hardness for any of the centrality problems since Diameter is not MWCC-hard (or
even sub-cubic equivalent to APSP), and Min-Wt-∆ has an Õ(m3/2 ) time algorithm, and so will
falsify MWCC if it is MWCC-hard. On other hand, Diameter is known to be both SETH-hard [34]
and k-DSH Hard (Section 5) and hence all these problems in Figure 7 (except Min-Wt-∆) are also
SETH and k-DSH hard.
22

BC

MWC

2-SiSP
≡sprs
m+n
2-SiSC
[7]

s-t replacement paths
≡sprs
m+n ANSC

Pos
ANBC

ANBC
n2
n2

Radius

Eccentricities

APSP

Figure 8: Sparse reductions for weighted directed graphs. The regular edges represent sparse O(m + n)
reductions, the squiggly edges represent tilde-sparse O(m + n) reductions, and the dashed edges represent
reductions that are trivial. All problems except APSP are MWCC-hard. Eccentricities, BC, ANBC and Pos
ANBC are also SETH/ k-DSH hard. ANBC and Pos ANBC (problems inside the dashed circles) are both
not known to be subcubic equivalent to APSP.

In this section, we give a sparse reduction from 2-SiSP to BC, establishing MWCC-hardness for
BC. We also give a tilde-sparse reduction from ANSC to Pos ANBC, and thus we have MWCChardness for both Pos ANBC and for ANBC, though neither problem is known to be in the sub-cubic
equivalence class. (Both have Õ(mn) time algorithms, and have APSP-hardness under sub-cubic
reductions.)
Figure 8 gives an updated partial order of our sparse reductions for weighted directed graphs; this
ﬁgure augments Figure 1 by including the sparse reductions for BC problems given in this section.
I. 2-SiSP to BC: Our sparse reduction from 2-SiSP to BC is similar to the reduction from 2SiSP to Radius described in Section 4. In our reduction, we ﬁrst map every edge (vj , vj+1 ) to new
vertices yjo and yji such that the shortest path from yjo to yji corresponds to the replacement path
from s to t for the edge (vj , vj+1 ). We then add an additional vertex A and connect it to vertices
yjo ’s and yji ’s. We also ensure that the only shortest paths passing through A are from yjo to yji .
We then do binary search on the edge weights for the edges going from A to yji ’s with oracle calls to
the Betweenness Centrality problem, to compute the weight of the shortest replacement path from
s to t, which by deﬁnition of 2-SiSP, is the second simple shortest path from s to t.
sprs

Lemma 9.1. In weighted directed graphs, 2-SiSP .sprs
m+n Betweenness Centrality
Proof. We are given an input graph G = (V, E), a source vertex s and a sink/target vertex t and we
wish to compute the second simple shortest path from s to t. Let P (s = v0 → v1
vl−1 → vl = t)
be the shortest path from s to t in G.
(i) Constructing G′′ : We ﬁrst construct the graph G′′ , as described in the proof of Lemma 8.1,
without the vertices A and B. For each 0 ≤ j ≤ l − 1, we change the weight of the edge from zji to
yji to M ′ (where M ′ = 9nM and M is the largest edge weight in G).
We add an additional vertex A and for each 0 ≤ j ≤ l − 1, we add an incoming (outgoing) edge
from (to) yjo (yji ). We assign the weight of the edges from yjo ’s to A as 0 and from A to yji ’s as
M ′ + q (for some q in the range 0 to nM ).
Figure 9 depicts the full construction of G′′ for l = 3.
We observe that for each 0 ≤ j ≤ l − 1, a shortest path from yjo to yji with (zji , yji ) as the last
edge has weight equal to M ′ + dG′′ (zjo , zji ).
23

dG (s, v1 )

dG (v2 , t)

v1
G

v2

v0 (s)

v3 (t)
dG (v1z, t)

0
z0o

z1o

0i

0

0

0

(s, v2 )
zd2G
o

z1i
0

0

0

0

0
z2i

0

y0o

y1o
y0i

y1i

y2o

y2i

A

C1,0

C1,1

C2,0

C2,1
sprs

Figure 9: G′′ for l = 3 in the reduction: directed 2-SiSP .sprs
m+n Betweenness Centrality. The gray and the
bold edges have weight M ′ and 31 M ′ respectively. All the outgoing (incoming) edges from (to) A have weight
M ′ + q (0).

(ii) We now show that the Betweenness Centrality of A, i.e. BC(A), is equal to l iff q < dG′′ (zjo , zji )
for each 0 ≤ j ≤ l − 1. The only paths that passes through the vertex A are from vertices yjo ’s to
vertices yji ’s. For j 6= k, as noted in the proof of Lemma 8.1, there exists some r, s such that there
is a path from yjo to yki that goes through Cr,s and has weight equal to 32 M ′ . However a path from
yjo to yki has weight M ′ + q, which is strictly greater than 23 M ′ and hence the pairs (yjo , yki ) does
not contribute to the Betweenness Centrality of A.
Now if BC(A), is equal to l, it implies that the shortest paths for all pairs (yjo , yji ) passes through
A and there is exactly one shortest path for each such pair. Hence for each 0 ≤ j ≤ l − 1,
M ′ + q < M ′ + dG′′ (zjo , zji ). Thus q < dG′′ (zjo , zji ) for each 0 ≤ j ≤ l − 1.

On the other hand if q < dG′′ (zjo , zji ) for each 0 ≤ j ≤ l − 1, then the path from yjo to yji with
(zji , yji ) as the last edge has weight M ′ + dG′′ (zjo , zji ). However the path from yjo to yji passing
through A has weight M ′ + q < M ′ + dG′′ (zjo , zji ). Hence every such pair contributes 1 to the
Betweenness Centrality of A and thus BC(A) = l.
Thus using (ii), we just need to ﬁnd the minimum value of q such that BC(A) < l in order to
compute the value min0≤j≤l−1 dG′′ (zjo , zji ). We can ﬁnd such q by performing a binary search in
the range 0 to nM and computing BC(A) at every layer. Thus we make O(log nM ) calls to the
Betweenness Centrality algorithm.
As observed in the proof of Lemma 8.3, we know that the shortest path from zjo to zji corresponds
to the replacement path for the edge (vj , vj+1 ) lying on P . Thus by making O(log nM ) calls to the
Betweenness Centrality algorithm, we can compute the second simple shortest path from s to t in
G. This completes the proof.
The cost of this reduction is O((m + n log n) · log nM ).
II. ANSC to Pos ANBC: We now describe a tilde-sparse reduction from the ANSC problem
to the All Nodes Positive Betweenness Centrality problem (Pos ANBC). Sparse reductions from

24

1o

0 1i 2o

0 2i 3o

0

q1 0

q2 0

0 3i

G

z1

z2

q3
z3
sprs

Figure 10: G for n = 3 in the reduction: directed ANSC .sprs
m+n Pos ANBC.
′

Min-Wt-∆ and from Diameter to Pos ANBC are given in [3]. However, Min-Wt-∆ can be solved in
O(m3/2 ) time, and Diameter is not known to be MWC-hard, hence neither of these reductions can
be used to show hardness of the All Nodes Positive Betweenness Centrality problem relative to the
MWC Conjecture. (Recall that Pos ANBC is not known to be subcubic equivalent to APSP.)
Our reduction is similar to the reduction from 2-SiSP to the Betweenness Centrality problem, but
instead of computing betweenness centrality through one vertex, it computes the positive betweenness centrality values for n diﬀerent nodes. We ﬁrst split every vertex x into vertices xo and xi
such that the shortest path from xo to xi corresponds to the shortest cycle passing through x in
the original graph. We then add additional vertices zx for each vertex x in the original graph and
connect it to the vertices xo and xi such that the only shortest path passing through zx is from xo
to xi . We then perform binary search on the edge weights for the edges going from zx to xi with
oracle calls to the Positive Betweenness Centrality problem, to compute the weight of the shortest
cycle passing through x in the original graph. Our reduction is described in Lemma 9.2.
sprs

Lemma 9.2. In weighted directed graphs, ANSC .sprs
m+n Pos ANBC
Proof. We are given an input graph G = (V, E) and we wish to compute the ANSC in G. Let M
be the largest edge weight in G.
(i) Constructing G′ : Now we construct a graph G′ from G. For each vertex x ∈ V , we replace x
by vertices xi and xo and we place a directed edge of weight 0 from xi to xo , and we also replace
each incoming edge to (outgoing edge from) x with an incoming edge to xi (outgoing edge from xo )
in G′ . We can observe that the shortest path from xo to xi in G′ corresponds to the shortest cycle
passing through x in G.
For each vertex x ∈ V , we add an additional vertex zx in G′ and we add an edge of weight 0 from
xo to zx and an edge of weight qx (where qx lies in the range from 0 to nM ) from zx to xi .
Figure 10 depicts the full construction of G′ for n = 3.
We observe that the shortest path from xo to xi for some vertex x ∈ V passes through zx only if
the shortest cycle passing through x in G has weight greater than qx .
(ii) We now show that for each vertex x ∈ V , Positive Betweenness Centrality of zx is true, i.e.,
BC(zx ) > 0 iff the shortest cycle passing through x has weight greater than qx . It is easy to see that
the only path that pass through vertex zx is from xo to xi (as the only outgoing edge from xi is to
xo and the only incoming edge to xo is from xi ).
Now if BC(zx ) > 0, it implies that the shortest path from xo to xi passes through zx and hence the
path from xo to xi corresponding to the shortest cycle passing through x has weight greater than
qx .
On the other hand, if the shortest cycle passing through x has weight greater than qx , then the
shortest path from xo to xi passes through zx . And hence BC(zx ) > 0.
Then using (ii), we just need to ﬁnd the maximum value of qx such that BC(zx ) > 0 in order
to compute the weight of the shortest cycle passing through x in the original graph. We can ﬁnd
25

such qx by performing a binary search in the range 0 to nM and computing Positive Betweenness
Centrality for all nodes at every layer. Thus we make O(log nM ) calls to the Pos ANBC algorithm.
This completes the proof.
The cost of this reduction is O((m + n) · log nM ).

A
A.1

Appendix
Definitions of Graph Problems

All Pairs Shortest Distances (APSD). Given a graph G = (V, E), the APSD problem is to
compute the shortest path distances for every pair of vertices in G.
APSP. This is the problem of computing the shortest path distances for every pair of vertices in
G together with a concise representation of the shortest paths, which in our case is an n × n matrix,
LastG , that contains, in position (x, y), the predecessor vertex of y on a shortest path from x to y.
Minimum Weight Cycle (MWC). Given a graph G = (V, E), the minimum weight cycle
problem is to ﬁnd the weight of a minimum weight cycle in G.
All Nodes Shortest Cycles (ANSC). Given a graph G = (V, E), the ANSC problem is to ﬁnd
the weight of a shortest cycle through each vertex in G.
Replacement Paths. Given a graph G = (V, E) and a pair of vertices s, t, the replacement paths
problem is to ﬁnd, for each edge e lying on the shortest path from s to t, a shortest path from s to
t avoiding the edge e.
k-SiSP. Given a graph G = (V, E) and a pair of vertices s, t, the k-SiSP problem is to ﬁnd the k
shortest simple paths from s to t: the i-th path must be diﬀerent from ﬁrst (i − 1) paths and must
have weight greater than or equal to the weight of any of these (i − 1) paths.
k-SiSC. The corresponding cycle version of k-SiSP is known as k-SiSC, where the goal is to
compute the k shortest simple cycles through a given vertex x, such that the i-th cycle generated
is diﬀerent from all previously generated (i − 1) cycles and has weight greater than or equal to the
weight of any of these (i − 1) cycles.
Radius. For a given graph G = (V, E), the Radius problem is to compute the value minx∈V
maxy∈V dG (x, y). The center of a graph is the vertex x which minimizes this value.
Diameter.
dG (x, y).

For a given graph G = (V, E), the Diameter problem is to compute the value maxx,y∈V

Eccentricities. For a given graph G = (V, E), the Eccentricities problem is to compute the value
maxy∈V dG (x, y) for each vertex x ∈ V .
Betweenness Centrality (BC). For a given graph G = (V, E) and a node v ∈ V , the BetweenP
σ (v)
ness Centrality of v, BC(v), is the value s,t∈V,s,t6=v s,t
σs,t , where σs,t is the number of shortest
paths from s to t and σs,t (v) is the number of shortest paths from s to t passing through v.
As in [3] we assume that the graph has unique shortest paths, hence BC(v) is simply the number
of s, t pairs such that the shortest path from s to t passes through v.
All Nodes Betweenness Centrality (ANBC).
ity: determine BC(v) for all vertices.
26

The all-nodes version of Betweenness Central-

Positive Betweenness Centrality (Pos BC).
Pos BC problem is to deternine if BC(v) > 0.

Given a graph G = (V, E) and a vertex v, the

All Nodes Positive Betweenness Centrality (Pos ANBC).
Betweenness Centrality.

The all-nodes version of Positive

Reach Centrality (RC). For a given graph G = (V, E) and a node v ∈ V , the Reach Centrality
of v, RC(v), is the value maxs,t∈V :dG (s,v)+dG (v,t)=dG (s,t) min(dG (s, b), dG (b, t)).

A.2

k-SiSC Algorithm : Undirected Graphs

This section deals with an application of our bit-sampling technique to obtaining a new near-linear
time algorithm for k-SiSC in undirected graphs (see deﬁnition below). Note that this problem is
not in the mn class and this result is included here as an application of the bit-sampling technique.
k-SiSC is the problem of ﬁnding k simple shortest cycles passing through a vertex v. Here the
output is a sequence of k simple cycles through v in non-decreasing order of weights such that the
i-th cycle in the output is diﬀerent from the previous i − 1 cycles. The corresponding path version
of this problem is known as k-SiSP and is solvable in near linear time in undirected graphs [26].
We now use our bit-sampling technique (described in Section 3) to get a near-linear time algorithm for k-SiSC, which was not previously known. We obtain this k-SiSC algorithm by giving a
tilde-sparse Õ(m + n) time reduction from k-SiSC to k-SiSP. This reduction uses our bit-sampling
technique for sampling the edges incident to v and creates ⌈log n⌉ diﬀerent graphs. Here we only
use index i of our bit-sampling method.
sprs

Lemma A.1. In undirected graphs, k-SiSC .sprs
(m+n) k-SiSP.
Proof. Let the input be G = (V, E) and let x ∈ V be the vertex for which we need to compute
k-SiSC. Let N (x) be the neighbor-set of x. We create ⌈log n⌉ graphs Gi = (Vi , Ei ) such that
∀1 ≤ i ≤ ⌈log n⌉, Gi contains two additional vertices x0,i and x1,i (instead of the vertex x) and
∀y ∈ N (x), the edge (y, x0,i ) ∈ Ei if y’s i-th bit is 0, otherwise the edge (y, x1,i ) ∈ Ei . This is our
bit-sampling method.
The construction takes O((m+n)·log n) time and we observe that every cycle through x will appear
as a path from x0,i to x1,i in at least one of the Gi . Hence, the k-th shortest path in the collection
of k-SiSPs from x0,i to x1,i in log n Gi , 1 ≤ i ≤ ⌈log n⌉ (after removing duplicates), corresponds to
the k-th SiSC passing through x.
Using the undirected k-SiSP algorithm in [26] that runs in O(k · (m + n log n)), we obtain an
O(k log n · (m + n log n)) time algorithm for k-SiSC in undirected graphs.

References
[1] A. Abboud, A. Backurs, and V. V. Williams. If the current clique algorithms are optimal, so
is Valiant’s parser. In Proc. FOCS, pages 98–117. IEEE, 2015.
[2] A. Abboud, K. Censor-Hillel, and S. Khoury. Near-linear lower bounds for distributed distance
computations, even in sparse networks. In Proc. ISDC, pages 29–42. Springer, 2016.
27

[3] A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equivalences between graph centrality
problems, APSP and diameter. In Proc. SODA, pages 1681–1697, 2015.
[4] A. Abboud, V. Vassilevska Williams, and H. Yu. Matching triangles and basing hardness on
an extremely popular conjecture. In Proc. STOC, pages 41–50. ACM, 2015.
[5] A. Abboud and V. V. Williams. Popular conjectures imply strong lower bounds for dynamic
problems. In Proc. FOCS, pages 434–443. IEEE, 2014.
[6] A. Abboud, V. V. Williams, and J. Wang. Approximation and ﬁxed parameter subquadratic
algorithms for radius and diameter in sparse graphs. In Proc. SODA, pages 377–391. SIAM,
2016.
[7] U. Agarwal and V. Ramachandran. Finding k simple shortest paths and cycles. In Proc.
ISAAC, pages 8:1–8:12, 2016.
[8] N. Alon, Z. Galil, O. Margalit, and M. Naor. Witnesses for boolean matrix multiplication and
for shortest paths. In Proc. FOCS, pages 417–426. IEEE, 1992.
[9] N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica,
17(3):209–223, 1997.
[10] A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein. On hardness of jumbled indexing.
In Proc. ICALP, pages 114–125. Springer, 2014.
[11] A. Backurs and P. Indyk. Edit distance cannot be computed in strongly subquadratic time
(unless SETH is false). In Proc. STOC, pages 51–58. ACM, 2015.
[12] U. Brandes. A faster algorithm for betweenness centrality. Jour. Math. Soc., 25(2):163–177,
2001.
[13] M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for nonreducibility. In Proc. ITCS, pages 261–270. ACM, 2016.
[14] S. Chechik, T. D. Hansen, G. F. Italiano, V. Loitzenbauer, and N. Parotsidis. Faster algorithms
for computing maximal 2-connected subgraphs in sparse directed graphs. In Proc. SODA, pages
1900–1918. SIAM, 2017.
[15] A. Gajentaan and M. H. Overmars. On a class of O(n2 ) problems in computational geometry.
Computational Geometry, 5(3):165–185, 1995.
[16] Z. Galil and O. Margalit. All pairs shortest distances for graphs with small integer length
edges. Information and Computation, 134(2):103–139, 1997.
[17] J. Gao, R. Impagliazzo, A. Kolokolova, and R. Williams. Completeness for ﬁrst-order properties
on sparse structures with algorithmic applications. In Proc. SODA, pages 2162–2181. SIAM,
2017.
[18] Z. Gotthilf and M. Lewenstein. Improved algorithms for the k simple shortest paths and the
replacement paths problems. Inf. Proc. Lett., 109(7):352–355, 2009.

28

[19] T. Hagerup. Improved shortest paths on the word ram. In Proc. ICALP, pages 61–72. Springer,
2000.
[20] M. Henzinger, S. Krinninger, and V. Loitzenbauer. Finding 2-edge and 2-vertex strongly
connected components in quadratic time. In Proc. ICALP, pages 713–724. Springer, 2015.
[21] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. Unifying and strengthening
hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc.
STOC, pages 21–30. ACM, 2015.
[22] R. Impagliazzo and R. Paturi. On the complexity of k-sat. Jour. Comput. Sys. Sci., 62(2):367–
375, 2001.
[23] A. Itai and M. Rodeh. Finding a minimum circuit in an graph. SIAM Jour. Comput., 7(4):413–
423, 1978.
[24] Z. Jafargholi and E. Viola. 3SUM, 3XOR, triangles. Algorithmica, 74(1):326–343, 2016.
[25] R. M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85–103. Springer, 1972.
[26] N. Katoh, T. Ibaraki, and H. Mine. An eﬃcient algorithm for k shortest simple paths. Networks,
12(4):411–427, 1982.
[27] T. Kopelowitz, S. Pettie, and E. Porat. Higher lower bounds from the 3SUM conjecture. In
Proc. SODA, pages 1272–1287. SIAM, 2016.
[28] A. Lingas and E.-M. Lundell. Eﬃcient approximation algorithms for shortest cycles in undirected graphs. Inf. Proc. Lett., 109(10):493–498, 2009.
[29] J. B. Orlin and A. Sedeno-Noda. An O(nm) time algorithm for ﬁnding the min length directed
cycle in a graph. In Proc. SODA. SIAM, 2017.
[30] M. Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. STOC, pages
603–610. ACM, 2010.
[31] M. Pătraşcu and R. Williams. On the possibility of faster sat algorithms. In Proc. SODA,
pages 1065–1075. SIAM, 2010.
[32] S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical
Computer Science, 312(1):47–74, 2004.
[33] S. Pettie and V. Ramachandran. A shortest path algorithm for real-weighted undirected graphs.
SIAM Jour. Comput., 34(6):1398–1431, 2005.
[34] L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and
radius of sparse graphs. In Proc. STOC, pages 515–524. ACM, 2013.
[35] L. Roditty and V. V. Williams. Minimum weight cycles and triangles: Equivalences and
algorithms. In Proc. FOCS, pages 180–189. IEEE, 2011.
[36] P. Sankowski and K. Węgrzycki. Improved distance queries and cycle counting by Frobenius
Normal Form. In Proc. STACS, pages 56:1–56:14, 2017.
29

[37] R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Jour.
Comput. Sys. Sci., 51(3):400–403, 1995.
[38] A. Shoshan and U. Zwick. All pairs shortest paths in undirected graphs with integer weights.
In Proc. FOCS, pages 605–614. IEEE, 1999.
[39] M. Thorup. Undirected single source shortest paths in linear time. In Proc. FOCS, pages
12–21. IEEE, 1997.
[40] V. Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures
such as the strong exponential time hypothesis (invited talk). In LIPIcs-Leibniz Intl. Proc.
Informatics, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
[41] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357–365, 2005.
[42] V. V. Williams and R. Williams. Subcubic equivalences between path, matrix and triangle
problems. In Proc. FOCS, pages 645–654. IEEE, 2010.
[43] V. V. Williams and R. Williams. Finding, minimizing, and counting weighted subgraphs. SIAM
Jour. Comp., 42(3):831–854, 2013.
[44] R. Yuster. A shortest cycle for each vertex of a graph. Inf. Proc. Lett., 111(21):1057–1061,
2011.
[45] U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication.
JACM, 49(3):289–317, 2002.

30

