# On the Space Usage of Approximate Distance Oracles
with Sub-2 Stretch††thanks: This work is partially supported by Israel Science
Foundation (ISF) grant no. 1926/19 and by United States - Israel Binational
Science Foundation (BSF) grant no. 2018364. Contact<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Tsvi Kopelowitz  Ariel Korin  Liam Roditty
Bar-Ilan University  Ramat Gan  Israel

###### Abstract

For an undirected unweighted graph $G=(V,E)$ with $n$ vertices and $m$ edges,
let $d(u,v)$ denote the distance from $u\in V$ to $v\in V$ in $G$. An
$(\alpha,\beta)$-stretch approximate distance oracle (ADO) for $G$ is a data
structure that given $u,v\in V$ returns in constant (or near constant) time a
value $\hat{d}(u,v)$ such that $d(u,v)\leq\hat{d}(u,v)\leq\alpha\cdot
d(u,v)+\beta$, for some reals $\alpha>1,\beta$. If $\beta=0$, we say that the
ADO has stretch $\alpha$.

Thorup and Zwick [30] showed that one cannot beat stretch 3 with subquadratic
space (in terms of $n$) for general graphs. Pǎtraşcu and Roditty [23] showed
that one can obtain stretch 2 using $O(m^{1/3}n^{4/3})$ space, and so if $m$
is subquadratic in $n$ then the space usage is also subquadratic. Moreover,
Pǎtraşcu and Roditty [23] showed that one cannot beat stretch 2 with
subquadratic space even for graphs where $m=\tilde{O}(n)$, based on the set-
intersection hypothesis.

In this paper we explore the conditions for which an ADO can be stored using
subquadratic space while supporting a sub-2 stretch. In particular, we show
that if the maximum degree in $G$ is $\Delta_{G}\leq O(n^{1/2-\varepsilon})$
for some $0<\varepsilon\leq 1/2$, then there exists an ADO for $G$ that uses
$\tilde{O}(n^{2-\frac{2\varepsilon}{3}})$ space and has a sub-2 stretch.

Moreover, we prove a conditional lower bound, based on the set intersection
hypothesis, which states that for any positive integer $k\leq\log n$,
obtaining a sub-$\frac{k+2}{k}$ stretch for graphs with maximum degree
$\Theta(n^{1/k})$ requires quadratic space. Thus, for graphs with maximum
degree $\Theta(n^{1/2})$, obtaining a sub-2 stretch requires quadratic space.

##  1 Introduction

One of the most fundamental and classic problems in algorithmic research is
the task of computing distances in graphs. Formally, given an undirected
unweighted graph $G=(V,E)$, $|V|=n$ and $|E|=m$, the distance between two
vertices $u,v\in V$, denoted $d(u,v)$, is the length of a shortest path
between $u$ and $v$. A central problem in distance computations is the _all-
pairs shortest paths_ (APSP) problem [18, 10, 20, 16, 33, 12, 21] where the
objective is to compute the distances between every pair of vertices in the
graph. A main disadvantage in handling the output of the APSP problem is that
storing the distances between every pair of vertices in the graph requires
$\Omega(n^{2})$ space. As in many other problems in computer science, the lack
of space efficiency in solving the APSP problem has motivated researchers to
search for a tradeoff between space and accuracy. As a result, one central
form of the APSP problem emerging from this line of research is constructing
an _approximate distance oracle_ where we sacrifice accuracy for space
efficiency.

##### Approximate Distance Oracles.

An approximate distance oracle (ADO) is a space efficient data structure that
produces distance estimations between any two vertices in the graph in
constant or near-constant time. Formally, given two vertices, $u,v\in V$, an
ADO returns an estimation $\hat{d}(u,v)$ for the distance between $u$ and $v$
that satisfies: $d(u,v)\leq\hat{d}(u,v)\leq\alpha\cdot d(u,v)$, for some real
$\alpha>1$ which is called the _stretch_ of the ADO. If the estimation of the
ADO satisfies $d(u,v)\leq\hat{d}(u,v)\leq\max\\{d(u,v),\,\alpha\cdot
d(u,v)+\beta\\}$ for some reals $\alpha>1$ and $\beta$ (which can be
negative), we say that the stretch of the ADO is an $(\alpha,\beta)$-stretch.

##### ADO for general graphs.

ADOs were originally presented by Thorup and Zwick [30] who designed a
randomized algorithm that for any positive integer $k$ constructs an ADO for
_weighted_ undirected graphs in $O(kmn^{1/k})$ time that uses $O(kn^{1+1/k})$
space and returns a $2k-1$-stretch in $O(k)$ query time.

Thorup and Zwick [30] showed that the space usage of their ADO construction
for their given stretch is optimal for _general graphs_ based on the girth
conjecture of Erdős. Moreover, for stretch 3 (when $k=1$), the appropriate
case of the girth conjecture is known to be true (due to complete bipartite
graphs), and so the quadratic (in $n$) space lower bound for this case is
unconditional. Notice that constructing an exact distance oracle in quadratic
space is trivial.

In the case where one allows for an additive error, Pǎtraşcu and Roditty [23]
designed an algorithm which constructs a $(2,1)$-stretch ADO for unweighted
graphs using $O(n^{5/3})$ space and $O(1)$ query time. Their result
demonstrates that in such a case the multiplicative error can be reduced while
still using subquadratic space.

##### ADO for sparse graphs.

The (conditional) lower bound of Thorup and Zwick [30] does not apply to
sparser graphs with $m=o(n^{1+1/k})$, and indeed additional results show that
it is possible to use subquadratic space and return a sub-3 stretch in such
cases. Specifically, Pǎtraşcu and Roditty [23], designed an algorithm that
constructs a 2-stretch ADO using $O(m^{1/3}n^{4/3})$ space, and so for
subquadratic $m$ the space usage is subquadratic. Pǎtraşcu, Roditty and Thorup
[24] presented additional tradeoffs for sub-3 stretch using subquadratic space
for graphs where $m=\tilde{O}(n)$111Throughout this paper we use $\sim$ when
suppressing poly-logarithmic factors in asymptotic complexities.. Roddity and
Tov [27] improved the stretch of the ADO presented by Thorup and Zwick [30]
while using the same space for graphs with $m=\tilde{O}(n)$.

##### Conditional lower bounds and set-intersection.

Pǎtraşcu and Roditty [23] proved a lower bound for the space usage of sub-2
stretch ADOs (i.e., ADOs whose stretch is strictly less than 2) that holds
(even) for sparse graphs, conditioned on the space usage for data structures
that solve the following set intersection problem.

######  Problem 1.1.

Let $X=\log^{c}N$ for a large enough constant $c$. Construct a data structure
that preprocesses sets $S_{1},\dots,S_{N}\subseteq[X]$, and answers queries of
the form “does $S_{i}$ intersect $S_{j}$?” in constant time.

The lower bound proof by Pǎtraşcu and Roditty [23] is based on the following
hypothesis.

######  Hypothesis 1.2 ([23, 17]).

A data structure that solves Problem 1.1 requires $\tilde{\Omega}(N^{2})$
space.

Since understanding the reduction by Pǎtraşcu and Roditty [23] is useful for
our results, we provide an overview of their reduction tailored to our needs.
Given an instance of Problem 1.1, we construct a 3 _layered_ graph, where
edges are only between adjacent layers, as follows. The first layer is
$V_{L}=\\{v_{1},\ldots,v_{N}\\}$, the second layer is $V_{M}=X$, and the third
layer is $V_{R}=\\{u_{1},\ldots,u_{N}\\}$. Vertices $v_{i}$ and $u_{i}$
represent $S_{i}$, and so for each set $S_{i}$ and each $x\in S_{i}$, we add
edges $(v_{i},x)$ and $(x,u_{i})$. Notice that the graph contains $\Theta(N)$
vertices. It is straightforward to observe that $S_{i}\cap S_{j}\neq\emptyset$
if and only if there is a path of length 2 between $v_{i}$ and $u_{j}$.
Moreover, since the graph is a 3 layered graph and the representatives of the
sets are at the outer layers, there are no paths of length $3$ between
representatives of sets. Thus, one can solve Problem 1.1 using a solution to
the following problem (for $a=2$ and $b=4$).

######  Problem 1.3.

For positive integers $a$ and $b$, an _$(a,b)$ -distinguisher oracle_ for a
graph $G=(V,E)$, is a data structure that, given $u,v\in V$ establishes in
constant time whether $d(u,v)\leq a$ or $d(u,v)\geq b$. If $a<d(u,v)<b$ then
the data structure can return any arbitrary answer.

We conclude that a $(2,4)$-distinguisher oracle that uses $f(n)$ space can be
used to solve Problem 1.1 using $f(N)$ space by applying the oracle onto the 3
layered graph. Finally, since a sub-2 stretch ADO is a $(2,4)$-distinguisher
oracle, any sub-2 stretch ADO must use at least $\Omega(n^{2})$ space.

###  1.1 Main results: When can we beat stretch 2 with subquadratic space?

The line of work by [23, 24, 27] is a natural research path given the
observation that the (conditional) lower bounds of [30] apply only to graphs
with $m=\Omega(n^{1+1/k})$. Similarly, a natural goal, which we address in
this paper, is to understand for which families of graphs can an ADO beat
stretch $2$ using subquadratic space. In particular, the conditional lower
bound proof of Pǎtraşcu and Roditty [23] does not apply to graphs with maximum
degree of $n^{\frac{1}{2}-\Omega(1)}$, since in such graphs the number of
paths of length 2 is $n^{2-\Omega(1)}$, and so constructing a subquadratic
space $(2,4)$-distinguisher oracle is straightforward (by explicitly storing
all length 2 paths).

Thus, a natural goal, which we investigate in this paper, is to understand the
relationship between the maximum degree of $G$, denoted by $\Delta_{G}$, and
the best possible stretch obtainable for an ADO using subquadratic space. To
address this question, we present two main results. The first result is an
upper bound for $\Delta_{G}=n^{\frac{1}{k}-\Omega(1)}$ which is summarized in
the following Theorem. For $k=2$, the theorem implies a subquadratic sub-2
stretch ADO for graphs for which $\Delta_{G}\leq
O(n^{\frac{1}{2}-\Omega(1)})$.

######  Theorem 1.4.

For any graph $G$ and positive integer $k=O(1)$ for which $\Delta_{G}\leq
O(n^{\frac{1}{k}-\varepsilon})$ for some real $0<\varepsilon\leq 1/k$, there
exists an ADO for $G$ that uses $\tilde{O}(n^{2-\frac{k\varepsilon}{3}})$
space and has a $(2,1-k)$-stretch.

The second result is a conditional lower bound, conditioned on Hypothesis 1.2,
that applies when $\Delta_{G}=\Theta(n^{1/k})$, for all integers $k\geq 1$
222The case $k=1$ was proven by Thorup and Zwick [30] to hold unconditionally.
Thus, Theorem 1.5 focuses on $k\geq 2$.. The conditional lower bound is
summarized in the following Theorem.

######  Theorem 1.5.

Let $2\leq k\leq\log n$. Assuming Hypothesis 1.2, a sub-$\frac{k+2}{k}$
stretch ADO for graphs with $n$ vertices and maximum degree $\Theta(n^{1/k})$
must use $\tilde{\Omega}(n^{2})$ space.

When $k=2$, the conditional lower bound of Theorem 1.5 implies that Theorem
1.4 is essentially optimal, in the sense that there is no ADO for graphs with
a maximum degree of $\Theta(n^{1/2})$ that still use subquadratic space and
has a sub-2 stretch.

###  1.2 Organization

The rest of this paper is organized as follows. In Section 1.3 we provide an
overview of the main ideas used in this paper. In Section 1.4 we survey some
additional related work. In Section 2 we provide some definitions that are
used in the more technical parts of the paper. In Section 3 we prove some
useful lemmas that are used in the proof of Theorem 1.4, which is described in
Section 4 together with the construction of our new ADO. In Section 5 we prove
Theorem 1.5. Finally, in Section 6 we provide some conclusions and describe a
natural open problem.

###  1.3 Overview of Results and Techniques

In this section we describe an overview of the intuition and techniques used
to obtain our main results.

####  1.3.1 Upper Bound: A New ADO

Since our new ADO is based on the ADO of Agarwal and Godfrey [6], that has a
$(2,1)$-stretch and uses $\tilde{O}(n^{5/3})$ space (which simplifies the ADO
of [23]), we provide an overview of the construction of their ADO.

The ADO constructed by Agarwal and Godfrey [6] uses the concept of _bunches_
and _clusters_ introduced by Thorup and Zwick [29]. Following the conventions
of Thorup and Zwick [29, 30], for a vertex $v\in V$, let $p_{A}(v)$ be the
vertex in $A$ which is closest to $v$ (breaking ties arbitrarily). The _bunch_
$B_{A}(v)$ of $v$ with respect to $A$ is defined as $B_{A}(v)=\\{w\in V\mid
d(v,w)<d(v,p_{A}(v))\\}$. The _cluster_ $C_{A}(w)$ of $w$ with respect to $A$
is defined as $C_{A}(w)=\\{v\in V\mid d(w,v)<d(v,p_{A}(v))\\}$. We omit $A$
from the notation when it is clear from context. Thorup and Zwick [29]
presented an algorithm that computes a set $A$ of size $\tilde{O}(s)$ such
that $|B(v)|,|C(v)|\leq 4n/s$, for every $v\in V$. The ADO of Agarwal and
Godfrey [6] uses a hitting set $A$ of size $\tilde{O}(n^{2/3})$ such that for
every $v\in V$, $|B(v)|,|C(v)|\leq O(n^{1/3})$.

Given two vertices $u,v\in V$, the ADO first tests whether $B(u)\cap
B(v)\neq\emptyset$, and, if so, then the ADO returns the exact distance
$d(u,v)$. The method for testing whether the two bunches intersect is based on
the observation (which follows from the definitions of bunch and cluster) that
$B(u)\cap B(v)\neq\emptyset$ if and only if $u\in C(B(v))$333For $S\subseteq
V$, let $C(S)=\bigcup\limits_{u\in S}C(u)$.. Thus, each vertex $v\in V$ stores
the exact distances to all vertices in $C(B(v))$, and now, the case of
$B(u)\cap B(v)\neq\emptyset$ costs constant time and returns an exact
distance. To deal with the case of $B(u)\cap B(v)=\emptyset$, the oracle
stores the distances of pairs in $V\times A$, and the ADO returns the minimum
of either the length of the shortest path between $u$ and $v$ passing through
$p(u)$ or the length of the shortest path between $u$ and $v$ passing through
$p(v)$. The space usage is $O(n^{5/3})$ for storing $C(B(v))$ for every $v\in
V$, and $\tilde{O}(n|A|)=\tilde{O}(n^{5/3})$ for storing the distances for all
pairs in $V\times A$.

##### Intuition for the new ADO.

Our new ADO construction is based on the following intuition regarding the ADO
construction of Agarwal and Godfrey [6]. If we enlarge $B(u)$ by moving $p(u)$
to a further vertex (from $u$), then we would increase the likelihood of
$B(u)\cap B(v)\neq\emptyset$, and so the ADO would return exact distances for
more pairs of vertices. However, in such a case, the quality guarantee on the
stretch obtained by approximating $d(u,v)$ with the shortest path from $u$ to
$v$ that passes through $p(u)$ becomes worse. Part of the challenge is to
balance the size of $B(u)$ which affects the usefulness of the intersections
and the role of $p(u)$ when approximating the distances.

Our approach, intuitively, is to separate the definition of $p(u)$ used for
the approximations and the set chosen for the intersections. Specifically, the
definition of $p(u)$ remains unchanged relative to $A$ (we do however change
the size of $A$), but instead of testing whether $B(u)\cap B(v)\neq\emptyset$,
we use a larger set $N(u)$ (which contains $B(u)$), and test whether $N(u)\cap
B(v)\neq\emptyset$ (or $B(u)\cap N(v)\neq\emptyset$). Testing whether
$N(u)\cap B(v)\neq\emptyset$ is implemented by storing all of the distances
between $u$ and vertices in $C(N(u))$. We remark that one may consider the
possibility of testing whether $N(u)\cap N(v)\neq\emptyset$ instead of testing
whether $N(u)\cap B(v)\neq\emptyset$, however, such an approach seems to
require too much space.

Recall that Agarwal and Godfrey [6] obtained a $(2,1)$-stretch. In our
algorithm, we choose $N(u)$ in such a way that when $N(u)\cap B(v)=\emptyset$
then $\min_{x\in B(u),y\in B(v)}\\{d(x,y)\\}>k$ if $\Delta_{G}\leq
O(n^{\frac{1}{k}-\Omega(1)})$, which ends up reducing the additive component
of the stretch by at least $k$ (see 4.2). Thus, the approximation of the ADO
is always at most $(2,1-k)$, which is less than stretch 2 for $k\geq 2$.

####  1.3.2 Conditional Lower bound

In Section 5 we prove the following lemma, which directly implies Theorem 1.5
since a sub-$\frac{k+2}{k}$ stretch ADO is also a $(k,k+2)$-distinguisher
oracle.

######  Lemma 1.6.

Let $2\leq k\leq\log n$. Assuming Hypothesis 1.2, any $(k,k+2)$-distinguisher
oracle for graphs with $n$ vertices and maximum degree $\Theta(n^{1/k})$ must
use $\tilde{\Omega}(n^{2})$ space.

Notice that it is straightforward to construct a $(k,k+2)$-distinguisher
oracle for graphs with $n$ vertices and maximum degree
$\Theta(n^{\frac{1}{k}-\varepsilon})$ in $O(n^{2-k\varepsilon})$ space by
storing all pairs of vertices at distance exactly $k$. Thus, Lemma 1.6 shows
that such a construction is essentially optimal.

##### The challenges.

There are two issues that need to be addressed in order to extend the
reduction in a way that proves Lemma 1.6. The first is to adjust the distances
so that $S_{i}\cap S_{j}\neq\emptyset$ if and only if $d(v_{i},u_{j})=k$, and
otherwise, $d(v_{i},u_{j})\geq k+2$. The second issue is that the degrees of
vertices in $V_{M}$ need to be adjusted to be at most $\tilde{O}(N^{1/k})$. In
order to simplify our intuitive explanation, we focus our attention to the
special case where $X=\\{x\\}$ has only one element.

One straightforward way of dealing with the first issue is to replace vertex
$x\in V_{M}$ with a path $P_{x}=(w_{1},\ldots,w_{k-1})$ of length $k-2$, and
for each $S_{i}$ that contains $x$ we add edges $(v_{i},w_{1})$ and
$(w_{k-1},u_{i})$. Thus, the constructed graph would be a $k+1$ layered graph.
The number of vertices in such a graph is $O(k+N)=O(N)$, and the distance
between vertices in the first and last layers are $k+2q$ for some integer
$q\geq 0$. However, we still need to address the second issue of bounding the
maximum degree, since $w_{1}$ and $w_{k-1}$ may have a very high degree
corresponding to the number of sets containing $x$.

On the other hand, one initial idea (that does not work) for dealing with the
second issue is to replace $x\in V_{M}$ (in the original 3 layered graph) with
$N$ vertices $y_{1},y_{2},\ldots,y_{N}$, and for each $S_{i}$ that contains
$x$ we add edges $(v_{i},y_{i})$ and $(y_{i},u_{i})$. Now the maximum degree
of each node is constant, however, for $i\neq j$ such that $x\in S_{i}\cap
S_{j}$, there is no path from $v_{i}$ to $u_{j}$. This idea is missing the
functionality of the path $P_{x}$ which allows us to connect more than one
pair of vertices from $V_{L}\times V_{R}$.

##### Combining approaches.

Our reduction makes use of an underlying $k+1$ layered graph $\mathcal{L}$,
called the _infrastructure_ graph, which has the following three properties:
(i) each layer contains $N$ vertices,  (ii) there is a path of length $k$ from
every vertex in the first layer to every vertex in the last layer, and  (iii)
the degree of every vertex is at most $2N^{1/k}$.  The layers of $\mathcal{L}$
are numbered $0$ to $k$. The vertices in each layer are (separately) indexed
with integers from $1$ to $N$, and the construction of $\mathcal{L}$ is based
on the base $N^{1/k}$ representation of the these indices: for $1\leq t\leq
k$, vertices from layer $t-1$ are connected with vertices from layer $t$ if
and only if the base $N^{1/k}$ representation of their corresponding indices
are the same, except for possibly the $t$’th digit. Similar to before, we
denote the first layer of $\mathcal{L}$ by $V_{L}=\\{v_{1},\ldots,v_{N}\\}$
and the last layer by $V_{R}=\\{u_{1},\ldots,u_{N}\\}$.

Finally, we construct a $k+1$ layered graph $G_{x}$ which is intuitively
obtained by removing from $\mathcal{L}$ edges touching either $v_{i}$ or
$u_{i}$ for every $S_{i}$ that does not contain $x$. Thus, in $G_{x}$, if
$x\in S_{i}\cap S_{j}$ then there is a path of length $k$ from $v_{i}$ to
$u_{j}$ in $G_{x}$, and otherwise, there is no path from $v_{i}$ to $u_{j}$ in
$G_{x}$.

We remark that in the general case, where $|X|$ may be larger than 1, we
combine $G_{x}$ for different $x\in X$ in a special way, and so we may
introduce paths from $v_{i}$ to $u_{j}$ even if $S_{i}\cap S_{j}=\emptyset$.
However, since the resulting graph is still a $k+1$ layered graph, and we are
interested in paths between vertices in the first layer and vertices in the
last layer, the lengths of such paths must be at least $k+2$. Thus, a
$(k,k+2)$-distinguisher oracle on the combined graph suffices for solving 1.1.
See Section 5 for more details.

###  1.4 Additional related work

Different aspects of Thorup and Zwick [30] ADOs were studied since they were
introduced for the first time. Chechik [14, 13] reduced the query time from
$O(k)$ to $O(1)$, while keeping the stretch and the space unchanged. (See also
[32, 22].) Roditty, Thorup, and Zwick [26] presented a deterministic algorithm
that constructs an ADO in $\widetilde{O}(mn^{1/k})$ time while keeping the
stretch and the space unchanged. Baswana and Kavitha [9] presented an
algorithm with $O(n^{2}\log n)$ running time.444For $k=2$ the query time is
$O(\log n)$. For $k>2$ the query time is $O(k)$.. Baswana, Goyaland and Sen
[8] presented an $\widetilde{O}(n^{2})$ time algorithm that computes a
$(2,3)$-distance oracle with $\widetilde{O}(n^{5/3})$ space. Sommer [28]
presented an $\widetilde{O}(n^{2})$ time algorithm that computes a
$(2,1)$-distance oracle with $\widetilde{O}(n^{5/3})$ space. Akav and Roditty
[7] presented the first sub-quadratic time algorithm that constructs an ADO
with stretch better than $3$. They presented an $O(n^{2-\epsilon})$-time
algorithm that constructs a ADO with $O(n^{11/6})$ space and
$(2+\epsilon,5)$-stretch. Chechik and Zhang [15] improved the result of Akav
and Roditty [7]. Among their results is an $O(m+n^{1.987})$ time algorithm
that constructs an ADO with $(2,1)$-stretch and $\widetilde{O}(n^{5/3})$
space. Following the work by Pǎtraşcu and Roditty [23] who constructed an ADO
for unweighted graphs that uses $O(n^{5/3})$ space and returns a
$(2,1)$-stretch in $O(1)$ time, Abraham and Gavoille [2] extended the ADO by
Pǎtraşcu and Roditty [23] for all even stretch values, by constructing for any
integer $k\geq 2$, an ADO of size $\tilde{O}(n^{1+2/(2k-1)})$ with a
$(2k-2,1)$-stretch returned in $O(k)$ time. Pǎtraşcu, Roditty and Thorup [24]
focused on analyzing sparse graphs where $m=\tilde{O}(n)$ and noted that both
the ADOs by Thorup and Zwick [30], and the ADOs by Abraham and Gavoille [2]
use a space complexity that can be described by the curve
$S(\alpha,m)=\tilde{O}(m^{1+2/(\alpha+1)})$ where $\alpha$ is the stretch of
the ADO and $m$ is the number of edges in the graph. Pǎtraşcu, Roditty and
Thorup [24] extended the curve $S(\alpha,m)$ to work for non integer stretch
values $\alpha>2$. Although our research focuses on constant query time ADOs,
another branch of research includes ADOs that have non constant query time [5,
25, 4, 3, 11].

In the lower bound regime, the problem of constructing a $(2,4)$-distinguisher
oracle was analyzed from the perspective of time complexity as well. V.
Williams and Xu [31] showed that for graphs with degree of at most $n^{1/2}$,
the problem of determining for each edge in the graph whether it is in a
triangle in $O(n^{2-\varepsilon})$ for some $\varepsilon>0$ is hard under
either the $\mathsf{3SUM}$ or $\mathsf{APSP}$ hypotheses. Since there exists a
standard reduction from the problem of determining for each edge in the graph
whether it is in a triangle to the problem of constructing a
$(2,4)$-distinguisher oracle (see [1]), a $(2,4)$-distinguisher oracle is also
hard to construct in subquadratic time for graphs with degree of at most
$n^{1/2}$ under either the $\mathsf{3SUM}$ or $\mathsf{APSP}$ hypotheses.

The problem of constructing a $(k,k+2)$-distinguisher oracle for a general
integer $k\geq 2$ was also studied in the past in terms of time complexity.
Dor, Halperin and Zwick [19] showed that if all distances in an undirected $n$
vertex graph can be approximated with an additive error of at most $1$ in
$O(A(n))$ time, then _Boolean matrix multiplication_ on matrices of size
$n\times n$ can also be performed in $O(A(n))$ time. Dor, Halperin and Zwick
[19] conclude that constructing a $(k,k+2)$-distinguisher oracle for an
integer $k\geq 2$ is at least as hard as multiplying two Boolean matrices.

##  2 Preliminaries

Let $d_{G}(u,v)$ be the distance between vertices $u$ and $v$ in the graph
$G$. The eccentricity of a vertex $v\in V$ in a graph $G$, denoted by
$ecc_{G}(v)$, is defined as $ecc_{G}(v)=\max_{u\in V}\\{d_{G}(v,u)\\}$. The
diameter of $G$ is defined as $diam_{G}=\max_{v\in V}\\{ecc_{G}(v)\\}$ and the
radius of $G$ is defined as $rad_{G}=\min_{v\in V}\\{ecc_{G}(v)\\}$.

The eccentricity of a vertex $v$ can be thought of as the distance between $v$
and the last vertex met during a _Breadth First Search_ (BFS) of the graph
starting at $v$. Since our goal is to construct an ADO that uses subquadratic
space, we cannot afford to store a separate BFS tree for each vertex. Instead,
the construction algorithm of our ADO will store only a partial BFS tree for
each vertex by truncating the BFS scan after some number of vertices.
Motivated by this notion of a truncated scan, we introduce the following
generalization of eccentricity which turns out to be useful for our purposes.

Let $N_{G}(v,s)$ be the first $s$ vertices met during a BFS555 The traversal
order of vertices in the same layer during the BFS execution does not matter
as long as the order is consistent.  starting from $v$ in the graph $G$, i.e.,
the $s$ closest vertices to $v$ (excluding $v$). If $s$ is not an integer,
then let $N(v,s)=N(v,\lfloor s\rfloor)$. For an integer $r\geq 0$, define
$L_{G}(v,r)=\\{u\in V\setminus\\{v\\}\mid d_{G}(u,v)=r\\}$ and
$T_{G}(v,r)=\\{u\in V\mid 0<d_{G}(u,v)\leq r\\}$. Notice that
$T_{G}(v,r)=\bigcup\limits_{i=1}^{r}L_{G}(v,i)$. For any real $1\leq s\leq
n-1$, define $ecc_{G}(v,s)$ to be the maximum integer
$k\in\left[0,ecc_{G}(v)\right]$ for which $T_{G}(v,k)\subseteq N_{G}(v,s)$.
Notice that $ecc_{G}(v,n-1)=ecc_{G}(v)$. Define $rad_{G}(s)=\min_{v\in
V}\\{ecc_{G}(v,s)\\}$. Notice that $rad_{G}(n-1)=rad_{G}$. We omit the
subscript $G$ when using the definitions above whenever $G$ is clear from
context.

##  3 Useful Lemmas

In this section we prove several useful properties of the graph attributes
defined in Section 2 which will be used throughout the paper.

The following observation and corollary address the relationship between
$T(v,r)$ and $N(v,s)$, and follow from the definition of BFS.

######  Observation 3.1.

Let $G=(V,E)$ be an unweighted undirected graph, with $|V|=n$. For any $v\in
V$ and integers $s$ and $r$ such that $1\leq s<n$ and $1\leq r\leq diam_{G}$,
either  (i) $T(v,r)\subset N(v,s)$,  (ii) $N(v,s)\subset T(v,r)$, or  (iii)
$N(v,s)=T(v,r)$ .

######  Corollary 3.2.

Let $G=(V,E)$ be an unweighted undirected graph, with $|V|=n$. For any $v\in
V$ and integers $s$ and $r$ such that $1\leq s<n$ and $1\leq r\leq diam_{G}$,
(i) if $|T(v,r)|<|N(v,s)|$ then $T(v,r)\subset N(v,s)$,  (ii) if
$|N(v,s)|<|T(v,r)|$ then $N(v,s)\subset T(v,r)$, and  (iii) if
$|N(v,s)|=|T(v,r)|$ then $N(v,s)=T(v,r)$ .

The following useful property addresses the relationship between $T(v,r)$ and
$N(v,s)$ for the special cases where either $r=ecc(v,s)$ or $r=ecc(v,s)+1$.

######  Property 3.3.

Let $G=(V,E)$ be an unweighted undirected graph, with $|V|=n$. For any $v\in
V$ and integer $s$ such that $1\leq s<n$, we have:  (i)
$T(v,ecc(v,s))\subseteq N(v,s)$, and  (ii) if $s<n-1$, then
$T(v,ecc(v,s)+1)\not\subseteq N(v,s)$ .

###### Proof.

By definition, $ecc(v,s)$ is the largest integer $k\in\left[0,ecc(v)\right]$
for which $T(v,k)\subseteq N(v,s)$. Thus,  (i) $T(v,ecc(v,s))\subseteq
N(v,s)$, and  (ii) if $ecc(v,s)<ecc(v)$ then $T(v,ecc(v,s)+1)\not\subseteq
N(v,s)$ . If $s<n-1$, it must be that $ecc(v,s)<ecc(v)$, since if we assume
towards a contradiction that $ecc(v,s)=ecc(v)$ for some $s<n-1$ then
$T(v,ecc(v,s))=T(v,ecc(v))=V\setminus\\{v\\}=N(v,n-1)$ but on the other hand,
by definition of $ecc(v,s)$, we have $T(v,ecc(v,s))\subseteq N(v,s)\subset
N(v,n-1)$, which is a contradiction. ∎

The following lemma states that $ecc_{G}(v,s)$ exhibits a behavior that is
similar to the behavior of the distance function which cannot decrease when
removing edges and vertices from $G$.

######  Lemma 3.4.

Let $G=(V,E)$ be an unweighted undirected graph, $V^{\prime}\subseteq V$, and
let $G^{\prime}$ be the subgraph of $G$ induced by the vertices in
$V^{\prime}$. For any vertex $v\in V^{\prime}$ and for any integer $s$ such
that $1\leq s<|V^{\prime}|$, it holds that $ecc_{G}(v,s)\leq
ecc_{G^{\prime}}(v,s)$.

###### Proof.

Given an integer $1\leq s<|V^{\prime}|$, let $r=ecc_{G}(v,s)$ and
$r^{\prime}=ecc_{G^{\prime}}(v,s)$. We want to show that $r\leq r^{\prime}$.
By definition of $ecc_{G^{\prime}}(v,s)$, $r^{\prime}=ecc_{G^{\prime}}(v,s)$
is the largest value for which $T_{G^{\prime}}(v,r^{\prime})\subseteq
N_{G^{\prime}}(v,s)$. Thus, in order to show that $r\leq r^{\prime}$, it
suffices to show that $T_{G^{\prime}}(v,r)\subseteq N_{G^{\prime}}(v,s)$.

For any vertex pair $u,w\in V^{\prime}$, we have $d_{G}(u,w)\leq
d_{G^{\prime}}(u,w)$ since $G^{\prime}$ is a subgraph of $G$. Thus,

$\displaystyle T_{G^{\prime}}(v,r)$ $\displaystyle=\\{u\in V^{\prime}\mid
0<d_{G^{\prime}}(v,u)\leq r\\}$ $\displaystyle\subseteq\\{u\in V\mid
0<d_{G}(v,u)\leq r\\}$ $\displaystyle=T_{G}(v,r)$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{Property \ref{prop:1}}}\end{subarray}}{\subseteq}N_{G}(v,s).$

This implies that
$|T_{G^{\prime}}(v,r)|\leq|N_{G}(v,s)|=s=|N_{G^{\prime}}(v,s)|$. By Corollary
3.2, since $|T_{G^{\prime}}(v,r)|\leq|N_{G^{\prime}}(v,s)|$ then
$T_{G^{\prime}}(v,r)\subseteq N_{G^{\prime}}(v,s)$, as required. ∎

###  3.1 The Logarithmic-Like Behavior of $ecc(v,s)$

In the following lemma, which is an important ingredient in the analysis of
our new ADO, we show that $ecc(v,s)$ satisfies a logarithmic-like behavior.
Specifically, $\log(xy)=\log x+\log y$. The reason for this behavior is that
the number of vertices in each layer of a BFS tree expands in a similar way to
an exponential function. For a tree-graph $G$ with minimum degree $\delta$
rooted at a vertex $v$, for integers $0\leq i<t<ecc(v)$ it holds that
$|L(v,t)|\geq\delta^{i}\cdot|L(v,t-i)|$. Since the number of vertices in every
layer of the rooted tree grows exponentially, the eccentricity $ecc(v,s)$
grows logarithmically (in relation to $s$). Unlike in trees where the
expansion of the number of vertices in every layer of a BFS can be analyzed
using $\delta$, for general graphs, in order to achieve a lower bound for the
expansion rate of the eccentricity of the vertices, we use $rad_{G}(s)$
instead.

######  Lemma 3.5.

Let $G=(V,E)$ be an unweighted undirected graph, with $|V|=n$. For any vertex
$v\in V$ and integers $s_{1},s_{2}\geq 1$ such that $s_{1}(s_{2}+1)<n-1$, it
holds that $ecc_{G}(v,s_{1}(s_{2}+1))\geq ecc_{G}(v,s_{1})+rad_{G}(s_{2})$.

###### Proof.

Assume towards a contradiction that
$ecc_{G}(v,s_{1}(s_{2}+1))<ecc_{G}(v,s_{1})+rad_{G}(s_{2})$. Thus,
$ecc_{G}(v,s_{1}(s_{2}+1))+1\leq ecc_{G}(v,s_{1})+rad_{G}(s_{2})$.

Let $T_{BFS}$ be a BFS tree rooted at $v$ in graph $G$. Let
$\ell=|L(v,ecc_{G}(v,s_{1}))|$ and let $u_{1},u_{2},\dots,u_{\ell}$ be the
vertices in $L(v,ecc_{G}(v,s_{1}))$. For any $i$, where $1\leq i\leq\ell$, let
$V_{i}$ be the set of descendant of $u_{i}$ in $T_{BFS}$ and let $G_{i}$ be
the graph induced by $V_{i}$ in $G$666It is important to note that for all
scans referenced in this proof, which include a BFS procedure of $G$ starting
at $v$ and BFS procedures of $G_{i}$ starting at $u_{i}$ for $1\leq
i\leq\ell$, we require a consistent order of scanning, i.e., that for a given
$1\leq i\leq\ell$, and vertices $x,x^{\prime}\in V_{i}\subseteq V$, if $x$ is
scanned before $x^{\prime}$ in $G$ then $x$ should also be scanned before
$x^{\prime}$ in $G_{i}$ (and vice versa). This is a valid requirement since
for any vertices $y,y^{\prime}\in V_{i}\subseteq V$, $d_{G}(v,y)\leq
d_{G}(v,y^{\prime})$ if and only if $d_{G_{i}}(u_{i},y)\leq
d_{G_{i}}(u_{i},y^{\prime})$..

Let $\mu=\min_{i\in[1,\ell]}\\{ecc_{G_{i}}(u_{i},s_{2})\\}$. We will show
that:

$\displaystyle\\{u\in V\mid ecc_{G}(v,s_{1})<d_{G}(v,u)\leq
ecc_{G}(v,s_{1})+\mu\\}\subseteq\bigcup\limits_{i=1}^{\ell}N_{G_{i}}(u_{i},s_{2}).$
(1)

Let $w\in\\{u\in V\mid ecc_{G}(v,s_{1})<d_{G}(v,u)\leq
ecc_{G}(v,s_{1})+\mu\\}$. By the definition of BFS, since
$d_{G}(v,w)>ecc_{G}(v,s_{1})$, $w$ must be a descendant of some vertex
$u_{j}$, and so $w\in V_{j}$. Since $T_{BFS}$ is a shortest path tree rooted
at $v$ and since $w\in V_{j}$, it must be that
$d_{G}(v,w)=d_{G}(v,u_{j})+d_{G}(u_{j},w)=ecc_{G}(v,s_{1})+d_{G}(u_{j},w)$. By
definition of $w$, $d_{G}(v,w)\leq ecc_{G}(v,s_{1})+\mu$. Thus,
$ecc_{G}(v,s_{1})+d_{G}(u_{j},w)\leq ecc_{G}(v,s_{1})+\mu$ and so
$d_{G}(u_{j},w)\leq\mu$.

By definition, $T_{G_{j}}(u_{j},ecc_{G_{j}}(u_{j},s_{2}))=\\{x\mid x\in
V_{j}\,\wedge\,0<d_{G_{j}}(u_{j},x)\leq ecc_{G_{j}}(u_{j},s_{2})\\}$. Since
$T_{BFS}$ is a shortest path tree, for any $y\in V_{j}$ it must be that
$d_{G_{j}}(u_{j},y)=d_{G}(u_{j},y)$. Thus,
$T_{G_{j}}(u_{j},ecc_{G_{j}}(u_{j},s_{2}))=\\{x\mid x\in
V_{j}\,\wedge\,0<d_{G}(u_{j},x)\leq ecc_{G_{j}}(u_{j},s_{2})\\}$.

Since $w\in V_{j}$, and since $d_{G}(u_{j},w)\leq\mu\leq
ecc_{G_{j}}(u_{j},s_{2})$, it must be that $w\in
T_{G_{j}}(u_{j},ecc_{G_{j}}(u_{j},s_{2}))$. By Property 3.3,
$T_{G_{j}}(u_{j},ecc_{G_{j}}(u_{j},s_{2}))\subseteq N_{G_{j}}(u_{j},s_{2})$.
It follows that every vertex in $\\{u\in V\mid ecc_{G}(v,s_{1})<d_{G}(v,u)\leq
ecc_{G}(v,s_{1})+\mu\\}$ must be included in $N_{G_{i}}(u_{i},s_{2})$ for some
$i$, thus confirming Equation (1).

By Property 3.3, $\\{u\in V\mid 0<d(v,u)\leq
ecc_{G}(v,s_{1})\\}=T(v,ecc_{G}(v,s_{1}))\subseteq N(v,s_{1})$. Combining with
Equation (1) we have that $\\{u\in V\mid 0<d(v,u)\leq
ecc_{G}(v,s_{1})\\}\cup\\{u\in V\mid ecc_{G}(v,s_{1})<d_{G}(v,u)\leq
ecc_{G}(v,s_{1})+\mu\\}\subseteq
N(v,s_{1})\cup\left(\bigcup\limits_{i=1}^{\ell}N_{G_{i}}(u_{i},s_{2})\right)$,
and so:

$\displaystyle\\{u\in V\mid 0<d(v,u)\leq
ecc_{G}(v,s_{1})+\mu\\}=T(v,ecc_{G}(v,s_{1})+\mu)\subseteq
N(v,s_{1})\cup\left(\bigcup\limits_{i=1}^{\ell}N_{G_{i}}(u_{i},s_{2})\right).$

Now,

$\displaystyle ecc_{G}(v,s_{1})+\mu$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{definition of
$\mu$}}\end{subarray}}{=}ecc_{G}(v,s_{1})+\min_{i\in[1,\ell]}\\{ecc_{G_{i}}(u_{i},s_{2})\\}$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\ \mathrlap{\text{by
Lemma
\ref{lem:1}}}\end{subarray}}{\geq}ecc_{G}(v,s_{1})+\min_{i\in[1,\ell]}\\{ecc_{G}(u_{i},s_{2})\\}$
$\displaystyle\geq ecc_{G}(v,s_{1})+\min_{u\in V}\\{ecc_{G}(u,s_{2})\\}$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{definition of
$rad_{G}(s_{2})$}}\end{subarray}}{=}ecc_{G}(v,s_{1})+rad_{G}(s_{2})$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{assumption}}\end{subarray}}{\geq}ecc_{G}(v,s_{1}(s_{2}+1))+1.$

Thus, $T(v,ecc_{G}(v,s_{1}(s_{2}+1))+1)\subseteq
T(v,ecc_{G}(v,s_{1})+\mu)\subseteq
N(v,s_{1})\cup\left(\bigcup\limits_{i=1}^{\ell}N_{G_{i}}(u_{i},s_{2})\right)$.

Notice that $\ell\leq s_{1}$, since, by Property 3.3,
$\ell=|L(v,ecc_{G}(v,s_{1}))|\leq|T(v,ecc_{G}(v,s_{1}))|\leq
N(v,s_{1})=s_{1}$. Therefore,

$\displaystyle|T(v,ecc_{G}(v,s_{1}(s_{2}+1))+1)|$
$\displaystyle\leq|N(v,s_{1})\cup\left(\bigcup\limits_{i=1}^{\ell}N_{G_{i}}(u_{i},s_{2})\right)|$
$\displaystyle\leq|N(v,s_{1})|+\sum\limits_{i=1}^{\ell}|N_{G_{i}}(u_{i},s_{2})|$
$\displaystyle\leq s_{1}+\ell\cdot s_{2}$ $\displaystyle\leq s_{1}+s_{1}\cdot
s_{2}$ $\displaystyle=s_{1}(1+s_{2})$ $\displaystyle=|N(v,s_{1}(s_{2}+1))|.$

By Corollary 3.2, it follows that $T(v,ecc_{G}(v,s_{1}(s_{2}+1))+1)\subseteq
N(v,s_{1}(s_{2}+1))$, which contradicts Property 3.3. ∎

##  4 The new ADO

In this section we introduce a new ADO which uses subquadratic space and
produces a stretch strictly smaller than $2$ for the family of graphs for
which $\Delta_{G}\leq O(n^{1/2-\varepsilon})$ where $0<\varepsilon\leq 1/2$.
The ADO is parameterized by a parameter $0\leq\alpha<1/3$ which quantifies the
tradeoff between the space and the stretch of the ADO. When $\alpha=0$ the ADO
is very similar to the ADO of Agarwal and Godfrey [6] which uses
$\tilde{O}(n^{5/3})$ space and has a $(2,1)$-stretch. For $0<\alpha<1/3$, the
ADO uses additional space and is able to improve the stretch of the ADO for
the family of graphs for which $\Delta_{G}\leq O(n^{3\alpha/2})$ .

###  4.1 The Construction Algorithm

The description of our construction algorithm follows the notations and
definitions described in Section 1.3.1. The construction begins with an
algorithm of Thorup and Zwick [29] that computes a set $A$ of size
$\tilde{O}(s)$ such that $|B(v)|,|C(v)|\leq 4n/s$, for every $v\in V$. In our
case we set $s=n^{2/3+\alpha}$, thus $|A|=\tilde{O}(n^{2/3+\alpha})$ and
$|B(v)|,|C(v)|\leq 4n^{1/3-\alpha}$, for every $v\in V$.

For every vertex $v\in V$, the ADO explicitly stores the distances between $v$
and every vertex in $C(N(v,16c\,n^{1/3+2\alpha}))$. In addition, for every
vertex $v\in V$ the ADO stores $p(v)$, $d(v,p(v))$ and the distances between
$v$ and every vertex in $A$.

A distance query between vertices $u$ and $v$ is answered as follows. If one
of the following conditions holds  (i) $u\in A$or $v\in A$,  (ii) $u\in
C(N(v,16c\,n^{1/3+2\alpha}))$or $v\in C(N(u,16c\,n^{1/3+2\alpha}))$ , then the
exact distance is returned. Otherwise, the ADO returns
$\hat{d}(u,v)=\min\\{d(u,p(u))+d(p(u),v),\,d(u,p(v))+d(p(v),v)\\}$. Notice
that the query time is constant.

In Claim 4.1, we show that the space complexity of the ADO is
$\tilde{O}(n^{5/3+\alpha})$ and in Claim 4.2, we show that the ADO satisfies a
$(2,1-rad(cn^{3\alpha}))$-stretch.

######  Claim 4.1.

The space complexity of the ADO is $\tilde{O}(n^{5/3+\alpha})$.

###### Proof.

Storing $p(v)$, $d(v,p(v))$ and the distances between $v$ and every vertex in
$A$, for all vertices $v\in V$, uses $\tilde{O}(n\cdot
n^{2/3+\alpha})=\tilde{O}(n^{5/3+\alpha})$ space. As mentioned in the
construction phase, $|B(v)|,|C(v)|\leq O(n^{1/3-\alpha})$ for every $v\in V$.
Thus, storing the distances between every vertex $v$ and
$C(N(v,16c\,n^{1/3+2\alpha}))$ requires $O(n\cdot n^{1/3-\alpha}\cdot
16c\,n^{1/3+2\alpha})=\tilde{O}(n^{5/3+\alpha})$ space as well, leading to an
overall space complexity of $\tilde{O}(n^{5/3+\alpha})$. ∎

######  Claim 4.2.

The distance estimation $\hat{d}(u,v)$ returned by the ADO satisfies
$d(u,v)\leq\hat{d}(u,v)\leq 2d(u,v)+1-rad(cn^{3\alpha})$.

###### Proof.

Notice that $d(u,v)\leq\hat{d}(u,v)$ since the ADO always returns a length of
some path in the graph between $u$ and $v$. It is left to show that
$\hat{d}(u,v)\leq 2d(u,v)+1-rad(cn^{3\alpha})$.

If the exact distance is stored in the ADO then $\hat{d}(u,v)=d(u,v)$ and the
claim follows. Consider the case that the exact distance is not stored. This
implies that $u,v\notin A$ and $v\notin C(N(u,16c\,n^{1/3+2\alpha}))$. Assume
towards a contradiction that $N(u,16c\,n^{1/3+2\alpha})\cap B(v)\neq\emptyset$
and let $w$ be a vertex such that $w\in N(u,16c\,n^{1/3+2\alpha})\cap B(v)$.
From the definitions of bunch and cluster, we have that $w\in B(v)$ if and
only if $v\in C(w)$. Thus, $v\in C(w)$, and since $w\in
N(u,16c\,n^{1/3+2\alpha})$, it must be that $v\in
C(N(u,16c\,n^{1/3+2\alpha}))$ which is a contradiction. Thus, we have that
$N(u,16c\,n^{1/3+2\alpha})\cap B(v)=\emptyset$.

$a$$b$$u$$v$$B(u)$$B(v)$$N\left(u,16n^{1/3\ +\
2\alpha}\right)$$1$$d(u,a)$$d(v,b)$$2$$3$$3$$2$$1$$x$$d(u,x)$${\displaystyle
P(u,v)}$ Figure 1: A query for $u,v\in V$ in the case that
$N(u,16c\,n^{1/3+2\alpha})\cap B(v)=\emptyset$. Since $x\in
N(u,16c\,n^{1/3+2\alpha})$, $b\in B(v)$ and $x$ and $b$ are both on a shortest
path between $u$ and $v$, it must be that $d(u,x)\leq d(u,b)-1$.

Let $P(u,v)$ be a shortest path between $u$ and $v$. Let $a$ be the furthest
vertex from $u$ in $B(u)\cap P(u,v)$, let $x$ be the furthest vertex from $u$
in $N(u,16c\,n^{1/3+2\alpha})\cap P(u,v)$ and let $b$ be the furthest vertex
from $v$ in $B(v)\cap P(u,v)$ (see Figure 1). Notice that, by definition of
$x$ and $ecc(v,s)$, if $T(u,d(u,x))\subseteq N(u,16c\,n^{1/3+2\alpha})$ then
$d(u,x)=ecc(u,16c\,n^{1/3+2\alpha})$ and if $T(u,d(u,x))\not\subseteq
N(u,16c\,n^{1/3+2\alpha})$ then $d(u,x)=ecc(u,16c\,n^{1/3+2\alpha})+1$. Thus,
we get that $d(u,x)\geq ecc(u,16c\,n^{1/3+2\alpha})$.

Since $N(u,16c\,n^{1/3+2\alpha})\cap B(v)=\emptyset$, $x\in
N(u,16c\,n^{1/3+2\alpha})$, $b\in B(v)$ and $x$ and $b$ are both on a shortest
path between $u$ and $v$, it must be that $d(u,x)\leq d(u,b)-1$. Since $b$ is
on a shortest path between $u$ and $v$, it holds that $d(u,b)=d(u,v)-d(v,b)$,
and so $d(u,x)\leq d(u,v)-d(v,b)-1$. Since $d(u,x)\geq
ecc(u,16c\,n^{1/3+2\alpha})$, it follows that:

$\displaystyle ecc(u,16c\,n^{1/3+2\alpha})\leq d(u,v)-d(v,b)-1.$ (2)

By Lemma 3.5, $ecc(u,\left\lceil 4n^{1/3-\alpha}\right\rceil)+rad(\left\lceil
cn^{3\alpha}\right\rceil)\leq ecc(u,(4n^{1/3-\alpha}+1)(cn^{3\alpha}+2))$.
Since $a\in B(u)$ and $|B(u)|\leq 4n^{1/3-\alpha}$, it follows from the
definitions of $ecc(v,s)$ and bunch that $d(u,a)\leq ecc(u,4n^{1/3-\alpha})$.
We have that:

$\displaystyle d(u,a)+rad(cn^{3\alpha})$ $\displaystyle\leq
ecc(u,4n^{1/3-\alpha})+rad(cn^{3\alpha})$ $\displaystyle\leq ecc(u,\left\lceil
4n^{1/3-\alpha}\right\rceil)+rad(\left\lceil cn^{3\alpha}\right\rceil)$
$\displaystyle\leq ecc(u,(4n^{1/3-\alpha}+1)(cn^{3\alpha}+2))$
$\displaystyle\leq ecc(u,16c\,n^{1/3+2\alpha})$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{Equation \eqref{eq:2}}}\end{subarray}}{\leq}d(u,v)-d(v,b)-1.$

Thus, $d(u,a)+d(b,v)\leq d(u,v)-rad(cn^{3\alpha})-1$. It follows that:

$\displaystyle 2\,\min\\{d(u,a),d(b,v)\\}\leq d(u,v)-rad(cn^{3\alpha})-1.$ (3)

Notice that by the definitions of bunch, $a$ and $p(u)$, it holds that
$d(u,p(u))=d(u,a)+1$. Similarly, $d(v,p(v))=d(v,b)+1$. Thus:

$\displaystyle\hat{d}(u,v)$
$\displaystyle\leq\min\\{d(u,p(u))+d(p(u),v),d(u,p(v))+d(p(v),v)\\}$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{triangle
inequallity}}\end{subarray}}{\leq}\min\\{2d(u,p(u))+d(u,v),2d(v,p(v))+d(u,v)\\}$
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{$d(u,p(u))=d(u,a)+1$ and
$d(v,p(v))=d(v,b)+1$}}\end{subarray}}{=}\min\\{2(d(u,a)+1)+d(u,v),2(d(v,b)+1)+d(u,v)\\}$
$\displaystyle\leq 2\min\\{d(u,a),d(v,b)\\}+2+d(u,v)$ (4)
$\displaystyle\underset{\begin{subarray}{c}\uparrow\\\
\mathrlap{\text{Equation
\eqref{eq:3}}}\end{subarray}}{\leq}d(u,v)-rad(cn^{3\alpha})+1+d(u,v)$
$\displaystyle=2d(u,v)+1-rad(cn^{3\alpha}).$ (5)

∎

By combining our ADO construction with Claims 4.1 and 4.2 we have proven the
following lemma.

######  Lemma 4.3.

For any graph $G$ with $n$ vertices, real $0\leq\alpha<\frac{1}{3}$ and
constant $c\geq 1$, it is possible to construct an ADO that uses
$\tilde{O}(n^{\frac{5}{3}+\alpha})$ space and has a
$(2,1-rad(cn^{3\alpha}))$-stretch.

###  4.2 Proof of Main Upper Bound Theorem

The following lemma connects $\Delta_{G}$ and $rad(s)$, which is the last
ingredient needed for proving Theorem 1.4.

######  Lemma 4.4.

Let $G=(V,E)$ be an unweighted undirected graph, with $|V|=n$. For any real
$s$ such that $1\leq s<n$, it holds that
$rad_{G}(s)\geq\lfloor\log_{\Delta_{G}}(s/2)\rfloor$.

###### Proof.

For any vertex $v$ and integer $t\geq 1$, $T(v,t)$ cannot include more than
$\Delta_{G}\cdot\sum_{i=0}^{t-1}(\Delta_{G}-1)^{i}$ vertices. Since
$\Delta_{G},t\geq 1$ we have that
$\Delta_{G}\cdot\sum_{i=0}^{t-1}(\Delta_{G}-1)^{i}\leq 2\cdot\Delta_{G}^{t}$
and so for any integer $t\geq 1$ such that $2\cdot\Delta_{G}^{t}<n$ it must be
that $T(v,t)\subseteq N(v,2\cdot\Delta_{G}^{t})$. By definition, $ecc(v,s)$ is
equal to the largest integer $x\in\left[0,ecc(v)\right]$ for which
$T(v,x)\subseteq N(v,s)$. Thus, $t\leq ecc(v,2\cdot\Delta_{G}^{t})$. Since
$t\leq ecc(v,2\cdot\Delta_{G}^{t})$ for any vertex $v$, it follows from the
definition of $rad(s)=\min_{v\in V}\\{ecc(v,s)\\}$ that $t\leq
rad(2\cdot\Delta_{G}^{t})$. Setting $s\geq 2\cdot\Delta_{G}^{t}$, or
$t\leq\log_{\Delta_{G}}(s/2)$, it follows that for any integer $t$ such that
$t\leq\log_{\Delta_{G}}(s/2)$ it must be that $t\leq
rad(2\cdot\Delta_{G}^{t})\leq rad(s)$. Thus,
$\lfloor\log_{\Delta_{G}}(s/2)\rfloor\leq rad(s)$. ∎

Finally, we are ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

Since $\Delta_{G}\leq O(n^{1/k-\varepsilon})$, there exists some positive real
$c_{1}$ such that $\Delta_{G}\leq c_{1}n^{1/k-\varepsilon}$. By Lemma 4.4,
$k=\lfloor\log_{\Delta_{G}}(\Delta_{G}^{k})\rfloor\leq\lfloor\log_{\Delta_{G}}(c_{1}^{k}n^{1-k\varepsilon})\rfloor\leq
rad_{G}(2c_{1}^{k}n^{1-k\varepsilon})$. Thus, the ADO from Lemma 4.3
constructed for $G$ using $\alpha=\frac{1-k\varepsilon}{3}$ and $c=2c_{1}^{k}$
will use $\tilde{O}(n^{2-\frac{k\varepsilon}{3}})$ space and produce a
distance estimation that satisfies
$d(u,v)\leq\hat{d}(u,v)\leq\max\\{d(u,v),\,2d(u,v)+1-rad_{G}(2c_{1}^{k}n^{1-k\varepsilon})\\}\leq\max\\{d(u,v),\,2d(u,v)+1-k\\}$.
∎

##  5 Reduction from the Set Intersection Problem

###### Proof of Lemma 1.6..

Given an instance of Problem 1.1, we construct a graph $G$ with
$n=\tilde{O}(N)$ vertices and $\Delta_{G}=O(n^{1/k})$, such that a
$(k,k+2)$-distinguisher oracle for $G$ solves the instance of Problem 1.1.

We begin by focusing on a $k+1$ layered graph
$\mathcal{L}=(V_{\mathcal{L}},E_{\mathcal{L}})$, which we call the
_infrastructure_ graph. The infrastructure graph has three important
properties:  (i) each layer contains $N$ vertices,  (ii) there is a path of
length $k$ from every vertex in the first layer to every vertex in the last
layer, and  (iii) the degree of every vertex is at most $2N^{1/k}$.

We then construct for each $x\in X$ a graph $G_{x}=(V_{x},E_{x})$, which is a
subgraph of (a copy of) $\mathcal{L}$, by removing some of the edges between
the first (last) and second (second to last) layers of $\mathcal{L}$ in a way
that expresses which sets contain $x$ and which do not. Finally, we construct
the graph $G$ which is _specialized_ union of all of the graphs $G_{x}$ for
all $x\in X$, and enables solving the instance of Problem 1.1 by using a
$(k,k+2)$-distinguisher oracle on $G$.

##### The infrastructure graph.

The infrastructure graph $\mathcal{L}$ is a $k+1$ layered graph where each
layer contains $N$ vertices, and each layer of $N$ vertices is locally indexed
from $1$ to $N$. The layers are numbered $0$ to $k$.

The edges of $\mathcal{L}$ are defined using the following labels. We assign a
_label_ $\ell(v)$ to every vertex $v$ in $\mathcal{L}$ which is the $k$ digit
representation in base777We assume for convenience that $N^{1/k}$ is an
integer, since otherwise, one can increase $N$ slightly without affecting the
asymptotic complexities. $N^{1/k}$ of the local index (an integer between $1$
and $N$) of $v$. Then, for every $1\leq t\leq k$, we connect $u$ from layer
$t-1$ with $v$ from layer $t$ if and only if the digits of $\ell(u)$ and the
digits of $\ell(v)$ all match, except for possibly the $t$’th digit. It is
straightforward to observe (since each digit has $N^{1/k}$ options) that the
degree of every vertex in $\mathcal{L}$ is $2N^{1/k}$, except for the vertices
in the first and last layers which have degree $N^{1/k}$. In the following
claim we show that there is a path of length $k$ from every vertex in the
first layer and every vertex in the last layer.

######  Claim 5.1.

Let $v$ be a vertex in the first layer of $\mathcal{L}$ and let $u$ be a
vertex in the last layer of $\mathcal{L}$. Then there exists a path of length
$k$ from $u$ to $v$ in $\mathcal{L}$.

###### Proof.

We describe the path of length $k$ between $u$ and $v$. For any $0\leq t\leq
k$, consider the vertex $w_{t}$ in layer $t$ of $\mathcal{L}$ with the label
of the following form: the first $t$ digits are the first $t$ digits of
$\ell(u)$, and the last $k-t$ digits are the last $k-t$ digits of $\ell(v)$.
Thus, for $0\leq t\leq k-1$, the edge $(w_{t},w_{t+1})$ is in $\mathcal{L}$
since $\ell(w_{t})$ and $\ell(w_{t+1})$ are the same, except for possibly the
$(t+1)$-th digit. The set of edges which we described form a path of length
$k$ between $v$ and $u$. ∎

##### Constructing $G_{x}$.

We construct $V_{x}$ by making copies of each vertex in $V_{\mathcal{L}}$.
Denote the first layer of $\mathcal{L}$ by $V_{L}=\\{v_{1},\dots,v_{N}\\}$ and
the last layer by $V_{R}=\\{u_{1},\dots,u_{N}\\}$. Let
$\hat{E}_{x}=\\{(v_{i},w)|x\notin S_{i}\wedge(v_{i},w)\in
E_{\mathcal{L}}\\}\cup\\{(u_{i},w)|x\notin S_{i}\wedge(u_{i},w)\in
E_{\mathcal{L}}\\}$. Thus, $\hat{E}_{x}$ is the set of edges in $\mathcal{L}$
that touch vertices in the first or last layers whose index corresponds to the
index of sets that do not contain $x$. We construct $E_{x}$ by making copies
of all edges in $E_{\mathcal{L}}\setminus\hat{E}_{x}$. The reason for removing
the edges in $\hat{E}_{x}$ is so that vertices in the first and last layers of
$G_{x}$ whose edges are in $\hat{E}_{x}$ are not connected to any other vertex
in $G_{x}$. Thus, for each $v_{i}$ ($u_{j}$) in the first (last) layer of
$G_{x}$, $x\in S_{i}$ if and only if there are edges between $v_{i}$ ($u_{j}$)
and the second (second to last) layer in $G_{x}$. By 5.1, if $S_{i}\cap
S_{j}\neq\emptyset$ then there exists a path of length $k$ between $v_{i}$ and
$u_{j}$, and otherwise, there is no path in $G_{x}$ between $v_{i}$ and
$u_{j}$. Finally, since $G_{x}$ is a partial copy of $\mathcal{L}$, the
maximum degree in $G_{x}$ is $2N^{1/k}$.

##### Constructing $G$.

We construct the $k+1$ layered graph $G$ by performing the following special
union of $G_{x}$ for all $x$: for $1\leq t\leq k-1$ the $t$’th layer of $G$ is
the union of the $t$’th layer of all of the $G_{x}$ graphs taken over all
$x\in X$. Thus, each of the $k-1$ inner layers (excluding the first and last
layer of $G$) has $|X|N$ vertices. For the first (last) layer $G$, instead of
taking the union of all of the first (last) layers from all of the $G_{x}$
graphs, we merge them all into one layer of $N$ vertices. So the $i$’th vertex
in the first (last) layer of $G$ is a vertex obtained by merging the $i$’th
vertex in the first (last) layer of every $G_{x}$, for all $x\in X$. Thus, the
first and last layers of $G_{x}$ contain $N$ vertices each. Since the vertices
in the first and last layer of $G$ correspond directly to the vertices $V_{L}$
and $V_{R}$ in $\mathcal{L}$, respectively, we treat the first layer of $G$ as
$V_{L}=\\{v_{1},\ldots v_{n}\\}$ and the last layer of $G$ by
$V_{R}=\\{u_{1},\ldots,u_{N}\\}$. Thus, each node in $V_{L}\cup V_{R}$ has
maximum degree at most $|X|N^{1/k}=\tilde{O}(N^{1/k}).$

##### Answering a set intersection query.

Notice that for a set intersection query between $S_{i}$ and $S_{j}$, if
$S_{i}\cap S_{j}\neq\emptyset$, then there exists some $x\in S_{i}\cap S_{j}$,
and since $G$ contains $G_{x}$ as a subgraph, the distance between $v_{i}$ and
$u_{j}$ is at most (and actually exactly) $k$. On the other hand, if there
exists a path $P$ of length $k$ between $v_{i}$ and $u_{j}$, then by the
construction of $G$, $P$ must be completely contained within some $G_{x}$ for
some $x\in X$. By the construction of $G_{x}$, and specifically $E_{x}$, the
existence of $P$ in $G_{x}$ implies that $x\in S_{i}$ and $x\in S_{j}$. So, in
such a case $S_{i}\cap S_{j}\neq\emptyset$.

Notice that, since $G$ is a $k+1$ layered graph, any path between a vertex in
the first layer and a vertex in the last layer must be of length $k+2q$ for
some integer $q\geq 0$. Thus, to answer a set intersection query, it suffices
to establish whether the distance in $G$ between $v_{i}$ and $u_{j}$ is either
$k$ or at least $k+2$, which the $(k,k+2)$-distinguisher oracle returns in
constant time.

##### Analysis.

We conclude that a $(k,k+2)$-distinguisher oracle for graphs with
$n=\tilde{O}(N)$ vertices and maximum degree $\tilde{O}(n^{1/k})$ also solves
the instance of Problem 1.1 (of size $N$). Thus, according to Hypothesis 1.2,
an ADO for graphs with $n=\tilde{O}(N)$ vertices, for which the maximum degree
is $\tilde{O}(n^{1/k})$, must use $\tilde{O}(N^{2})=\tilde{O}(n^{2})$ space.
We note that the maximum degree can be reduced to $O(n^{1/k})$ by artificially
adding $\tilde{O}(n)=\tilde{O}(N)$ isolated vertices to $G$. ∎

##  6 Conclusions and Open Problems

In this paper we provide an algorithm (Theorem 1.4) and a conditional lower
bound (Theorem 1.5) for subquadratic space ADOs as a function of the maximum
degree. As mentioned in Section 1, the case of $k=2$ in Theorem 1.5
essentially matches the upper bound of Theorem 1.4. Although our upper bound
from Theorem 1.4 improves the additive approximation of the ADO for larger
values of $k$, a natural remaining open problem is whether it is also possible
to reduce the multiplicative approximation of the ADO and design a
sub-$\frac{k+2}{k}$ stretch ADO for graphs with maximum degree
$\Theta(n^{\frac{1}{k}-\Omega(1)})$ while using subquadratic space for
integers $k\geq 3$.

## References

  * [1] Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir.  Hardness of approximation in p via short cycle removal: Cycle detection, distance oracles, and beyond.  In 54th Annual ACM Symposium on Theory of Computing, pages 1487–1500. ACM, 2022.
  * [2] Ittai Abraham and Cyril Gavoille.  On approximate distance labels and routing schemes with affine stretch.  In International Symposium on Distributed Computing, pages 404–415. Springer, 2011.
  * [3] Rachit Agarwal.  The space-stretch-time tradeoff in distance oracles.  In European Symposium on Algorithms, pages 49–60. Springer, 2014\.
  * [4] Rachit Agarwal and P Brighten Godfrey.  Distance oracles for stretch less than 2.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 526–538. SIAM, 2013.
  * [5] Rachit Agarwal, P Brighten Godfrey, and Sariel Har-Peled.  Approximate distance queries and compact routing in sparse graphs.  In 2011 Proceedings IEEE INFOCOM, pages 1754–1762. IEEE, 2011.
  * [6] Rachit Agarwal and Philip Brighten Godfrey.  Brief announcement: a simple stretch 2 distance oracle.  In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 110–112, 2013.
  * [7] Maor Akav and Liam Roditty.  An almost 2-approximation for all-pairs of shortest paths in subquadratic time.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1–11. SIAM, 2020.
  * [8] Surender Baswana, Vishrut Goyal, and Sandeep Sen.  All-pairs nearly 2-approximate shortest paths in _I_ time.  Theor. Comput. Sci., 410(1):84–93, 2009.
  * [9] Surender Baswana and Telikepalli Kavitha.  Faster algorithms for approximate distance oracles and all-pairs small stretch paths.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 591–602. IEEE, 2006.
  * [10] Richard Bellman.  On a routing problem.  Quarterly of applied mathematics, 16(1):87–90, 1958.
  * [11] Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck.  Improved approximate distance oracles: Bypassing the thorup-zwick bound in dense graphs.  arXiv preprint arXiv:2307.11677, 2023.
  * [12] Timothy M Chan.  More algorithms for all-pairs shortest paths in weighted graphs.  SIAM Journal on Computing, 39(5):2075–2089, 2010.
  * [13] Shiri Chechik.  Approximate distance oracles with constant query time.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 654–663, 2014.
  * [14] Shiri Chechik.  Approximate distance oracles with improved bounds.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1–10, 2015.
  * [15] Shiri Chechik and Tianyi Zhang.  Nearly 2-approximate distance oracles in subquadratic time.  In SODA, pages 551–580. SIAM, 2022.
  * [16] Boris V Cherkassky, Andrew V Goldberg, and Tomasz Radzik.  Shortest paths algorithms: Theory and experimental evaluation.  Mathematical programming, 73(2):129–174, 1996.
  * [17] Hagai Cohen and Ely Porat.  On the hardness of distance oracle for sparse graph.  arXiv preprint arXiv:1006.1117, 2010.
  * [18] Edsger W Dijkstra et al.  A note on two problems in connexion with graphs.  Numerische mathematik, 1(1):269–271, 1959.
  * [19] Dorit Dor, Shay Halperin, and Uri Zwick.  All-pairs almost shortest paths.  SIAM Journal on Computing, 29(5):1740–1759, 2000.
  * [20] Michael L Fredman and Robert Endre Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  Journal of the ACM (JACM), 34(3):596–615, 1987.
  * [21] Amgad Madkour, Walid G Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, and Saleh Basalamah.  A survey of shortest-path algorithms.  arXiv preprint arXiv:1705.02044, 2017.
  * [22] Manor Mendel and Assaf Naor.  Ramsey partitions and proximity data structures.  In FOCS, pages 109–118, 2006.
  * [23] Mihai Patrascu and Liam Roditty.  Distance oracles beyond the thorup-zwick bound.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 815–823. IEEE, 2010.
  * [24] Mihai Patrascu, Liam Roditty, and Mikkel Thorup.  A new infinity of distance oracles for sparse graphs.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 738–747. IEEE, 2012.
  * [25] Ely Porat and Liam Roditty.  Preprocess, set, query!  Algorithmica, 67(4):516–528, 2013.
  * [26] Liam Roditty, Mikkel Thorup, and Uri Zwick.  Deterministic constructions of approximate distance oracles and spanners.  In International Colloquium on Automata, Languages, and Programming, pages 261–272. Springer, 2005.
  * [27] Liam Roditty and Roei Tov.  Approximate distance oracles with improved stretch for sparse graphs.  Theoretical Computer Science, 943:89–101, 2023.
  * [28] Christian Sommer.  All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing.  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:13, 2016.
  * [29] Mikkel Thorup and Uri Zwick.  Compact routing schemes.  In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1–10, 2001.
  * [30] Mikkel Thorup and Uri Zwick.  Approximate distance oracles.  Journal of the ACM (JACM), 52(1):1–24, 2005.
  * [31] Virginia Vassilevska Williams and Yinzhan Xu.  Monochromatic triangles, triangle listing and apsp.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 786–797. IEEE, 2020.
  * [32] Christian Wulff-Nilsen.  Approximate distance oracles with improved query time.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 539–549, 2013.
  * [33] Uri Zwick.  Exact and approximate distances in graphs—a survey.  In European Symposium on Algorithms, pages 33–48. Springer, 2001\.


Laboratory and astronomical discovery of magnesium dicarbide, MgC_2

P. B. Changala
Center for Astrophysics $|$ Harvard & Smithsonian, Cambridge, MA 02138, USA

H. Gupta
Center for Astrophysics $|$ Harvard & Smithsonian, Cambridge, MA 02138, USA
National Science Foundation, Alexandria, VA 22314, USA

J. Cernicharo
Instituto de Física Fundamental, CSIC, Department of Molecular Astrophysics, Serrano 121, 28006 Madrid, Spain

J. R. Pardo
Instituto de Física Fundamental, CSIC, Department of Molecular Astrophysics, Serrano 121, 28006 Madrid, Spain

M. Agúndez
Instituto de Física Fundamental, CSIC, Department of Molecular Astrophysics, Serrano 121, 28006 Madrid, Spain

C. Cabezas
Instituto de Física Fundamental, CSIC, Department of Molecular Astrophysics, Serrano 121, 28006 Madrid, Spain

B. Tercero
Observatorio Astronómico Nacional, IGN, C/Alfonso XII 3, 28014 Madrid, Spain

M. Guélin
Institut de Radioastronomie Millimétrique, 300 rue de la Piscine, 38406 Saint Martin d'Hères, France

M. C. McCarthy
Center for Astrophysics $|$ Harvard & Smithsonian, Cambridge, MA 02138, USA

We report the detection of magnesium dicarbide, MgC$_2$, in the laboratory at centimeter wavelengths and assign $^{24}$MgC$_2$, $^{25}$MgC$_2$, and $^{26}$MgC$_2$ to 14 unidentified lines in the radio spectrum of the circumstellar envelope of the evolved carbon star IRC+10216. The structure of MgC$_2$ is found to be T-shaped with a highly ionic bond between the metal atom and the C$_2$ unit, analogous to other dicarbides containing electropositive elements.
A two-temperature excitation model of the MgC$_2$ emission lines observed in IRC+10216 yields a very low rotational temperature of $6\pm1$ K, a kinetic temperature of $22\pm13$ K, and a column density of $(1.0 \pm 0.3) \times 10^{12}$ cm$^{-2}$.
The abundance of MgC$_2$ relative to the magnesium-carbon chains MgCCH, MgC$_4$H, and MgC$_6$H is $1{:}2{:}22{:}20$ and provides a new constraint on the sequential radiative association-dissociative recombination mechanisms implicated in the production of metal-bearing molecules in circumstellar environments.

§ INTRODUCTION

Silicon dicarbide (SiC$_2$) was long known to exist in carbon-rich stellar atmospheres <cit.>, but its identification as the carrier of nine unassigned lines in the radio spectrum of the archetype carbon star IRC+10216 was a key advance in  understanding the molecular constituents of evolved carbon stars [Thaddeus et al., 1984].  Its substantial abundance and the highly ionic nature of the Si–C$_2$ bond suggested that molecules containing other electropositive elements bonded to C$_2$ or longer carbon chains might be present in IRC+10216 and responsible for other unidentified lines there.  In the nearly 40 years since the radio astronomical identification of SiC$_2$, a number of metal-bearing molecules have been discovered in IRC+10216, most containing strong ionic bonds between metal atoms and carbon chains [Cernicharo et al., 2019, Pardo et al., 2021].  It is surprising, therefore, that metal dicarbides  — the simplest molecules containing one metal atom and two carbon atoms — are absent from this inventory.  Although several metal dicarbides have now been studied in the laboratory, accurate data are available only for one (AlC$_2$) <cit.> that is a plausible candidate for radio astronomical detection.

Magnesium dicarbide (MgC$_2$) is an excellent candidate for detection in IRC+10216 because of the high cosmic abundance of magnesium, which is found in nearly half of all known metal-bearing species in this source.
An early theoretical study of MgC$_2$ [Green, 1984] predicted a triangular, symmetric, and highly polar ground-state structure similar to SiC$_2$.  Motivated by the discoveries of MgNC and MgCN several years later [Kawaguchi et al., 1993, Ziurys et al., 1995], more accurate calculations of MgC$_2$ appeared in the literature [Itono et al., 2000], but no gas-phase measurements followed.  The purpose of this Letter is to report the laboratory detection of MgC$_2$ at centimeter wavelengths, and its assignment to a series of previously unidentified lines in the radio spectrum of IRC+10216.  To our knowledge, this is the first spectroscopic characterization of MgC$_2$ in any wavelength region, while its astronomical discovery  fills a longstanding gap in the molecular inventory of evolved carbon stars.

§ LABORATORY MEASUREMENTS

Rotational lines of MgC$_2$ were detected with a Fourier transform microwave (FTMW) spectrometer coupled to a laser ablation supersonic expansion source previously used in our laboratory to characterize small metal-containing molecules [Brünken et al., 2008, Zingsheim et al., 2017, Lee et al., 2019]. A rotating magnesium rod was ablated by 50-mJ pulses of 532-nm radiation from an Nd:YAG laser operating at 5 Hz. The ablated Mg atoms were entrained in a dilute mixture (0.1%) of acetylene in neon, which then passed through two copper discharge electrodes. An 800-V discharge struck between the electrodes increased the product yield by up to a factor of 5 [Sun et al., 2010]. After expanding into a large vacuum chamber, the molecules were polarized in a co-axially aligned cavity spectrometer operating from 5 to 26 GHz [Grabow et al., 2005, Crabtree et al., 2016]. Double-resonance transitions at higher frequencies were driven by microwave horns placed perpendicular to the cavity axis.

The identification of MgC$_2$ was challenging because only one transition, the $1_{01}-0_{00}$ line predicted to lie near 20.9 GHz [Itono et al., 2000], falls within our spectrometer bandwidth.
After optimizing the production of MgCCH, we conducted a search from 20.4 to 21.0 GHz. This survey was extremely sparse, with only a single ablation-dependent feature at 20896 MHz, shown in Fig. <ref>, close to the prediction of 20892 MHz from quantum chemical calculations performed for this work (see Appendix <ref>).
We conducted a number of assays to test the carrier of this line: the signal was unaffected by applied magnetic fields, consistent with the predicted closed-shell ground electronic state; it required the presence of acetylene, but was unaffected by replacing HCCH with DCCD, indicating it contains carbon but not hydrogen; and the relative intensity from a statistical $^{12}$C/$^{13}$C HCCH precursor suggested it likely contained only two C atoms.
Spectroscopic confirmation was provided by the observation of a double resonance transition ($2_{02}-1_{01}$, top panel of Fig <ref>) at its expected frequency near 41.7 GHz.
Assuming a dipole moment of 7.9 D [Itono et al., 2000], we estimate the number of MgC$_2$ molecules in each gas pulse to be $4 \times 10^8$, significantly less abundant than MgCCH ($5 \times 10^{10}$) or the precursor Mg atoms ($5 \times 10^{14}$, estimated from the ablation target mass loss) and HCCH ($2\times 10^{15}$, from calibrated flow meters).

With the assignment of MgC$_2$ secure, we proceeded to search for its isotopologues. The fundamental transitions of $^{26}$Mg$^{12}$C$_2$ and $^{25}$Mg$^{12}$C$_2$ were detected in natural abundance,
while those of $^{24}$Mg$^{13}$C$^{12}$C and $^{24}$Mg$^{13}$C$_2$ were detected using a $^{13}$C-enriched sample of acetylene. Their transition frequencies are shown in Table <ref> and are uniformly within 0.5 MHz of the theoretical isotopic shifts. These laboratory measurements are insufficient to determine the $A$, $B$, and $C$ rotational constants for each isotopologue independently, but together provide enough information to derive a semi-experimental equilibrium structure, shown in Fig. <ref> (see Appendix <ref> for details). The $1_{01}-0_{00}$ transition of $^{25}$Mg$^{12}$C$_2$ is split into three hyperfine components by nuclear electric quadrupole interactions. The observed coupling constants are $\chi_{aa} = -11.75(2)$ MHz and $\chi_{bb} = 4.8(10)$ MHz, which agree well with the theoretical predictions of $-11.4$ MHz and $4.8$ MHz, respectively.

§ ASTRONOMICAL IDENTIFICATION

With accurate laboratory data in hand, we examined available spectroscopic surveys and observations of IRC+10216 for evidence of MgC$_2$.  An unidentified rotational line, U41712, coincident with the $2_{02}-1_{01}$ transition of $^{24}$MgC$_2$ was found in the recent 6–10 millimeter survey done by Pardo et al., 2022 using the Yebes 40 m telescope.  A second unidentified line, U82788, was found in a study reporting the identification of the HC$_4$N radical [Cernicharo et al., 2004] using the IRAM 30 m telescope.  Subsequently, 8 additional unidentified lines were quickly found in unpublished surveys at 2 and 3 millimeters done with the IRAM 30 m telescope (see Cernicharo et al., 2019 for details) and assigned to $^{24}$MgC$_2$.  One line of $^{25}$MgC$_2$ and three lines of $^{26}$MgC$_2$ were also found at precisely the expected isotopic shifts.

There is overwhelming evidence that MgC$_2$ is the carrier of the lines listed in Table <ref> and displayed in Figures <ref> and <ref>. As Table <ref> shows, a combined fit of the observed laboratory and astronomical lines of $^{24}$MgC$_2$ to Watson's $A$-reduced Hamiltonian yields small residuals corresponding to a normalized rms of 1.37 (Table <ref>), demonstrating that they originate from the same molecule. Table <ref> lists the spectroscopic constants derived using only six free parameters (three rotational constants and three centrifugal distortion constants) and two parameters fixed to theoretical values.
Similarly small residuals are obtained for $^{25}$MgC$_2$ and $^{26}$MgC$_2$, albeit with fewer determinable parameters given the small data sets.
The ratio of the integrated intensities of the $2_{02}-1_{01}$ lines of the three isotopologues is $(73\pm5)\rm{:}(11\pm2)\rm{:}(15\pm3)$, consistent with the solar abundance ratio of $^{24}$Mg:$^{25}$Mg:$^{26}$Mg of $(79.2\pm0.6)\rm{:}(9.5\pm0.5)\rm{:}(11.3\pm0.5)$ [Bochsler et al., 1996] and the abundance ratio derived for MgNC in IRC+10216 itself, $(78\pm2)\rm{:}(11\pm1)\rm{:}(11\pm1)$ [Guélin et al., 1995].

Figures <ref> and <ref> present the astronomical spectra and show that the assigned lines meet all requirements of the identification.
Each line exhibits the same double-peaked or “U-shaped” profile and has the same width as the strong $4_{04}-3_{03}$ line ($29.0\pm 0.5$ ) to within observational uncertainties. Six fully resolved or nearly fully resolved lines and four partially blended lines of $^{24}$MgC$_2$ are detected. Three lines of $^{26}$MgC$_2$ are detected, including one which is partially blended. Finally, one line of $^{25}$MgC$_2$ is detected with a slightly broadened line width consistent with the underlying quadrupole hyperfine structure predicted from the laboratory measurements.  The high quality profiles derived from the resolved lines and the precise rest frequencies of the blended lines allow us to account for the contributions of the interlopers and extract reliable parameters.

We have analyzed the intensities of the rotational lines to infer the excitation of the molecules on two assumptions: (1) to correct for the changing antenna beamwidth in Table <ref>, it is assumed by analogy with other Mg-bearing molecules in IRC+10216, that the MgC$_2$ emission is confined to a shell of $30\arcsec$ in diameter [Cernicharo et al., 2019, Pardo et al., 2021], an assumption supported by the U-shaped profiles of the lines and (2) all of the lines in Table <ref> are optically thin because of their faintness.

§ DISCUSSION

As Figure <ref> shows, rotational emission lines spanning a wide range in energy are detected in IRC+10216, allowing us to construct the rotational temperature diagram shown in Fig. <ref>.
The integrated intensities of the lines are reproduced by a simple two-temperature excitation model (see Appendix <ref>)
in which a temperature $T_\mathrm{rot}=6\pm1$ K describes the relative populations within each $K$ ladder
and $T_\mathrm{kin}=22\pm13$ K describes the relative populations across $K$ ladders and provides a measure of the gas kinetic temperature.
A comparison of the derived excitation temperatures of MgC$_2$, SiC$_2$, and SiC$_3$ shows that $T_\mathrm{rot}$ is similar for the three species ($6\pm1$ K vs. 10 K and 13 K [Thaddeus et al., 1984, Apponi et al., 1999]), but $T_\mathrm{kin}$ is not.  The latter is similar for MgC$_2$ and SiC$_3$ ($22\pm13$ K and 46 K [Apponi et al., 1999]), and it is significantly smaller than for SiC$_2$ (140 K [Thaddeus et al., 1984]), probably because MgC$_2$ and SiC$_3$ reside in the cool outer envelope of IRC+10216, whereas SiC$_2$ is more widely distributed, residing in the warmer inner regions as well as the outer envelope [Patel et al., 2011]. The $T_\mathrm{kin}$ of 22 K inferred for MgC$_2$ is remarkably close to the value of 20 K inferred from observations and modeling of dust, CO, and CCH in the $30\arcsec\rm{-}40\arcsec$ diameter shell of IRC+10216 [Guélin et al., 2018].  As discussed in Appendix <ref>, the column density averaged over a $30\arcsec$ antenna beam is  $N(\mathrm{MgC_{2}})=1\times10^{12}$ cm$^{-2}$, with an estimated uncertainty of $30\%$, corresponding to a fractional abundance of ${\sim}5\times10^{-10}$ relative to H$_2$.[We adopt $N(\mathrm{H_{2}})=2.1\times10^{21}$ cm$^{-2}$ following Gong et al., 2015.]

On the assumption that MgC$_2$ is co-spatial with the magnesium-carbon chain radicals MgCCH, MgC$_4$H and MgC$_6$H (which is supported by the similar line profiles), a comparison of their abundances might shed light on the production of Mg-bearing species in the outer envelope of IRC+10216. The formation of MgCCH, MgC$_4$H and MgC$_6$H has been explained by a two-step process in which radiative association (RA) of Mg$^+$ with large polyynes HC$_{2n}$H ($n\geq4$) yields the intermediate ions MgHC$_{2n}$H$^{+}$, which then undergo dissociative recombination (DR) to yield the neutral radicals [Cernicharo et al., 2019, Pardo et al., 2021].
This mechanism, originally proposed by Petrie, 1996 and later expanded by Dunbar & Petrie, 2002, is thought to control the formation of the metal cyanides and acetylides detected in IRC+10216 [Millar, 2008, Cabezas et al., 2013, Cernicharo et al., 2019, Pardo et al., 2021]. The chemical models developed in these studies indicate that the main precursors of magnesium carbon chains are large MgHC$_{2n}$H$^+$ complexes with more than six carbon atoms.
If, as is plausible,  MgC$_2$ is also a fragmentation product in the DR of MgHC$_{2n}$H$^{+}$, then the observed column density ratio MgC$_2$:MgCCH:MgC$_4$H:MgC$_6$H $=1{:}2{:}22{:}20$ provides a useful constraint on the relative yields of the DR of the parent ions. Observations of other plausible DR products, such as MgC and larger MgC$_n$ clusters are needed to better elucidate the poorly constrained gas-phase chemistry. A parallel formation mechanism that may also be important is the RA-DR of Mg$^+$ and large cyanopolyynes, HC$_{2n+1}$N [Dunbar & Petrie, 2002]. Experimental measurements of the branching ratios of the various fragments formed in the DR of large MgHC$_{2n}$H$^+$ and MgHC$_{2n+1}$NH$^+$ ions would enable a direct comparison against the observed abundance ratios, permitting a holistic assessment of the production of metal-bearing molecules in the outer layers of IRC+10216.

Understanding the structure and bonding in metal dicarbides is of fundamental chemical interest and may identify additional metal carbides that are candidates for astronomical detection.
Like other T-shaped triatomic dicarbides, including SiC$_2$ [Cernicharo et al., 1991], GeC$_2$ [Zingsheim et al., 2017], BeC$_2$ [Green et al., 2020], AlC$_2$ [Halfen & Ziurys, 2018], ScC$_2$ [Min et al., 2014], and YC$_2$ [Halfen et al., 2013], MgC$_2$ exhibits an ionic metal-carbon bond best described as Mg$^+$–C$_2^-$.
Its equilibrium CC bond length, $r_\mathrm{CC} = 1.2706(7)$ Å, is close to that of bare C$_2^-$ itself, $r_\mathrm{CC} = 1.26831(13)$ Å [Rehfuss et al., 1988], which are both significantly longer than neutral C$_2$, $r_\mathrm{CC} = 1.24244(1)$ Å [Douay et al., 1988]. Moreover, the ionicity, defined as the ratio of the molecular dipole moment to the dipole moment resulting from unit point charges separated by the metal-C$_2$ bond length, $i = \mu/er_\mathrm{Mg-C_2} = 0.86$, suggests nearly complete transfer of a $3s$ electron from Mg to the C$_2$ fragment.

The bonding in MgC$_2$ closely resembles that in MgO [Boldyrev & Simons, 1997], with the in-plane $\pi_u$ orbital of C$_2$ taking the place of the $2p_z$ orbital of O. MgO has a similar ionicity, $i = 0.72$, and Mg nuclear quadrupole coupling constant: $-10(4)$ MHz [Törring & Hoeft, 1986] versus $\chi_{aa} = -11.72(2)$ MHz for MgC$_2$. These latter parameters indicate that the Mg $3s$ orbital in both molecules is substantially hybridized. Given that the atomic $3p_z$ orbital of Mg$^{+}$ has a quadrupole coupling constant of $-46$ MHz [Sur et al., 2005], the $p$ character is about 25%. Although simple orbital descriptions of MgC$_2$ and MgO are potentially obscured by their multiconfigurational, mixed ionic-covalent character [Thümmel et al., 1989, Itono et al., 2000], this issue appears to be less severe for MgC$_2$, which is adequately described with single-reference coupled cluster methods as borne out by the calculations in this work and others [Woon, 1996].
The bonding of the heavier Group IIA dicarbides CaC$_2$ and SrC$_2$ can be expected to follow the same trends observed in their respective oxides. Because of their high ionicities, all of these species possess unusually large dipole moments [Fuentealba & Savin, 2000].

Observations of MgC$_2$ and similar metal dicarbides are a promising means to elucidate the role of metals in the chemistry of IRC+10216, as well as the state of refractory elements in carbon-rich circumstellar environments more generally.  Metals are inferred to be significantly depleted onto dust grains in IRC+10216 [Mauron & Huggins, 2010], yet even the residual gas-phase abundance of metal atoms and ions is sufficient to drive a rich chemistry. For example, molecules containing the cyano radical (CN) bonded to the most abundant metallic elements (Na, K, Mg, Ca, Al, and Fe) have been found there. Given that the abundances of MgC$_2$ and MgNC [Guélin et al., 1995] are within an order of magnitude of each other, it is very likely that other metal dicarbides are also synthesized in the external layers of the circumstellar envelope of IRC+10216, plausibly following the same chemical pathway that is postulated to yield MgC$_2$. By analogy with SiC$_2$, which has yielded invaluable information on gas-phase processes within the inner and intermediate winds, as well as the outer circumstellar envelopes of evolved carbon-rich stars <cit.>, metal dicarbides may also serve as important probes provided their excitation, abundance, and distribution are understood.  The distribution of metal dicarbides as a function of radial distance from the central star in IRC+10216, for example, accompanied by a careful analysis of their abundance and excitation might shed light on processes such as condensation and dust formation, which remain poorly understood.

The identification of MgC$_2$ in the laboratory and in space marks a key step in the study of metal carbides and suggests that other highly polar metal-carbon molecules might be detectable.  After MgC$_2$, CaC$_2$ is the next most promising candidate for detection because it possesses an even larger dipole moment (10.7 D; Fuentealba & Savin, 2000) than MgC$_2$  (7.9 D; Itono et al., 2000) and because Ca is cosmically the next most abundant Group IIA element after Mg; calcium isocyanide (CaNC) has already been detected in IRC+10216 [Cernicharo et al., 2019], suggesting that other Ca-bearing molecules may be present there. By analogy with SiC [Massalkhi et al., 2018], the monocarbides MgC and CaC may be important for comparative studies of the distribution, abundance, and photochemical processing of dicarbides in circumstellar envelopes; although CaC has been detected in the laboratory, MgC has not, and its astronomical detection might be more feasible given the higher abundance of Mg.  Other promising systems for study include larger metal-carbon clusters such as MgC$_{n}$ about which little is known experimentally, but which, like the silicon-carbon clusters SiC$_3$ and SiC$_4$ [Apponi et al., 1999, Gordon et al., 2000], are amenable to laboratory characterization and astronomical detection.

§ STRUCTURE CALCULATIONS AND SEMI-EXPERIMENTAL EQUILIBRIUM GEOMETRY

Coupled cluster calculations were performed using the CFOUR package [Matthews et al., 2020] at the singles, doubles, and perturbative triples (CCSD(T)) level of theory [Raghavachari et al., 1989] with the cc-pCV$X$Z ($X$ = D,T,Q,5) basis sets [Woon & Dunning, 1995, Prascher et al., 2011] correlating all but the Mg $1s$ electrons. The complete basis set equilibrium geometry was estimated by an exponential extrapolation of the entire $X$ = D–5 sequence. To derive a semi-experimental equilibrium geometry, vibrational corrections to the rotational frequencies were determined by variational rovibrational calculations on a  potential energy surface (PES) fitted to 448 CCSD(T)/cc-pCVQZ single-point energies using the NITROGEN package [Changala, 2021]. Additional contributions to the rotational constants from the rotational $g$-tensor [Gauss & Puzzarini, 2010] were computed with the cc-pCVTZ basis set, and nuclear electric quadrupole coupling constants with the cc-pCV5Z basis set.

The small number of laboratory transitions observed for each isotopologue is insufficient to determine a complete set of experimental rotational constants. Instead, the structure determination was performed by least-squares fitting directly to the transition frequencies. That is, a proposed equilibrium geometry was used to compute equilibrium rotational constants, which were then corrected by the rotational $g$-tensor. These in turn were used to generate rigid-rotor transition frequencies, to which the vibrational corrections from the rovibrational variational calculations were added. These latter corrections are defined as the difference between the variational transition energies and the rigid-rotor transition energies based on the equilibrium geometry of the same PES. They therefore include both vibrational zero-point and centrifugal distortion effects. For $^{25}$MgC$_2$, the degeneracy-weighted mean of the quadrupole-split energies was used as the hyperfine-free value. The optimized structural parameters are shown in Fig. <ref> and compared to the extrapolated CCSD(T) geometry in Table <ref>. These parameters reproduce the 6 laboratory frequencies with a root-mean-square residual of 0.1 MHz. This is significantly larger than the experimental uncertainty (2 kHz) indicating that the theoretical corrections are the dominant source of error.

§ TWO-TEMPERATURE MODEL FOR ROTATIONAL EXCITATION

In the analysis of rotational emission of prolate asymmetric tops such as MgC$_2$ the partitioning of energy levels within and across radiatively decoupled rotational manifolds must be taken into account.  Because radiative transitions are confined within the $K$ ladders but collisional transitions occur within and across the ladders, the rotational excitation temperature within the ladders ($T_\mathrm{rot}$) is not necessarily equal to the excitation temperature across the ladders, which is assumed equal to the kinetic temperature ($T_\mathrm{kin}$) of the gas.  For highly polar species, excitation within the ladders is highly subthermal (i.e., $T_\mathrm{rot} \ll T_\mathrm{kin}$) because collisional excitation is much slower than spontaneous radiative decay.  Let $T_\mathrm{kin}$ describe the population distribution across $K$ ladders and $T_\mathrm{rot}$ describe the population distribution within each $K$ ladder.  Then, the intensity of an optically thin rotational line is given by

\begin{equation}\label{eq:B1}
\frac{3kW}{8\pi^{3}\nu S \mu^{2}}= \frac{Ne^{-E_{J}/kT_\mathrm{rot}}e^{{-E_{K}/kT_\mathrm{kin}}}}{Z}
\end{equation}

where $W=\int{T_\mathrm{MB}\,dv}$ is the main beam temperature integrated over the radial velocity, $\nu$ is the line frequency, $S$ is the rotational line strength, $\mu$ is the dipole moment, and $N$ is the total column density. The Boltzmann factors and partition function, $Z$, in Eq. <ref> are calculated by splitting the total rotational energy into two parts, $E_u = E_{K} + E_{J}$, where $E_{K}=(A-{(B+C)}/{2})K^{2}$ is the $K$-dependent part, and $E_J$ is the remainder. Taking the logarithm of Eq. <ref> yields

\begin{equation}\label{eq:B2}
\log \frac{3kW}{8\pi^{3}\nu S \mu^{2}}= \log \frac{N}{Z} - \frac{(E_{u}-E_{K}) \log e}{kT_\mathrm{rot}} - \frac{E_{K} \log e}{kT_\mathrm{kin}}.
\end{equation}

A least squares fit of  equation <ref> to the integrated intensities ($W$) from Table <ref> yields $T_\mathrm{rot}=5.71\pm1.12$ K and $T_\mathrm{kin}=22.14\pm13.08$ K, which are shown rounded off in the rotational temperature diagram of Fig. <ref>.  Multiplying the intercept $\log(N/Z)=10.60$ by the partition function $Z(T_\mathrm{rot},T_\mathrm{kin})=24.59$ evaluated numerically as a sum over states, yields $N(\mathrm{MgC_2})=1\times10^{12}$ cm$^{-2}$. We estimate the total uncertainty in $N$ from the dipole moment ($7.9\pm1.0$ D) and excitation conditions to be 30%.

§ ACKNOWLEDGMENTS

We thank Dr. Marie-Aline Martin-Drumel (CNRS) for her valuable assistance with the initial laboratory efforts and comments on the manuscript. P.B.C. and M.C.M. are supported by the National Science Foundation (award nos.  AST-1908576 and PHY-2110489). H.G. acknowledges support from the National Science Foundation for participation in this work as part of his independent research and development plan.  Any opinions, findings, and conclusions expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.  We acknowledge funding support from the Spanish Ministerio de Ciencia e Innovación through grants PID2019-107115GB-C21 and PID2019-106110GB-100.

[Apponi et al., 1999]
Apponi, A. J., McCarthy, M. C., Gottlieb, C., & Thaddeus, P. 1999, ApJ, 516,

[Bochsler et al., 1996]
Bochsler, P., Gonin, M., Sheldon, R. B., et al. 1996, AIP Conference
Proceedings, 382, 199

[Boldyrev & Simons, 1997]
Boldyrev, A. I., & Simons, J. 1997, J. Phys. Chem. A, 101, 2215.

[Brünken et al., 2008]
Brünken, S., Müller, H. S. P., Menten, K. M., McCarthy, M. C., &
Thaddeus, P. 2008, ApJ, 676, 1367.

[Cabezas et al., 2013]
Cabezas, C., Cernicharo, J., Alonso, J. L., et al. 2013, 775, 133

[Cernicharo et al., 2019]
Cernicharo, J., Cabezas, C., Pardo, J., Agúndez, M., & Bermúdez, C.
e. a. 2019, Astron. Astrophys., 630, L2

[Cernicharo et al., 2004]
Cernicharo, J., Guélin, M., & Pardo, J. R. 2004, Astron. Astrophys., 615,

[Cernicharo et al., 1991]
Cernicharo, J., Guélin, M., Kahane, C., et al. 1991, Astron. Astrophys.,
246, 213

[Changala, 2021]
Changala, P. B. 2021, NITROGEN, version 2.1,

[Crabtree et al., 2016]
Crabtree, K. N., Martin-Drumel, M.-A., Brown, G. G., et al. 2016, J. Chem.
Phys., 144, 124201.

[Douay et al., 1988]
Douay, M., Nietmann, R., & Bernath, P. F. 1988, J. Mol. Spectrosc., 131, 250

[Dunbar & Petrie, 2002]
Dunbar, R. C., & Petrie, S. 2002, Astrophys. J., 564, 792

[Fuentealba & Savin, 2000]
Fuentealba, P., & Savin, A. 2000, J. Phys. Chem. A, 104, 10882

[Gauss & Puzzarini, 2010]
Gauss, J., & Puzzarini, C. 2010, Mol. Phys., 108, 269

[Gong et al., 2015]
Gong, Y., Henkel, C., & Spezzano, S. e. a. 2015, Astron. Astrophys., 574, A56

[Gordon et al., 2000]
Gordon, V. D., Nathan, E. S., Apponi, A. J., et al. 2000, J. Chem. Phys.,
113, 5311

[Grabow et al., 2005]
Grabow, J. U., Palmer, E. S., McCarthy, M. C., & Thaddeus, P. 2005, Rev. Sci.
Instrum., 76, 093106

[Green et al., 2020]
Green, M. L., Jaffe, N. B., & Heaven, M. C. 2020, J. Phys. Chem. Lett., 11, 88

[Green, 1984]
Green, S. 1984, Chem. Phys. Lett., 112, 29

[Guélin et al., 1995]
Guélin, M., Forestini, M., Valiron, P., et al. 1995, Astron.
Astrophys., 297, 183

[Guélin et al., 2018]
Guélin, M., Patel, N. A., Bremer, M., et al. 2018, A&A, 610, A4

[Halfen et al., 2013]
Halfen, D. T., Min, J., & Ziurys, L. M. 2013, Chem. Phys. Lett., 555, 31

[Halfen & Ziurys, 2018]
Halfen, D. T., & Ziurys, L. M. 2018, Phys. Chem. Chem. Phys., 20, 11047

[Itono et al., 2000]
Itono, S., Takano, K., Hirano, T., & Nagashima, U. 2000, ApJL, 538, L163.

[Kawaguchi et al., 1993]
Kawaguchi, K., Kagi, E., Hirano, T., Takano, S., & S., S. 1993, ApJ, 406, L39

[Kleman, 1956]
Kleman, B. 1956, ApJ, 123, 162

[Lee et al., 2019]
Lee, K. L. K., Thorwirth, S., Martin-Drumel, M. A., & McCarthy, M. C. 2019,
Phys. Chem. Chem. Phys., 21, 18911.

[Massalkhi et al., 2018]
Massalkhi, S., Agúndez, M., & Cernicharo, J. e. a. 2018, Astron.
Astrophys., 630, A29

[Matthews et al., 2020]
Matthews, D. A., Cheng, L., Harding, M. E., et al. 2020, J. Chem. Phys., 152,

[Mauron & Huggins, 2010]
Mauron, N., & Huggins, P. J. 2010, Astron. Astrophys., 513, A31.

[Millar, 2008]
Millar, T. J. 2008, Astrophys. Space Sci., 313, 223.

[Min et al., 2014]
Min, J., Halfen, D. T., & Ziurys, L. M. 2014, Chem. Phys. Lett., 609, 70.

[Pardo et al., 2021]
Pardo, J. R., Cabezas, C., Fonfría, J. P., et al. 2021, Astron.
Astrophys., 652, L13

[Pardo et al., 2022]
Pardo, J. R., Cernicharo, J., Tercero, B., et al. 2022, Astron. Astrophys.,
658, A39

[Patel et al., 2011]
Patel, N. A., Young, K. H., Gottlieb, C. A., et al. 2011, Astrophys. J.
Suppl. Ser., 193, 17.

[Petrie, 1996]
Petrie, S. 1996, Mon. Not. R. Astron. Soc., 282, 807.

[Prascher et al., 2011]
Prascher, B. P., Woon, D. E., Peterson, K. A., Dunning, T. H., & Wilson, A. K.
2011, Theor. Chem. Acc., 128, 69.

[Raghavachari et al., 1989]
Raghavachari, K., Trucks, G. W., Pople, J. A., & Head-Gordon, M. 1989, Chem.
Phys. Lett., 157, 479.

[Rehfuss et al., 1988]
Rehfuss, B. D., Liu, D. J., Dinelli, B. M., et al. 1988, J. Chem. Phys., 89,

[Sun et al., 2010]
Sun, M., Halfen, D. T., Min, J., et al. 2010, J. Chem. Phys., 133, 174301

[Sur et al., 2005]
Sur, C., Sahoo, B. K., Chaudhuri, R. K., Das, B. P., & Mukherjee, D. 2005,
Eur. Phys. J. D, 32, 25.

[Thaddeus et al., 1984]
Thaddeus, P., Cummins, S. E., & Linke, R. A. 1984, ApJ, 23, L45

[Thümmel et al., 1989]
Thümmel, H., Klotz, R., & Peyerimhoff, S. D. 1989, Chem. Phys., 129, 417

[Törring & Hoeft, 1986]
Törring, T., & Hoeft, J. 1986, Chem. Phys. Lett., 126, 477

[Woon, 1996]
Woon, D. E. 1996, Astrophys. J., 456, 602

[Woon & Dunning, 1995]
Woon, D. E., & Dunning, T. H. 1995, J. Chem. Phys, 103, 4572

[Zingsheim et al., 2017]
Zingsheim, O., Martin-Drumel, M. A., Thorwirth, S., et al. 2017, J. Phys.
Chem. Lett., 8, 3776

[Ziurys et al., 1995]
Ziurys, L. M., Apponi, A. J., Guélin, M., & Cernicharo, J. 1995, ApJ, 445,

Laboratory rotational frequencies of MgC$_2$.

Isotopologue       2cTransition       Frequency

$J'_{K_a K_c} - J''_{K_a K_c}$       $F'-F''$       (MHz)

$^{24}$Mg$^{12}$C$_2$     $1_{01} - 0_{00}$     $\cdots$     20896.090(2)

$2_{02} - 1_{01}$     $\cdots$    41711.852(4)

$^{24}$Mg$^{13}$C$^{12}$C     $1_{01} - 0_{00}$     $\cdots$     20443.702(2)

$^{24}$Mg$^{13}$C$_2$     $1_{01} - 0_{00}$     $\cdots$     20027.207(2)

$^{25}$Mg$^{12}$C$_2$     $1_{01} - 0_{00}$     $2.5-2.5$     20509.780(4)

$3.5-2.5$     20512.245(4)

$1.5-2.5$     20513.305(4)

$^{26}$Mg$^{12}$C$_2$     $1_{01} - 0_{00}$     $\cdots$     20157.202(2)
Estimated uncertainties are given in parentheses in units of the last digit.

l ccCCCcccc[ht]

Lines of MgC$_2$ in IRC+10216

Isotopologue       Transition        $\nu_\mathrm{obs}$a        $\nu_\mathrm{obs-calc}$        $E_{u}/k$        $S$        $\int{T_\mathrm{A}^{*} dv}$b        $\theta_{\mathrm{B}}$        $\eta_{\mathrm{B}}$        $W$c

$J'_{K_a K_c} - J''_{K_a K_c}$        (MHz)        (MHz)        (K)                 (mK )        $(\arcsec)$                (mK )

$^{24}$MgC$_2$         $2_{02}-1_{01}$         $41711.82\pm0.02$        -0.034         3.00         2.00                              $221\pm10$         42.5       0.53         $1254\pm138$

$4_{04}-3_{03}$     $82787.94\pm0.02$        0.015         9.97         3.99               $362\pm10$         29.7       0.853         $841\pm87$

$4_{23}-3_{22}$     $83511.00\pm0.15$        -0.096        17.98         3.00               $108\pm11$         29.5       0.853         $249\pm36$

$4_{22}-3_{21}$     $84304.13\pm0.04$        0.105        18.04         3.00               $149\pm9$         29.2       0.853         $340\pm40$

$5_{05}-4_{04}$     $102907.74\pm0.10$        0.137        14.91         4.98              $248\pm8$         23.9       0.853         $476\pm50$

$5_{42}-4_{41}$d      $104610.76\pm0.30$        -0.463        46.88         1.80             $35\pm8$         23.5       0.853         $65\pm16$

$5_{41}-4_{40}$d     $104610.76\pm0.30$        -0.762        46.88         1.80              $35\pm8$         23.5       0.853         $65\pm16$

$5_{23}-4_{22}$     $105852.05\pm0.15$        -0.338        23.12         4.20              $164\pm9$         23.2       0.853         $308\pm35$

$6_{06}-5_{05}$     $122684.00\pm0.50$        -0.084        20.80         5.97              $251\pm30$         20.1       0.785         $463\pm89$

$7_{07}-6_{06}$     $142108.88\pm0.10$        -0.077        27.62         6.96              $83\pm6$         17.3       0.785         $141\pm23$

$7_{25}-6_{24}$     $149761.18\pm0.20$        -0.189        36.43         6.43              $38\pm7$         16.4       0.785         $63\pm15$

$^{25}$MgC$_2$         $2_{02}-1_{01}$         $40949.33\pm0.20$        -0.267         3.00         2.00              $34\pm5$         42.5       0.53         $193\pm34$

$^{26}$MgC$_2$         $2_{02}-1_{01}$         $40245.20\pm0.20$        -0.085         2.90         2.00           $46\pm8$         42.5       0.53         $261\pm52$

$4_{04}-3_{03}$     $79942.90\pm0.30$        0.171         9.62         3.99               $41\pm13$         29.7       0.853         $99\pm33$

$5_{05}-4_{04}$     $99428.70\pm0.40$        -0.138        14.40         4.98               $45\pm10$         29.7       0.853         $89\pm22$
Unless otherwise noted, estimated uncertainties are $1\sigma$. Frequencies subtracted from those observed are calculated from the constants in Table <ref>. $E_{u}$ is the energy of the upper state of the transition, and $S$ is the asymmetric rotor line strength.  $\mathrm{\alpha_{J2000}=09^{h}47^{m}57^{s}{.}36,\delta_{J2000}=+13^{\circ}16\arcmin44{.}{\arcsec}4}$.
aOn the assumption of $v_\mathrm{LSR}=-26.5$ .
bDerived from least-squares fits of shell profiles to the spectra shown in Figs. <ref> and <ref>; in some cases the expansion velocity was fixed to $14.5$ .
c$W=\int{T_\mathrm{A}^{*} dv}/\eta_\mathrm{B}f_\mathrm{D}$, where $f_\mathrm{D} = \theta_\mathrm{S}^2/(\theta_\mathrm{S}^2 + \theta_\mathrm{B}^2)$ and the source diameter $\theta_\mathrm{S} = 30\arcsec$. Errors include calibration uncertainties of $10\%$ at 7 mm, $10\%$ at 3 mm, and $15\%$ at 2 mm, as well as an assumed error of 1 D on the dipole moment, added in quadrature.
dUnresolved doublet with each component assumed to lie at the same frequency and possess half the intensity.

l C C C

Spectroscopic Constants of MgC$_2$

Constant       $^{24}$MgC$_2$        $^{25}$MgC$_2$       $^{26}$MgC$_2$

4lRotational and centrifugal distortion constants (MHz):

$A$     51900(1)       51899.8b       51897.6b

$(B+C)/2$     10448.0740(9)      10255.8294(12)       10078.601(1)

$(B-C)/4$       526.033(14)       507.046b       490.890(61)

$10^{3}\Delta_{J}$     14.454(101)        ⋯     ⋯

$10^{3}\Delta_{JK}$    245.12(169)        ⋯     ⋯

$10^{3}\Delta_{K}$      -37.84a       ⋯    ⋯

$10^{3}\delta_{J}$     0.369(168)        ⋯    ⋯

$10^{3}\delta_{K}$    148.03a       ⋯    ⋯

4lElectric quadrupole coupling constants (MHz):

$\chi_{aa}$      ⋯    -11.75(2)       ⋯

$\chi_{bb}$      ⋯      4.8(10)       ⋯

$\sigma_\mathrm{nrms}$    1.37       0.29       0.40

4lInertial defect (amu-Å$^{2}$):

$\Delta$     0.1035(3)        0.1037        0.125(1)
Constants are derived from a least-squares fit to the rotational transitions in Tables <ref> and <ref>.  The $1\sigma$ uncertainties are indicated in  parentheses, with the least significant digit corresponding to the least significant digit of the value.  Parameters for which no errors are indicated have been fixed to the theoretical values.
aSecond-order vibrational perturbation theory (VPT2) value at the CCSD(T)/cc-pVTZ level of theory.
bFixed to the experimental values derived from $^{24}$MgC$_2$: the equilibrium isotope shift was taken from the semi-experimental equilibrium structure, and the zero-point correction from the variational calculations (Appendix <ref>).

The equilibrium geometry of MgC$_2$.

Basis set       $r_\mathrm{CC}$       $r_\mathrm{Mg-C_2}$

D     1.29422     1.96504

T     1.27545     1.92117

Q     1.27175     1.91073

5     1.27082     1.90741

CBS     1.27068     1.90673

$r_\mathrm{se}$     1.2706(7)     1.9066(1)
The CCSD(T)/cc-pCV$X$Z bond lengths (in $\mathrm{\AA}$) are shown for $X$ = D–5, followed by the complete basis set (CBS) extrapolation. The semi-experimental equilibrium geometry ($r_{\mathrm{se}}$) was determined as discussed in the text. $r_{\mathrm{CC}}$ is the C-C distance and $r_{\mathrm{Mg-C_2}}$ is the distance between Mg and the CC center-of-mass.

Lower rotational energy levels of MgC$_2$. Red lines indicate the observed laboratory transitions and blue arrows the astronomical transitions. The inset shows the semi-experimental equilibrium structure.

Laboratory measurements of the two lowest rotational transitions of $^{24}$MgC$_2$. The cavity-FTMW signal (bottom) centered at 20896.090 MHz is split into two Doppler components due to the co-axial cavity geometry. Its complex amplitude response (top) is plotted as a function of the double resonance pump frequency relative to 41711.852 MHz. The solid and dashed curves are the fitted saturated Lorentzian line profiles for the real and imaginary parts, respectively. Each panel represents 6.5 h of integration or about 120,000 laser shots.

Spectra of $^{24}$MgC$_2$ toward IRC+10216. The fitted profiles are plotted in red. `U' indicates unidentified lines.

Spectra of $^{25}$MgC$_2$ and $^{26}$MgC$_2$ toward IRC+10216. The simulated profile of the $2_{02} - 1_{01}$ transition of $^{26}$MgC$_2$ (shown in blue in the top left panel) accounts for contamination from overlapping CH$_2$CN transitions (shown in red); the total emission is shown in magenta. The profile for $^{25}$MgC$_2$ (top right) includes quadrupole hyperfine splittings calculated from the laboratory constants.
`U' indicates unidentified lines.

Rotational temperature diagram of $^{24}$MgC$_2$ in IRC+10216, fitted  with the two-temperature model described in Appendix <ref>.  The slope of the parallel lines through each $K$ ladder yields the rotational temperature ($T_\mathrm{rot}$), and the slope of the line through points across the $K$ ladders yields the kinetic temperature ($T_\mathrm{kin}$).  The flux of the $K=4$ transition is assumed to be one-half the total flux of the unresolved $5_{42} - 4_{41}$/$5_{41} - 4_{40}$ doublet. The error bar on each data point is twice the error shown in Table <ref>.  Error bars on the parameters are twice the standard error of the fit.