* [50] Mattingly, J. C., Pardoux, É.: Malliavin calculus for the stochastic 2d Navier–Stokes equation. Commun. Pure Appl. Math. 59(12), 1742–1790 (2006)
  * [51] Masmoudi, N., Young, L.-S.: Ergodic theory of infinite dimensional systems with applications to dissipative parabolic PDEs. Comm.Math. Phys. 227(3), 461–481 (2002)
  * [52] Nualart, D.: The Malliavin calculus and related topics. Probability and its Applications (New York), 2nd edn. Springer, Berlin (2006)
  * [53] Majid, N.R.: Entrance laws of generalized Ornstein-Uhlenbeck processes and asymptotic strong feller property for non-autonomous semigroups. (2013)
  * [54] Shirikyan, A.: Law of large numbers and central limit theorem for randomly forced PDE’s. Probab. Theory Related Fields 134 (2), 215–247 (2006)
  * [55] Villani, C.: Optimal Transport, Old and New, Volume 338 of Springer Science and Business Media (2008)


# Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search
Time in Trees

Svein Høgemo
University of Bergen E-mail<EMAIL_ADDRESS>
###### Abstract

The graph invariant EPT-sum has cropped up in several unrelated fields in
later years: As an objective function for hierarchical clustering, as a more
fine-grained version of the classical edge ranking problem, and, specifically
when the input is a vertex-weighted tree, as a measure of average/expected
search length in a partially ordered set. The EPT-sum of a graph $G$ is
defined as the minimum sum of the depth of every leaf in an edge partition
tree (EPT), a rooted tree where leaves correspond to vertices in $G$ and
internal nodes correspond to edges in $G$.

A simple algorithm that approximates EPT-sum on trees is given by recursively
choosing the most balanced edge in the input tree $G$ to build an EPT of $G$.
Due to its fast runtime, this balanced cut algorithm is used in practice. In
this paper, we show that the balanced cut algorithm gives a 1.5-approximation
of EPT-sum on trees, which amounts to a tight analysis and answers a question
posed by Cicalese et al. in 2014.

##  1 Introduction

Searching in ordered structures is a basic problem in computer science and has
seen a lot of attention since the dawn of the field [17, 29]. Some special
cases are well understood, e.g. the best search strategy in a totally ordered
set is a binary search tree, and the problem of optimal search in totally
ordered sets given a probability distribution on the elements was treated by
Knuth [21] and Hu and Tucker [19] in 1971. Also, if the search space is every
single subset of elements, then it is known that the optimum search strategy
is given by a Huffman tree (see [19]). Apart from such specific subcases,
little is known except that they are hard problems [11, 24].

An interesting subclass of partially ordered sets are “tree-like posets”,
those posets whose Hasse diagrams are rooted trees, or in other words those
posets where for any two elements $a,b$, the sets $\\{x\mid x\preceq a\\}$ and
$\\{x\mid x\preceq b\\}$ either are disjoint, or one is contained in the
other. They generalize totally ordered sets (whose Hasse diagrams are paths),
but are still much easier to work with than the general case of posets. The
average performance of search strategies for tree-like posets have been
studied by Laber and Molinaro in [22] and later by Cicalese et al. in [10,
11]. For these posets, the optimum search strategy with respect to average
search time can be shown to be equal to the _EPT-sum_ of their Hasse diagrams,
a graph invariant named by Høgemo et al. in [18], but defined and used several
times earlier in different circumstances.

###  1.1 EPT’s and EPT-sum

An _edge partition tree_ , or EPT for short, of a graph $G$ is a rooted tree
where every leaf corresponds to a vertex in $G$, the root corresponds to an
edge $e$ in $G$, and each child of the root is itself the root of an EPT of a
component of $G\setminus e$. The EPT-sum of $G$ with respect to some EPT $T$
is, loosely speaking, defined as the sum of the depth of each leaf in $T$; and
the EPT-sum of $G$ is defined as the minimum over all EPT’s. Viewing the EPT
as a certain search strategy in the graph $G$ where, upon each edge $e$, one
can query which of the components of $G\setminus e$ contains the wanted
vertex, the EPT-sum of $G$ with respect to $T$ is the combined search time of
locating every vertex in $G$ with this search strategy. Giving a probability
distribution to $V(G)$, the weighted EPT-sum is equal to the expected search
time for a vertex pulled at random from the given distribution. When $G$ is
itself a tree, this search strategy is equivalent to the usual search strategy
on the tree-like poset that has $G$ as its Hasse diagram. The aforementioned
edge rank problem, on the other hand, can be interpreted as finding a search
strategy with optimal _worst-case_ performance on a tree-like poset.

Given a tree $G$, we are interested in the following algorithm (the _balanced
cut algorithm_) to make an approximately optimal EPT of $G$ (with respect to
EPT-sum):

  * •

Find a balanced cut in $G$, i.e. an edge $e$ that minimizes the size of the
biggest component in $G\setminus e$.

  * •

Make $e$ the root of $T$.

  * •

Make EPT’s of the components of $G\setminus e$ recursively, and make the roots
of those trees children of $e$.

The balanced cut algorithm is attractive because of its runtime: Finding a
balanced edge in a tree takes $O(n)$ time, so making a balanced EPT can
trivially be done in $O(n^{2})$ time. However, this runtime can be reduced to
$O(n\log^{2}n)$, as shown in Lemma 1. This makes it practical for any
potential applications of searching in trees.

For the case of vertex-weighted trees, Cicalese et al. [10, 11] show a lower
and upper bound on the performance of the balanced cut algorithm of 1.5 and
$\varphi=\frac{\sqrt{5}+1}{2}$, respectively. They ask what the actual
performance of this algorithm actually is, and conjecture that it does provide
a 1.5-approximation, matching the lower bound.

In this paper we will affirm this conjecture, by proving that the balanced cut
algorithm indeed does give a 1.5-approximation of $\mathsf{EPT\text{-}sum}$ on
vertex-weighted trees. Our proof proceeds by constructing a so-called
_augmented tree_ , built from an optimum EPT by subdividing half of its edges,
and showing that it has $\mathsf{EPT\text{-}sum}$ at most 1.5 times the
optimum. Thereafter we iteratively apply operations to this tree that are
guaranteed to not increase the $\mathsf{EPT\text{-}sum}$, eventually arriving
at the EPT constructed by the balanced cut-algorithm.

###  1.2 Applications of EPT-sum to Hierarchical Clustering

Employing edge-weighted graphs, EPT-sum was considered by Dasgupta in [14] as
a suitable objective function for measuring the quality of hierarchical
clusterings of similarity graphs (where large weights mean high similarity and
vice versa). In this paper and a string of follow-ups [8, 13, 30], several
attractive properties of EPT-sum as an objective function were highlighted,
and algorithms for optimizing EPT-sum of edge-weighted graphs were proposed.
In light of this, a balanced edge of a tree is just a special case of the
_sparsest cut_ of an edge-weighted graph, a partition $(A,B)$ of $V(G)$ that
minimizes the ratio $(\sum_{e\in E(G[A,B])}x_{e})/(|A|\cdot|B|)$ (where
$x_{e}$ is the weight of the edge $e$). In general graphs, the sparsest cut is
itself NP-hard, and hard to approximate to a constant (given standard
complexity-theoretic assumptions [2, 9]), but Charikar and Chatziafratis [8]
showed that given an $\alpha$-approximation algorithm for sparsest cut, one
could find an $8\alpha$-approximation for EPT-sum. The state-of-the-art for
approximating sparsest cut in general graphs is the $O(\sqrt{\log n})$
algorithm due to Arora et al. [3].

The aforementioned results by Charikar and Chatziafratis clearly indicate that
the balanced cut algorithm gives an 8-approximation of the
$\mathsf{EPT\text{-}sum}$ of edge-weighted trees (and other graph classes for
which an optimal sparsest cut can be found in polynomial time, like planar
graphs, see [1] for more information). Whether this is the real approximation
ratio is, however, unknown.

###  1.3 Related Parameters

EPT’s were introduced by Iyer et al. in [20] along with the _edge rank
problem_ ; the problem of finding an EPT of a graph with lowest possible
height. EPT’s are a variation of _vertex partitioning trees_ or VPT’s, defined
similarly but where every node in the tree corresponds to a vertex in the
graph. VPT’s and the _node rank problem_ (also called _tree-depth_) of finding
a VPT of lowest height have applications in such disparate areas as VLSI chip
design [25], sparse matrix multiplication [7, 26], and structural graph theory
[27, 28]. The edge rank problem was rediscovered in terms of searching in
tree-like posets by Ben-Asher et al. [4], who also found a polynomial-time
algorithm for the problem (although polynomial- and linear-time algorithms
were already known for edge ranking, see [15, 23]) The equivalence between
edge rank of trees and searching in tree-like posets was first pointed out by
Dereniowski in [16].

There are also several relevant results on the related parameter of _VPT-sum_
; the VPT-sum of a graph $G$ with respect to a VPT $T$ is the sum of depth
plus one of every node in the VPT. Optimizing VPT is, on trees, equivalent to
optimizing a different search model where one has access to an oracle which,
for each vertex $v\in V(G)$, answers which of the components of $G\setminus v$
contains the vertex one is searching for. For this parameter, the
corresponding strategy of recursively choosing the most balanced vertex (i.e.
the _centroid_) to build a VPT, was recently shown by Berendsohn et al. [5] to
give exactly a 2-approximation of VPT-sum – both for weighted and unweighted
trees. (In contrast, for EPT-sum we have no strong lower bounds for the
approximation ratio of this algorithm on unweighted trees; the algorithm is
known to not give optimal EPT’s, but the maximum known asymptotical
approximation ratio on unweighted trees is only $(1+\frac{\Omega(1)}{n})$
[18]). In addition, there exists a PTAS for VPT-sum on trees [6].

EPT-sum and the related parameters that are treated in [18] are all NP-hard to
calculate on general, unweighted graphs. In contrast, on unweighted trees, the
complexity of EPT-sum and VPT-sum are unknown. For vertex-weighted trees, the
complexity of calculating VPT-sum is also, to the best of our knowledge,
unknown, but it is NP-hard to calculate EPT-sum [10]. One should note that in
the NP-hardness reductions employed in [10], the trees have exponential
weights. In [18], a polynomial-time algorithm for EPT-sum of unweighted
caterpillars was given, based on an equivalence between EPT-sum on vertex-
weighted trees and unweighted trees. So, if EPT-sum is NP-hard on trees where
every vertex has polynomial weight, then it is also NP-hard on unweighted
trees.

Independently of the result itself, we believe that there might be some
interest in the proof technique used here. Specifically, the trick of building
an augmented tree that has cost 1.5 times the optimum has, to our knowledge,
not been used before.

###  1.4 Organization

The rest of the paper is organized as follows: in Section 2 we give basic
definitions and a brief discussion on EPT’s and EPT-sum in the context of
searching in trees. We also show that there is an algorithm for making
balanced EPT’s that run in $O(n\log^{2}n)$ time. In Section 3 we prove the
main result of this paper, namely the fact that a balanced EPT has EPT-sum at
most 1.5 the optimum. Finally, in Section 4 we restate some of the most
relevant results and open problems regarding computing and approximating EPT-
sum on trees.

##  2 Preliminaries

###  2.1 Basic notions

In general, we follow the notation established in [18]. The vertex set and
edge set of a graph $G$ is denoted $V(G)$ and $E(G)$, respectively. Given
vertices $S\subseteq V(G)$, $G[S]$ signifies the induced subgraph of $G$ on
$S$. As both the input graphs and the output data structures are trees, we
employ the following conventions to avoid confusion: An unrooted tree that is
given as input is denoted $G$, while a rooted tree generated as output is
denoted $T$, and its vertices are called _nodes_. For a node $x\in V(T)$,
$T[x]$ signifies the rooted subtree of $T$ rooted in $x$. The set of _leaves_
in $T$ is denoted $L(T)$, a node which is not a leaf is called an _internal
node_. A _full binary tree_ is a binary tree where every internal node has
exactly two children.

The _depth_ of a node $x$ in a rooted tree $T$ is equal to the distance from
the root $r$ to $x$ in $T$. For example, $r$ itself has depth 0. The _height_
of $T$ is the maximum depth out of any node in $T$. The nodes on the path from
$r$ to $x$ (including both $r$ and $x$) are the _ancestors_ of $x$, and $x$ is
a _descendant_ of all these nodes.

###  2.2 Edge Partition Trees

Given a connected graph $G$, an _edge partition tree_ , or EPT for short, of
$G$ is a rooted tree with $|V(G)|$ leaves and $|E(G)|$ internal nodes, that
can be defined inductively as follows:

  * •

The EPT of a graph with a single vertex is a tree with a single node.

  * •

For a bigger graph $G$, the root $r$ of any EPT $T$ corresponds to an edge
$e\in E(G)$, and $r$ has at most two children $c_{1},c_{2}$; one for each
component of $G\setminus e$. $T[c_{1}]$ (and $T[c_{2}]$, if it exists) are, in
turn, EPT’s of the component(s) of $G\setminus e$.

Figure 1: An unweighted tree $G$ and an EPT $T$ of $G$. Adding up the depth of
each leaf, one sees that $\mathsf{EPT\text{-}sum}(G,T)=39$. This is not
optimal for $G$; a better EPT can be made by making the edge $ef$ (which
incidentally is also the most balanced edge in $G$) root.

An EPT is, as such, a binary tree. $G$ is a tree if and only if any (and
every) EPT of $G$ is a full binary tree (since in that case, every edge of $G$
is a bridge). Since we focus on trees as input, we assume that EPT’s are full
binary trees.

There is a bijection from the vertex set of $G$ to the leaves of $T$, and
likewise from the edge set of $G$ to the internal vertices of $T$. To simplify
notation somewhat, we will not notate these bijections and rather say that
each leaf of $T$ _is_ a vertex of $G$ and each internal node of $T$ _is_ an
edge of $G$.

###  2.3 EPT-sum and Searching in Trees

The focus of this paper is on the graph measure called EPT-sum. We give the
most general definition, where $G$ is equipped with both edge and vertex
weights:

Given a graph $G$ with vertex weights $W=\\{w_{v}\mid v\in V(G)\\}$ and edge
weights $X=\\{x_{e}\mid e\in E(G)\\}$, and an EPT $T$ of $G$, the EPT-sum of
$G$ with respect to $T$, $\mathsf{EPT\text{-}sum}(G,T)$ is equal to

$\sum_{e\in E(G)}x_{e}\cdot(\sum_{v\in L(T[e])}w_{v})$

If $G$ is not vertex-weighted, we can replace the sum of vertex-weights by
$|L(T[e])|$.

We can easily verify through reordering of terms that EPT-sum can be
equivalently defined as

$\sum_{v\in V(G)}w_{v}\cdot(\sum_{e\in\mathrm{\>ancestors\>of\>}v}x_{e})$

If $G$ is not edge-weighted, we can replace the sum of edge-weights by simply
the depth of $v$ in $T$. The graphs we will treat in this paper are vertex-
weighted, but not edge-weighted. Therefore the formula $\sum_{v\in
V(G)}(w_{v}\cdot dist_{T}(r,v))$, where $r$ is the root of $T$, is a natural
choice to use.

It is also this formulation that makes EPT-sum and similar measures attractive
for measuring the performance of search trees. Rooting a tree $G$ in an
arbitrary vertex $r$ and treating it as a Hasse diagram of some poset
$(V,\preceq)$, one sees that a search query of the type “is $x\preceq v$?”
partitions the tree into $G[v]$ (when it returns true) and $G\setminus G[v]$
(when it returns false), which are exactly the components of $G\setminus e$
where $e$ is the edge from $v$ to its parent. Then, if $\\{w_{v}\mid v\in
V\\}$ is a probability distribution, then the EPT-sum of the Hasse diagram $G$
with respect to some EPT $T$ is equal to the expected search length for an $x$
in $V$ (chosen randomly according to the probability distribution), given a
search strategy corresponding to $T$. This equivalence is a variant of the
equivalence between edge rank and worst-case performance of searching in
trees.

We must note that the equivalence between EPT-sum and average search time only
holds if the Hasse diagram actually is a rooted tree; otherwise the
relationship between these two problems is more complicated. This is evident
from the fact that the sparsest cut algorithm from [8] provides a
$O(\sqrt{\log n})$-time approximation of EPT-sum in edge-weighted graphs,
while it was proven in [10] that searching in posets (i.e. vertex-weighted
DAG’s) has no $o(\log n)$-approximation unless every problem in NP has a
quasi-polynomial algorithm.

###  2.4 A Fast Balanced Cut Algorithm

Before moving on to the main result, we show that finding a balanced EPT can
be done more quickly than the basic algorithm outlined in the introduction.
This has probably been noted beforehand; however we have been unable to find
such a result in the literature.

######  Lemma 1.

Given a tree $G$, one can compute a balanced EPT of $G$ in time
$O(n\log^{2}n)$.

###### Proof.

We will make use of the following observation: A balanced edge $e$ is an edge
that maximizes the size of the smallest component $C_{e}^{\min}$ when $e$ is
removed. If $|C_{e}^{\min}|\geq\frac{1}{3}|G|$, then the size of the biggest
component $C_{e}^{\max}$ is at most $\frac{2}{3}|G|$. However, if
$|C_{e}^{\min}|<\frac{1}{3}|G|$, then the next most balanced edge in
$C_{e}^{\max}$ must still be the most balanced edge after $e$ is removed. This
continues until the size of the big component has shrunk enough that it is
less than twice the size of the “small” component (i.e. the smallest in $G$)
for the next considered edge. At this point, the big component must be
strictly less than $\frac{2}{3}|G|$. Therefore, we can consider the following
algorithm:

  * •

Locate a centroid vertex $c$ in $G$. Put all edges $e_{1},\ldots,e_{k}$
incident on $c$ into a list; these must all be the most balanced edges in a
big component.

  * •

Sort each edge $e_{i}$ in descending order after $|C_{e_{i}}^{\min}|$. This is
done in time $O(n\log n)$.

  * •

Find the minimum $s<k$ such that
$n-\sum_{i=1}^{s}|C_{e_{i}}^{\min}|<2|C_{e_{s+1}}^{\min}|$.

  * •

Make a caterpillar-shaped partial EPT $T$ with $e_{1}$ as root and
$e_{2},\ldots,e_{s}$ downward.

  * •

Build onto $T$ by recursing on the subtrees left by removing
$e_{1},\ldots,e_{s}$ from $G$.

Not having to recompute the most balanced edges until every component has size
at most $\frac{2}{3}|G|$ makes this algorithm have runtime $O(n\log^{2}n)$. ∎

##  3 Balanced EPT’s have EPT-sum at most 1.5 the Optimum

We will go through the proof with unweighted graphs in mind, but note that the
proof is agnostic as to whether the vertices have weights. The proof therefore
also works for vertex-weighted trees.

The first step is building the tree that has $\mathsf{EPT\text{-}sum}$ at most
1.5 times as high as the optimal tree.

######  Definition 1 (Augmented tree).

Given a full binary tree $T$, the augmented tree of $T$, denoted $aug(T)$, is
constructed in the following manner: For any internal node $v\in V(T)$ with
children $c_{l},c_{r}$, choose one child (say, $c_{r}$) with the property that
$|L(T[c_{r}])|\leq|L(T[c_{l}])|$ (this is obviously true for at least one of
$c_{l},c_{r}$). Then, subdivide the edge $vc_{r}$ once.

If $T$ is an EPT of a tree $G$, then $aug(T)$ is not an EPT of $G$, since it
has more internal nodes than there are edges in $G$. Nonetheless, we define
$\mathsf{EPT\text{-}sum}(aug(T))$ to be the sum of depths of leaves in
$aug(T)$.

######  Lemma 2.

For any full binary tree $T$,
$\mathsf{EPT\text{-}sum}(aug(T))\leq\frac{3}{2}\mathsf{EPT\text{-}sum}(T)$.

###### Proof.

The proof goes by induction. For the base case, we observe that a full binary
tree with one leaf has $\mathsf{EPT\text{-}sum}$ equal to 0, and no edges to
augment.

For the inductive step, assume that the lemma holds for any full binary tree
with at most $n-1\geq 1$ leaves, and let $T$ be an arbitrary full binary tree
with $n$ leaves, and $aug(T)$ the augmented tree of $T$. Furthermore, let $r$
be the root of $T$, and $c_{l},c_{r}$ the children of $r$. Note that $c_{l}$
and $c_{r}$ are guaranteed to exist from the assumtion that $T$ is a full
binary tree with at least two leaves. Also, note that $aug(T)[c_{l}]$ (resp.
$aug(T)[c_{r}]$) is the augmented tree $aug(T[c_{l}])$ (resp.
$aug(T[c_{r}])$).

W.l.o.g. assume that $rc_{r}$ is the edge from $r$ to its children that is
subdivided in $aug(T)$. Then we know that $|L(T[c_{r}])|\leq\frac{n}{2}$.
Also, both $T[c_{l}]$ and $T[c_{r}]$ have at most $n-1$ leaves.

By definition,

$\mathsf{EPT\text{-}sum}(T)=\mathsf{EPT\text{-}sum}(T[c_{l}])+\mathsf{EPT\text{-}sum}(T[c_{r}])+n$

while

$\mathsf{EPT\text{-}sum}(aug(T))=\mathsf{EPT\text{-}sum}(aug(T[c_{l}]))+\mathsf{EPT\text{-}sum}(aug(T[c_{r}]))+n+|L(T[c_{r}])|$

which we have seen to be upper-bounded by

$\mathsf{EPT\text{-}sum}(aug(T[c_{l}]))+\mathsf{EPT\text{-}sum}(aug(T[c_{r}]))+\frac{3}{2}n$

Therefore

$\frac{\mathsf{EPT\text{-}sum}(aug(T))}{\mathsf{EPT\text{-}sum}(T)}\leq\frac{\mathsf{EPT\text{-}sum}(aug(T[c_{l}]))+\mathsf{EPT\text{-}sum}(aug(T[c_{r}]))+\frac{3}{2}n}{\mathsf{EPT\text{-}sum}(T[c_{l}])+\mathsf{EPT\text{-}sum}(T[c_{r}])+n}$

This fraction is a mediant of the three fractions
$\frac{\mathsf{EPT\text{-}sum}(aug(T[c_{l}]))}{\mathsf{EPT\text{-}sum}(T[c_{l}])}$,
$\frac{\mathsf{EPT\text{-}sum}(aug(T[c_{r}]))}{\mathsf{EPT\text{-}sum}(T[c_{r}])}$
and $\frac{3}{2}$. By the induction hypothesis, all these fractions are upper-
bounded by $\frac{3}{2}$, from which we conclude that
$\frac{\mathsf{EPT\text{-}sum}(aug(T))}{\mathsf{EPT\text{-}sum}(T)}\leq\frac{3}{2}$.
∎

One should note that this Lemma also holds for EPT’s of vertex-weighted trees;
this is easily seen by replacing $\frac{n}{2}$ with $\frac{\sum_{v\in
V(G)}w_{v}}{2}$ in the formula.

######  Theorem 1.

The balanced cut-algorithm gives a 1.5-approximation of
$\mathsf{EPT\text{-}sum}$ on trees.

###### Proof.

Let $G$ be an unrooted tree, with $T^{*}$ an optimal EPT of $G$, and
$T^{\prime}$ an EPT of $G$ given by the balanced cut-algorithm. We want to
show that
$\mathsf{EPT\text{-}sum}(T^{\prime})\leq\mathsf{EPT\text{-}sum}(aug(T^{*}))$.
We achieve this through a procedure that incrementally modifies $aug(T^{*})$
into $T^{\prime}$. Formally, we generate a series of trees
$T_{0},T_{1},\ldots,T_{t}$ where $T_{0}=aug(T^{*})$, $T_{t}=T^{\prime}$ and,
for every $0\leq i<t$, $T_{i+1}$ is made from $T_{i}$ by way of the following
algorithm:

  * •

If $T_{i}=T^{\prime}$: set $t:=i$ and halt.

  * •

Otherwise: select a node $v\in V(T_{i})$ that has a subdivided edge to one of
its children, but where none of its ancestors have such an edge.

  * •

If $v$ is a leaf: do nothing.

  * •

Otherwise: modify $T_{i}[v]$ in a suitable way, according to Cases 1-7 below
(depending on where the balanced edge of $G[v]$ is located in $T_{i}[v]$).

  * •

Set $T_{i+1}$ equal to the modified tree.

When a balanced edge has been placed correctly in the EPT, the subdivided edge
from it to one of its children is smoothed out; therefore the $T$ is gradually
modified from an augmented EPT to a non-augmented EPT. Also, because of this,
the node $v$ that has been chosen at a particular step is guaranteed to be a
node that has not been placed correctly yet, but where all of its ancestors
have been placed correctly.

The proof hinges on being able to show that the following invariant holds for
every $0\leq i\leq t$:

$\mathsf{EPT\text{-}sum}(G,T_{i})\leq\mathsf{EPT\text{-}sum}(G,aug(T^{*}))$

The invariant trivially holds for $i=0$. The rest of the proof goes by
induction; assuming that the invariant holds for some $i$ and showing that it
then also must hold for $i+1$. It is not hard to see, given the definition

$\mathsf{EPT\text{-}sum}(G,T)=\sum_{e\in E(G)}(\sum_{v\in L(T[e])}w_{v})$

that if the modification from $T_{i}$ to $T_{i+1}$ is constrained to the
rooted subtree $T_{i}[v]$, then

$\mathsf{EPT\text{-}sum}(G,T_{i+1})-\mathsf{EPT\text{-}sum}(G,T_{i})=\mathsf{EPT\text{-}sum}(G,T_{i+1}[v])-\mathsf{EPT\text{-}sum}(G,T_{i}[v])$

(this is what Dasgupta [14] refers to as _modularity of cost_).

How to actually modify $T_{i}$ depends on where the balanced edge is located,
and is subject to a lengthy case analysis, which constitutes the rest of the
proof. Each case concentrates on a subtree $T_{i}[v]$ where $v$ was selected
in the manner described above. For visual aid, we include a picture of each
case and how that particular tree is modified.

We will employ the following conventions throughout the case analysis: The
balanced edge in question is denoted $e$, and its corresponding node in
$T_{i}[v]$ is located in the subtree on the left hand side of the root (except
in Case 1). The leftmost and rightmost subsets of leaves (corresponding to
subsets of $V(G)$) are called $A$ and $B$, respectively, and the root is
called $v$, its left child $l$, and $l$’s right child is called $b$ (except in
Cases 1-2). Lastly, $A\cup B$ never forms a connected subgraph of $G$ (again,
except in Case 1, where $A\cup B$ is the whole of $G[L(T_{i}[v])]$). Note that
since $e$ lies in the left subtree, the right subtree must be strictly
smaller, and can therefore safely be assumed to be the one having a subdivided
edge from the root in $T_{i}[v]$.

Given these conventions, one should take care to get convinced that in each
case, all rooted subtrees (both in the original tree and the modified one)
induce connected subgraphs of $G$; this is important, as it is necessary in
order for the tree to be an EPT.

In the figures, pink dots signify subdivision nodes. A pink line between two
edges signify that one of those edges is subdivided (whichever leads to the
subtree with the fewest leaves), but we do not know which.

Case 1: $v=e$.

Figure 2: Case 1.

This is certainly the easiest case. The only modification we do is smoothing
the subdivided edge from the root. It is trivial to show that
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$ and
the invariant holds.

Case 2: $l=e$.

Figure 3: Case 2.

Both here and in the following cases, we need to remember that $A$ is defined
to be separated from $B$ by $M$, therefore $G[B\cup M]$ is connected.

In this case, we perform a simple rotation on $T_{i}[v]$, and smooth the
subdivided edge from $v$ to $B$. We further smooth the edge from $e$ to the
smallest subtree of $A$ and $M$, and $A$ decreases one in depth, but we
subdivide the edge from $v$ to the smallest subtree out of $M$ and $B$.

When we calculate the change in cost, it is easiest to somehow separate the
certain changes (the level of each subtree when disregarding subdivision
nodes, as well as those subdivision nodes we know the placement of) from the
uncertain changes (the subdivision nodes we do not know the placement of,
corresponding to pink lines in the figures). For example, $A$ certainly gets
exactly one level shallower, if we disregard the subdivision node that may or
may not go from $e$ to $A$. $B$ certainly stays at the same level if we count
the subdivision node that certainly goes from $v$ to $B$ that is removed, but
disregard the subdivision node that may be placed in between $v$ and $B$
again, if $|B|\leq|M|$. Taking all this into account, the change in cost
therefore simplifies to

$\min(|M|,|B|)-$ $(|A|+\min(|A|,|M|))$

where all increase is collected on the top line and decrease on the bottom
line. (We will not describe the steps taken and the reasoning behind the
change in cost in such detail in the later, more complicated cases. Rather, we
refer to the figures for visual aid.) We observe that the inequality
$|A|\geq|B|$ must hold, as otherwise $v$ would lead to a more balanced cut
than $e$. Therefore the change in cost is non-positive and
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$; thus
the invariant holds.

Case 3: $e$ lies inside $G[A]$.

Figure 4: Case 3.

This is a unique case in the sense that we do not care to balance the root of
$T_{i}[v]$ at this step. Therefore it is important to keep the subdivided edge
$v$ in this case, so that we can balance $T_{i+1}[v]$ at a later step, before
moving to its subtrees.

We observe that the inequality $|A|\geq|M|+|B|$ must hold, otherwise $l$ would
lead to a more balanced cut than $e$ (this is also why the edge from $l$ to
$M$ is subdivided). The change in cost is

$(|B|+\min(|M|,|B|))-$ $|A|$

From the aforementioned inequality, the change in cost is non-positive and
therefore
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$; thus
the invariant holds.

In the next three cases (4-6), we assume that $A$ and $B$ lie on different
sides of $e$, i.e. that there are connected subgraphs $G[L],G[R]$ such that
the components of $G[L(T_{i}[v])]\setminus e$ are $G[A\cup L]$ and $G[B\cup
R]$.

Case 4: $e$ is the root of the tree containing $L\cup R$.

Figure 5: Case 4.

Here, the change in cost is

$(\min(|A|,|L|)+\min(|R|,|B|))-$ $(\min(|A|,|L\cup R|)+\min(|L|,|R|)+|L|+|R|)$

As the sum of the top row is clearly at most $|L|+|R|$, the change in cost is
non-positive and
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$; thus
the invariant holds.

Case 5: $e$ lies inside the subtree induced by the child of $b$ containing
$R$.

Figure 6: Case 5.

Both here and in the next case, we must “tear apart” the subtree containing
$e$ (in this case $T_{i}[L_{2}\cup R]$), by forcing $e$ to become the root.
However, it is clear that, even when augmented, the two subtrees
$T_{i+1}[L_{2}]$ and $T_{i+1}[R]$ in sum have lower $\mathsf{EPT\text{-}sum}$
than $T_{i}[L_{2}\cup R]$ has. So, we can infer that the change in cost is at
most

$(\min(|A|,|L|)+\min(|L_{1}|,|L_{2}|)+\min(|R|,|B|))-$ $(\min(|A|,|L\cup
R|)+\min(|L_{1}|,|L_{2}\cup R|)+|R|)$

where we assume $L=L_{1}\cup L_{2}$. We see that each term in the top row is
at most as high as the corresponding term in the bottom row. As such, the
change in cost is non-positive and
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$; thus
the invariant holds.

Case 6: $e$ lies inside the subtree induced by the child of $b$ containing
$L$.

Figure 7: Case 6.

As in the previous case, we do not care about the fact that we must tear apart
the subtree containing $e$. Furthermore, we argue that the sum of the
$\mathsf{EPT\text{-}sum}$ of the torn-apart trees is strictly lower than
$\mathsf{EPT\text{-}sum}(T_{i}[L\cup R_{1}]$. Look at the root of that tree.
Either that root is equal to $e$, in which both $L$ and $R_{1}$ sit at a lower
level in $T_{i}[v]$ than what is shown in the drawing, or it is not equal to
$e$, in which one of the two – at least the smallest one – sits at a lower
level than what is shown in the drawing. We can therefore add a
$\min(|L|,|R_{1}|)$ to the bottom line of the change in cost which thus reads

$(\min(|A|,|L|)+\min(|R|,|B|)+\min(|R_{1}|,|R_{2}|))-$ $(\min(|A|,|L\cup
R|)+|L|+\min(|L\cup R_{1}|,|R_{2}|)+\min(|L|,|R_{1}|))$

where $R=R_{1}\cup R_{2}$. This is the most complicated case, and we must
employ four sub-cases corresponding to what the bottom line evaluates to.

_Case 6a)_ : $|A|>|L\cup R|$

In this case, the upper line is upper-bounded by

$(|L|+|R|+\min(|R_{1}|,|R_{2}|))$

and the lower line is lower-bounded by

$(|L|+|R|+\min(|L\cup R_{1}|,|R_{2}|))$

The change in cost is non-positive.

_Case 6b)_ : $|A|\leq|L\cup R|$ and $|L|<|R_{1}|$

In this case, the upper line is upper-bounded by

$(|L|+|B|+\min(|R_{1}|,|R_{2}|))$

and the lower line is lower-bounded by

$(|A|+2|L|+\min(|L\cup R_{1}|,|R_{2}|))$

We observe that the inequality $|A|+|L|\geq|B|$ must hold, otherwise $v$ would
lead to a more balanced cut than $e$. Therefore, the change in cost is non-
positive.

_Case 6c)_ : $|A|\leq|L\cup R|$ and $|L|\geq|R_{1}|$ and $|L\cup
R_{1}|>|R_{2}|$

In this case, the upper line is upper-bounded by

$(|A|+|R_{1}|+|R|)$

and the lower line is equal to

$(|A|+|L|+|R|)$

. By the definition of this case, the change in cost is non-positive.

_Case 6d)_ : $|A|\leq|L\cup R|$ and $|L|\geq|R_{1}|$ and $|L\cup
R_{1}|\leq|R_{2}|$

In this case, the upper line is upper-bounded by

$(|L|+|B|+|R_{1}|)$

and the lower line is equal to

$(|A|+2|L|+2|R_{1}|)$

. As, again, $|A|+|L|\geq|B|$, the change in cost is non-positive.

As we have argued, no matter how the sizes of different subtrees relate to
each other,
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$ and
the invariant holds.

In the last case, we assume that subtrees $A$ and $B$ lie on the same side of
$e$, and assume w.l.o.g. that the components of $G[L(T_{i}[v])]\setminus e$
are $G[A\cup B\cup R]$ and $G[L]$.

Case 7: $e$ lies within $L\cup R$ and $A$ and $B$ are in the same component of
$G-e$.

Figure 8: Case 7.

In this last case, we will look inside the tree covering $L\cup R$ and
enumerate each part of $R$, i.e. $R_{1},\ldots,R_{k-1}$, that is split off
before reaching a cut involving $L$, in order to accurately argue about how
the cost changes when modifying $T$. The crucial point here is that $|L|$ is
at least as large as both $|A|$, $|B|$ and $|R_{i}|$ for every $1\leq i\leq
k-1$, otherwise $v$, $l$ or $b_{i}$ respectively would have led to a more
balanced cut than $e$. Looking at the drawing, we reckon that every pink line
in $T_{i+1}[e]$ incurs at most as high a cost as the corresponding pink dot in
$T_{i}[v]$. We therefore disregard the pink dots and lines, and observe that
$A$, $B$ and $R_{1},\ldots,R_{k-1}$ all increase in depth between $T_{i}$ and
$T_{i+1}$, while $L$ decrease in depth. The change of cost is therefore upper-
bounded by

$(|B|+|A|+\sum_{i=1}^{k-1}|R_{i}|)-$ $(k+1)|L|$

As all the terms on the upper line, of which there are $k+1$, are at most
$|L|$, the change in cost is non-positive and
$\mathsf{EPT\text{-}sum}(G,T_{i+1})\leq\mathsf{EPT\text{-}sum}(G,T_{i})$; thus
the invariant holds.

With the assumptions placed on the orientation of $T_{i}[v]$, there is no
placement of the balanced edge $e$ that is not covered by one of the Cases
1-7. The procedure must halt after a finite amount of steps (specifically,
$O(n^{2})$ steps), because each internal node (corresponding to an edge in
$G$, of which there are $n-1$) is correctly placed in accordance with
$T^{\prime}$ in a linear amount of steps. For each subtree, Case 3 may be
encountered $O(n)$ times, while any other case may be encountered maximally
one time. From this fact and the fact that the invariant holds, we conclude
that the theorem is true. ∎

######  Corollary 1.

Theorem 1 holds also for vertex-weighted trees.

###### Proof.

This follows directly from replacing sizes of subsets of vertices ($|A|$,
$|B|$, $|M|$ etc.) with their weighted equivalents ($\sum_{a\in A}w_{a}$,
$\sum_{b\in B}w_{b}$ etc.). All the inequalities used in the proof must still
hold, since a balanced edge in a vertex-weighted tree is defined to be
balanced with respect to the weights. ∎

##  4 Conclusion

We have shown that the simple balanced cut algorithm gives a 1.5-approximation
of EPT-sum on vertex-weighted trees, and therefore of the minimum average
search time in trees.

There are some questions remaining. For the case of weighted trees, Cicalese
et al. [11] showed that for the balanced cut algorithm, an approximation ratio
of 1.5 must be the best possible, as for any lower ratio, there is an infinite
family of graphs failing to achieve that ratio by the balanced cut algorithm.
On the other hand, for unweighted trees, we have no such lower bounds. The
highest ratio found is by taking the smallest tree in the family found in
[18], a tree with 14 vertices; calculating the EPT-sum of the optimal EPT and
the one found by taking balanced cuts, the approximation ratio turns out to be
$\frac{65}{58}$ for this tree (for the family as a whole, the ratio is
$(1+o(1))$, as previously mentioned). We leave it as an open problem to close
the gap between $\frac{65}{58}$ and 1.5 for unweighted trees.

It must also be noted that for calculating EPT-sum on unweighted trees, it is
still unknown whether the problem is NP-hard or polynomial-time solvable. For
the related parameter of edge ranking (equivalent to minimum worst-case search
time in trees), there are polynomial- and even linear-time algorithms [4, 15,
23], but these are non-trivial. If EPT-sum of unweighted trees is solvable in
polynomial time, then there are few reasons to believe that an algorithm
should be any easier to find.

Finally, in this paper we did not focus on edge-weighted trees. It is not hard
to show that Lemma 2 still holds for trees with weights on both vertices and
edges, by defining the augmented tree to have a weight on each of their
subdivision nodes equal to that of its parent. On the other hand, as the
sparsest cut of an edge-weighted tree is more complex than the balanced cut of
an unweighted (or vertex-weighted) tree, we did not try to adapt the proof of
Theorem 1 to the setting of edge-weighted trees. Of course, the approximation
ratio for trees that are both edge- and vertex-weighted cannot be better than
that of trees that are only vertex-weighted, but we do not know if there are
any strictly larger lower bounds for this case. Cicalese et al [12] have
looked at this problem and provided hardness results for some very restricted
classes of trees, as well as an $O(\frac{\log n}{\log\log n})$-approximation
algorithm. It does not go against their results if the sparsest cut algorithm
finds a constant approximation also in this case: in fact, for trees that are
only edge-weighted, the previously mentioned results of Charikar and
Chatziafratis [8] imply that this algorithm should give a constant (8)
approximation factor. Whether the actual factor for edge-weighted trees (with
or without vertex weights) is as low as 1.5 is an interesting question, and a
natural next step for anyone interested in the average performance of
searching in trees.

## References

  * [1] A. Abboud, V. Cohen-Addad, and P. N. Klein.  New hardness results for planar graph problems in p and an algorithm for sparsest cut.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 996–1009, 2020.
  * [2] Christoph Ambuhl, Monaldo Mastrolilli, and Ola Svensson.  Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 329–337. IEEE, 2007.
  * [3] Sanjeev Arora, Satish Rao, and Umesh Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM, 56(2), 2009.
  * [4] Yosi Ben-Asher, Eitan Farchi, and Ilan Newman.  Optimal search in trees.  SIAM Journal on Computing, 28(6):2090–2102, 1999.
  * [5] B.A. Berendsohn, I. Golinsky, H. Kaplan, and L. Kozma.  Fast approximation of search trees on trees with centroid trees, 2022.  arXiv preprint [cs.DS], https://arxiv.org/abs/2209.08024.
  * [6] B.A. Berendsohn and L. Kozma.  Splay trees on trees.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1875–1900, 2022.
  * [7] Jean RS Blair and Barry Peyton.  An introduction to chordal graphs and clique trees.  In Graph theory and sparse matrix computation, pages 1–29. Springer, 1993.
  * [8] M. Charikar and V. Chatziafratis.  Approximate hierarchical clustering via sparsest cut and spreading metrics.  In Annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 841–854, 2017.
  * [9] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar.  On the hardness of approximating multicut and sparsest-cut.  computational complexity, 15:94–114, 2006.
  * [10] F. Cicalese, T. Jacobs, E. Laber, and M. Molinaro.  On the complexity of searching in trees and partially ordered structures.  Theoretical Computer Science, 412(50):6879–6896, 2011.
  * [11] F. Cicalese, T. Jacobs, E. Laber, and M. Molinaro.  Improved approximation algorithms for the average-case tree searching problem.  Algorithmica, 68(4):1045–1074, 2014.
  * [12] Ferdinando Cicalese, Balázs Keszegh, Bernard Lidickỳ, Dömötör Pálvölgyi, and Tomáš Valla.  On the tree search problem with non-uniform costs.  Theoretical Computer Science, 647:22–32, 2016.
  * [13] V. Cohen-Addad, V. Kanade, F. Mallmann-Trenn, and C. Mathieu.  Hierarchical clustering: Objective functions and algorithms.  Journal of ACM, 66(4):26:1–26–42, 2019.
  * [14] S. Dasgupta.  A cost function for similarity-based hierarchical clustering.  In Annual ACM symposium on Theory of Computing (STOC), pages 118–127, 2016.
  * [15] P. de la Torre, R. Greenlaw, and A. A Schäffer.  Optimal edge ranking of trees in polynomial time.  Algorithmica, 13(6):592–618, 1995.
  * [16] Dariusz Dereniowski.  Edge ranking and searching in partial orders.  Discrete Applied Mathematics, 156(13):2493–2500, 2008.  Fifth International Conference on Graphs and Optimization.
  * [17] Thomas N Hibbard.  Some combinatorial properties of certain trees with applications to searching and sorting.  Journal of the ACM (JACM), 9(1):13–28, 1962.
  * [18] Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul, and Jan Arne Telle.  On dasgupta’s hierarchical clustering objective and its relation to other graph parameters.  arXiv preprint arXiv:2105.12093, 2021.
  * [19] T.C. Hu and A.C. Tucker.  Optimal computer search trees and variable-length alphabetical codes.  SIAM Journal on Applied Mathematics, 21(4):514–532, 1971.
  * [20] A.V. Iyer, H.D. Ratliff, and G. Vijayan.  On an edge ranking problem of trees and graphs.  Discrete Applied Mathematics, 30(1):43–52, 1991.
  * [21] Donald E. Knuth.  Optimum binary search trees.  Acta informatica, 1:14–25, 1971.
  * [22] Eduardo Laber and Marco Molinaro.  An approximation algorithm for binary searching in trees.  Algorithmica, 59(4):601–620, 2011.
  * [23] T. W. Lam and F. L. Yue.  Optimal edge ranking of trees in linear time.  Algorithmica, 30(1):12–33, 2001.
  * [24] Hyafil Laurent and Ronald L Rivest.  Constructing optimal binary decision trees is np-complete.  Information processing letters, 5(1):15–17, 1976.
  * [25] Charles E Leiserson.  Area-efficient graph layouts (for vlsi).  In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 270–281. IEEE, 1980.
  * [26] Joseph WH Liu.  The role of elimination trees in sparse factorization.  SIAM journal on matrix analysis and applications, 11(1):134–172, 1990.
  * [27] J. Nešetřil and P. Ossona de Mendez.  On low tree-depth decompositions.  Graphs and Combinatorics, 31(6):1941–1963, 2015.
  * [28] J. Nešetřil and P. Ossona de Mendez.  Tree-depth, subgraph coloring and homomorphism bounds.  European Journal of Combinatorics, 27(6):1022–1041, 2006.
  * [29] Jürg Nievergelt and Edward M Reingold.  Binary search trees of bounded balance.  In Proceedings of the fourth annual ACM symposium on Theory of computing, pages 137–142, 1972.
  * [30] A. Roy and S. Pokutta.  Hierarchical clustering via spreading metrics.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 2324–2332, 2016.


$M\gtrsim 10^{5}M_{\odot}$, formed via AC, from Pop III/II galaxies (see Figs.
23and 24 )

The main takeaway of Fig. 19 is that at SMDSs will appear as point objects,
independent of the magnification factor. In contrast, all young Pop III/II
galactic counterparts of a $10^{6}M_{\odot}$ SMDS formed via AC would be
resolved by RST with $\mu\gtrsim 40$ thus making disambiguation possible based
on image morphology whenever $\mu\gtrsim 40$. For $10^{6}M_{\odot}$ SMDSs
formed via Capture, the same would be possible with a higher magnification
factor of $\mu\gtrsim 125$ but at $\mu\sim 100$ it will be hard to
disambiguate them from young Pop III.1A galaxies. For lower mass SMDSs
($M\lesssim 10^{5}M_{\odot}$), independent of formation mechanism, one needs
$\mu\gg 100$ to be able to use image morphology as a RST differentiating tool
from young Pop III/II galaxies.

Figure 20: Using lensing to differentiate SMDS vs. old galaxies: Same as Fig.
19, but this time considering old galaxies. For all galaxies the age chosen is
100 Myrs old, except for the case of Pop III.1A/C galaxies, that cease to emit
light after about 3.5 Myrs. As in the previous figure, the horizontal black
dotted lines (the Rayleigh criterion) represent the diffraction limit, above
which one can tell an extended object from a point source: i.e. objects with
apparent sizes above this horizontal line can be resolved. As shown in the top
two panels, at $\mu\sim 10$ most of the Pop III/II galaxies counterparts to
$10^{6}M_{\odot}$ SMDSs will appear as resolved, extended objects, and can be
differentiated from $10^{6}M_{\odot}$ SMDSs which appear as point sources. As
shown in the lower two panels, the galaxies matching the lower mass
($10^{5}M_{\odot}$ ) SMDSs will be more compact and appear as resolved,
extended objects at $\mu\sim 30$ and can be differentiated from SMDS.

In Fig. 20 we repeat the same analysis done in Fig. 19, this time for older
galaxies, with age of 100 Myrs.242424For the case of the top heavy IMF Pop
III.1 galaxies, since most of their stars exhaust the nuclear fuel after $\sim
3.5$ Myrs, we select a time just shy of this value as their “old” age. The top
two panels of Fig. 20 demonstrate that most old galaxies that match the flux
of a $10^{6}M_{\odot}$ SMDSs in the F184 band will be above the resolution
limit as soon as they are detected at a $S/N=5$ level. The only exception is
the Pop III.1 galaxies (blue lines), which, when contrasted against a
$10^{6}M_{\odot}$ SMDSs formed via DM capture (top left panel) can be detected
as unresolved, as long as it is magnified by $\mu\lesssim 5$. With this in
mind we conclude that old galaxies would be, in principle, differentiable from
$10^{6}M_{\odot}$ SMDSs based on image morphology. Regarding the
$10^{5}M_{\odot}$ SMDSs, all of their old Pop III/II galactic counterparts are
large enough to be resolved at $\mu$ ranging from a few to a few tens. In
particular, for the case of the $10^{5}M_{\odot}$ SMDS formed via DM Capture
(lower left panel of Fig. 20) by $\mu\sim 50$ even the more compact Pop III.1A
(blue solid line) galaxies are resolved. When contrasting $10^{5}M_{\odot}$
SMDSs formed via extended AC (lower right panel) we note that at $\mu\gtrsim
20$ all Pop III/II galaxies will show as extended objects, in contrast to the
SMDS. Thus, differentiation based on image morphology of a $\sim
10^{5}M_{\odot}$ SMDS, formed via either mechanism, from Pop III/II old
galaxies is possible with magnifications $\mu\gtrsim 50$.

Since the age of an object detected with photometry cannot be estimated
exactly, one should view our two extreme cases considered in Figs. 19 and 20
as the two limits in between which any observation would lie. Moreover, we
point out that the size of the galaxies or other lensed objects will depend on
the assumed lensing model and is usually associated with a large error bar, as
shown for example in Fig. 8 of 2019arXiv190308177L. Thus one should be careful
in using the Rayleigh criterion as a disambiguation between galaxies (extended
objects) and SMDSs with purely stellar spectra (point objects), especially
whenever the objects are barely resolved.

In summary, in this section we have demonstrated that, with sufficient
magnification ($\mu\gtrsim 40$), a $10^{6}M_{\odot}$ SMDS formed via AC can be
differentiated via image morphology from all Pop III/II galaxies considered.
The galaxies would all appear as extended objects whereas the SMDSs are still
unresolved, even for $\mu\gg 100$ (see top right panels of Figs. 19 and 20).
In contrast, for all $\mu\lesssim 100$, image morphology cannot be used to
conclusively differentiate between galaxies and $M\lesssim 10^{5}M_{\odot}$
SMDS (lower panel of Figs. 19) or between galaxies and a $10^{6}M_{\odot}$
SMDS formed via DM Capture (top left panel of Fig. 19). In the next section we
will explore if lensed SMDSs can be differentiated from Pop III/II galaxies
based on their locations in color-color diagrams.

###  7.2 SNR Ratio and Color-color Diagram

In this subsection we discuss the effects of gravitational lensing on the
prospect of detecting smaller mass SMDSs and the possibility to use color-
color diagrams to differentiate those SMDSs from Pop III/II galaxies. We begin
our analysis by asking the following question: what is the required
magnification factor needed for a SMDS of a given mass in order to be
detectable with RST at the level of SNR=5? In order to answer this question we
plot in Fig. 21 the values of the SNR in the F184 band as a function of
magnification ($\mu$) for SMDS of various masses (as labeled) formed either
via DM capture (left panel) or adiabatic contraction (right panel). The SNR
values are estimated using Pandia and are selected from the pixel where most
of the the photons from the SMDS will generate a signal, in a hypothetical
$10^{6}$ s exposure. We noted before that at the same mass SMDSs formed via AC
look brighter that their counterparts formed via DM capture, which can also be
seen in the slightly larger SNR values on the curves in the right panel (SMDS
AC) of Fig. 21. The main takeaway of Fig. 21 is that magnification factors of
$\mu\gtrsim 10$ are sufficient to lead to SMDSs of $M\sim 10^{4}M_{\odot}$
(formed via either mechanism) to be detectable with $10^{6}$ s exposures by
RST.

Figure 21: SNR values of SMDSs of masses $10^{4}$–$10^{6}M_{\odot}$ (at
$z_{emi}=12$) versus magnification factor ($\mu$) powered by 100 GeV WIMPs.
The SNR value was calculated assuming $10^{6}s$ exposure time and the F184
filter. The left panel represents SMDSs formed via DM Capture and the right
panel represents those formed via adiabatic contraction (AC). The horizontal
line corresponds to SNR=5, which is usually the minimum value required to
claim detection. This plot shows that SMDSs with $M\sim 10^{4}M_{\odot}$ could
be detectable with moderate amount of lensing ($\mu\sim 10$).

In Fig. 22 we repeat the same exercise done in Fig. 21, but this time we
consider Dark Stars of lower masses, i.e. with $M\lesssim 10^{3}M_{\odot}$. We
assume $z_{emi}\simeq 12$, and a heat source from 100 GeV WIMPs powering the
DSs. The properties of DS models used here (such as $T_{eff}$ and $R$) are
taken from Table 2 of Spolyar:2009. In the left panel of Fig 22 we show the
SNR values in the F184 RST band, whereas the right panel depicts the SNR
values in the F213 RST band. In both cases an exposure time of $10^{6}$s is
assumed. The weakened sensitivity in the F213 filter leads to higher $\mu$
values required for a detection at the same SNR level. Further, we can comment
on the difference between the cases of SMDS formed by AC (the 479$M_{\odot}$
and 716 $M_{\odot}$ SMDSs shown in the figure) vs. the DS formed via capture
(the 756$M_{\odot}$ and 787 $M_{\odot}$ DSs shown in the figure). SMDSs formed
via capture are hotter, leading to a peak in the SED is at shorter
wavelengths. Thus, in the two filters considered here, the 479$M_{\odot}$ and
756 $M_{\odot}$ DSs (formed via capture) are somewhat dimmer and require more
magnification (a larger $\mu$) than the 716$M_{\odot}$ and 787 $M_{\odot}$ DSs
formed via AC.

The main takeaway of Fig. 22 is that Dark Stars as distant as $z_{emi}\simeq
12$, with masses as low as $M\simeq 800M_{\odot}$ can be observed with RST, if
magnified by $\mu$ of a few hundreds or more. This is consistent with the
findings of Zackrisson:2010HighZDS, who shows that for $\mu\simeq 160$ DS at
$z_{emi}\simeq 12$, with masses as low as $700M_{\odot}$ can be detected at
the SNR=5 level in JWST, assuming exposure times of 100 hours.

Figure 22: SNR values versus magnification factor ($\mu$) for Dark Stars of
masses $479$ and $716M_{\odot}$ for the case of extended AC, and $756$ and
$787M_{\odot}$ for the case of captured DM. We take $z_{emi}=12$ and
annihilation of 100 GeV WIMPs to be the heat source for the SMDSs. The SNR
values are calculated assuming $10^{6}s$ exposure time and the F184/F213
filters (left/right panels). The horizontal line corresponds to SNR=5, which
is usually the minimum value required to claim detection. The parameters for
the Dark Star models are taken from Spolyar:2009. Note that for the same
object, a higher magnification is needed in order for it to be detected at the
same SNR level in the F213 filter vs the F184 filter. This is indicative of
the weakened sensitivity at higher wavelengths. The main takeaway of this
figure is that Dark Stars with masses as low as $\sim 800M_{\odot}$ can be
detected with RST, if magnified by lensing factors $\mu$ of the order of a few
hundred. Figure 23: Color-color plots as in Fig.17, but here we have assumed
the lensing factor $\mu=100$. The red circle and stars with 1-sigma error bars
represent individual SMDS formed via Capture and AC respectively, this time
with masses $2\times 10^{4},10^{5},10^{6}M_{\odot}$. Evolutionary tracks are
also schown for both type A (left panel) and Type C (right panel) Pop III/II
galaxies. All SMDSs formed via DM capture, regardless of stellar mass, occupy
roughly the same spot (red circles), lie along the evolutionary lines of
galaxies, and can therefore not be differentiated from galaxies. On the other
hand, SMDSs formed via AC (red stars in both panels) have color-color indices
that could differentiate them from galaxies. Figure 24: Similar to Fig.23, we
plot the color indices of our $z_{emi}=12$ target objects assuming lensing
magnification $\mu=100$ for the case of SMDS formed by AC of mass
$10^{5}M_{\odot}$(left panels) and $10^{6}M_{\odot}$(right panels). We include
the $2\sigma$ error ellipses both for the SMDS colors and those of the Pop
III/II galaxies along their evolutionary tracks. Note that we have not plotted
lighter SMDS as they are indistiguishable from galaxies at the $2\sigma$ level
for this value of magnification. We only keep Pop III/II Kroupa galaxies as
our galactic candidates since their evolutionary tracks are closest to the
chosen SMDSs. The panels on the top row are the comparisons to galaxies with
full nebular emission contribution (type A), whereas all the bottom panels are
the comparisons to the galaxies with no nebular contribution (type C). We find
that based on their color indices one can distinguish lensed ($\mu\sim 100$)
SMDSs with $M\sim 10^{5},10^{6}M_{\odot}$ from Pop III/II galaxies, as
observed with RST, at the 2$\sigma$ level; i.e., SMDSs with $M\sim
10^{5},10^{6}M_{\odot}$ deviate by at least $2\sigma$ in each direction from
the evolutionary tracks (green and gray lines) of the color indices of the
first generation of galaxies.

In the reminder of this subsection we focus on the role of gravitational
lensing on differentiating SMDSs from Pop III/II galaxies using the color
color techique discussed in Sec. 6.4. We start with Fig. 23, where the color
index analysis in the $m_{184}-m_{213}$ vs. $m_{158}-m_{184}$ plane presented
in Fig 17 is redone, assuming now that all objects are magnified with a
lensing factor $\mu=100$. In the left/right panel we compare the color indices
of SMDSs formed via DM capture (red circles) and adiabatic contraction (red
star symbols) to the evolutionary tracks of Pop III/II type A/C. For each SMDS
we calculate the size of the error bar according to Eq. (11). The boosted SNRs
lead to a significant reduction of the uncertainty in the color indices of
SMDSs, as can be seen by comparing Figs. 17 and 23. Moreover, since SMDSs
formed via DM capture have roughly equal temperature, independent of stellar
mass, their SEDs (and therefore colors) do not change significantly as the
SMDS grows. For this reason all the color indices of the SMDSs formed via DM
capture are stacked upon each other at a point that is very close to the
evolutionary tracks of both type galaxies. This reinforces once more that SMDS
formed via DM capture can be easily mistaken for early galaxies if neither of
those objects is resolved. We don’t add here error bars for the points along
the evolutionary tracks of galaxies, as those uncertainties will will be
dependent on the SNR (via Eq. 11), and, as such, on the mass of the SMDSs
counterpart. However, we revisit this in Fig. 24 where we plot separately each
SMDSs formed via AC, which allows for inclusion of uncertainties in color
indices of both galaxies and SMDSs.

As already stated, Fig. 23 reinforces the point that SMDSs formed via capture
are great Pop III/II galactic chameleons. Independent of their mass, they will
occupy the same spot in the $m_{158}-m_{184}$ vs. $m_{184}-m_{213}$ color
color plot, a spot that is along the evolutionary lines of both type A (left
panel) and type C (right panel) galaxies. We already knew that from the SED
comparisons, where we found that SMDSs formed via DM capture will have almost
indistinguishable SEDs from old Type A galaxies and most type C galaxies
(Figs. 11 and 12). A natural question arises: can one, in absence of spectral
data, tell apart a SMDSs formed via DM capture from the Pop III/II galaxies
counterparts that occupy roughly the same location in the color color plot of
Fig. 23? First, notice that the color-color technique is very valuable, as it
clearly disambiguates between both types SMDSs and Pop III.1A galaxies.
Therefore, considering the case of a $10^{6}M_{\odot}$ SMDS formed via DM
capture, for $\mu\gtrsim 40$, image morphology can break the degeneracy
presented in Fig. 23, as at those magifications the galactic counterparts
(that also occupy the same location in the color color plot) will be all
resolved, whereas the SMDSs will still be well under the resolution limit (see
Fig. 19). Naturally, for lower mass SMDSs, a larger magnification is required
to achieve the same effect.

When contrasting SDMSs formed via extended AC (red star symbols in Fig. 23) to
Pop III/II galaxies, the situation becomes more promising, as SMDS of smaller
and smaller mass deviate more and more from the evolutionary tracks of both
type A and C of galaxies. All SMDSs formed via this mechanism, boosted by
$\mu\sim 100$, will be more than $2\sigma$ away from the evolutionary tracks
of galaxies. The one caveat here is that Fig. 23 does not include the
uncertainty in the color indices of galaxies, as explained above. We address
this point in Fig. 24, where we present the color index comparison between
SMDSs formed via AC of $10^{5}$ and $10^{6}M_{\odot}$ to the evolutionary
tracks of Type A/C Pop III/II galaxies (top/bottom panels) that are selected
in such a way that they match the F184 flux of the SMDS, as per our comparison
criterion. For all objects a gravitational lensing magnification factor of
$\mu=100$ is assumed. As opposed to Fig. 23, here we can include both
uncertainties for the SMDS colors and those of the Pop III/II galaxies, along
their evolutionary tracks, as in each panel the SNR of galaxies and the star
is determined uniquely. In order to be conservative, and avoid unnecessarily
cluttering the plots, we only keep the Kroupa IMF type galaxies in this
figure, since their evolutionary tracks lie closest to the SMDSs. However, our
conclusions are unaffected by this aesthetic simplification.

For the magnification $\mu=100$ assumed in Fig. 24, we find that $10^{5}$ and
$10^{6}M_{\odot}$ SMDS formed via extended AC are separated at the 2$\sigma$
level (in each direction) from the evolutionary tracks of the Pop III/II
galaxies counterparts that have the same F184 flux. For smaller SMDS, the
distinction between SMDS and galaxies is even smaller. Hence a larger
magnification would be required to cleanly differentiate the type of object in
a color-color plot. If objects with high enough magnification are found to
unambiguously identify a SMDS, such a discovery could indirectly confirm the
nature of the DM.

##  8 Summary and Conclusions

Dark Stars (DSs) can form at redshift $z\sim 10-20$. Made almost entirely of
hydrogen and helium, they are fueled by Dark Matter heating. As they are
relatively cool ($T_{eff}\lesssim 50,000$ K) Dark Stars can grow, via
accretion, to become supermassive (SMDS) and extremely bright. In this paper
we examined the capability of the upcoming Roman Space Telescope (RST) to
detect SMDSs. First we showed that the sensitivity of RST does indeed allow
for detection of SMDS, and then we turned to the question of whether or not
they can be differentiated in the data from high redshift galaxies.

Roman Space Telescope will be an excellent observatory in the search for Dark
Stars. Due to its large field of view, it has great potential for discovery of
new objects at redshifts $z<16$. In this paper we considered Supermassive Dark
Stars in the mass range $10^{4}-10^{6}M_{\odot}$ formed via two possible
mechanisms: Extended AC and Capture. Here, “Extended AC” refers to the case in
which the DM is accreted gravitationally only; the “Capture” mechanism relies
upon an additional ingredient, capture of further DM via scattering off nuclei
in the star. As our fiducial values, we have studied SMDS emitting at
$z_{emi}=12$ and DM mass $m_{\chi}=$100 GeV.

SMDS detectability in RST: First, we compared predictions of SMDS spectra
(simulated with TLUSTY as shown in Fig. 2) against the sensitivity of RST
filters to determine which SMDSs at which redshifts would be detectable by
RST, using the standard dropout techniques. We found that SMDS candidates
formed via either the capture or extended AC formation mechanism could indeed
be detected by RST using photometry alone.

Figures 5 and 6 show the comparison of AB magnitudes of unlensed SMDSs at
different redshifts, in contrast to the detection limit (S/N=5) for each RST
filter assuming exposure times of $10^{4}$s and $10^{6}$s. For SMDSs with
masses $\sim 10^{6}M_{\odot}$, formed via AC or Capture, we find that at
emission redshift $z_{emi}\sim 10-15$ they would be observable by RST with
$\lesssim 10^{6}$s of exposure time, even if unlensed. With lensing factors of
$\mu\gtrsim 10$, RST can easily observe SMDSs with masses as low as $M\lesssim
10^{4}M_{\odot}$ (See Fig. 21). SMDSs will appear as J-band dropouts at
$z_{emi}\sim 10$ and H-band dropouts at $z_{emi}\sim 13$, and as $F_{184}$
(H/K) dropouts at $z\sim 14$. In order to be able to also include the color
index technique, that requires photometric data in at least three bands, we
chose $z_{emi}\sim 12$, as our fiducial value throughout this paper.

Differentiating SMDS from high redshift galaxies: A key question is whether or
not SMDS can be differentiated in the data from high redshift [zero (Pop III)
or very low metallicity (Pop II)] galaxies. For these galaxies, the spectral
evolution with respect to age, nebular emission, IMF and metallicity were
obtained using the YggDrasil (Zackrisson2011) simulated model grids, and the
relevant choice of parameters are given in Table 5. For the purposes of
comparison to SDMS, we chose Pop III/II galaxies that have the same integrated
observed F184 flux as the dark stars in question. We used several approaches
to see if we can differentiate SDMS from early galaxies: SEDS in photometric
data, location in color-color plots and image morphology (point vs. extended
objects).

Given the resolution of RST, SMDS will be point objects whereas galaxies may
be resolved. Without lensing, many galaxies will remain unresolved so that one
cannot tell the difference from supermassive stars. The higher the
magnification, the more likely that galaxies are resolved whereas SMDS remain
point sources. We estimate that magnification $\mu\sim 100$ is sufficient to
resolve the all galaxies we have investigated, but upcoming observations will
determine this number more accurately. We note that Airy patterns, being
specific only for point objects, would definitively identify them as such.
However, very long exposure times O(year) would be needed for their detection,
since the first ring is only 1.75% as bright as the central spot. Therefore,
discovery of such a pattern in RST is unlikely for Dark Stars, yet it is a
signature of SMDS that future telescopes would be able to see.

For objects only seen with RST photometry (rather than spectroscopy), SEDs of
both SMDS and Pop III/II galaxies can equally well match observations. One
approach to differentiate SMDS vs galaxies would be their location in color-
color plots. We used the Pandeia engine to simulate RST observations of
different candidate objects (e.g. Fig. 15 and 16).252525The simulated SNR
values also allow us to estimate the uncertainty in the absolute magnitude, in
any RST band in which an object is detected. Specifically., we use the F-K vs.
H-F color indices for all of the objects of interest (see Figs. 17, 23 and
24).

Table 3: For the SMDSs of stellar mass and formation mechanism as indicated, the Table summarizes the detectability results based on drop-out, color-color and morphology methods. We show results for the case of no lensing as well as with lensing (magnification factors $\mu$ listed in table header) . In all cases an exposure time of $10^{6}$s is assumed. Formation | $M_{*}\left(M_{\odot}\right)$ | Drop-out | ($SNR>5$) | Morphology | Morphology | Color-color | Color-color
---|---|---|---|---|---|---|---
Mechanism |  | No Lensing | $\mu\sim 100$ | No Lensing | $\mu\sim 100$ | No Lensing | $\mu\sim 100$
Extended AC | $2.04\times 10^{4}$ | No | Yes | No | No | No | No
Extended AC | $10^{5}$ | No | Yes | No | No | No | at 2$\sigma$
Extended AC | $10^{6}$ | Yes | Yes | No | Yes | No | at 2$\sigma$
Capture | $4.1\times 10^{4}$ | No | Yes | No | No | No | No
Capture | $10^{5}$ | No | Yes | No | No | No | No
Capture | $10^{6}$ | Yes | Yes | No | Yes | No | No

In Table 3 we summarize the potential to detect SMDSs and then to disambiguate
them via image morphology and/or color index techniques from their respective
Pop III/II galactic counterparts. The third and fourth columns take binary
(Yes/No) values and address the question of detection at $SNR=5$ level,
without lensing (column three) or with $\mu=100$ lensing (column four).
Similarly, in the fourth and fifth columns we summarize the answers to the
following question: can a SMDSs be differentiated from all possible galactic
counterparts based on image morphology, i.e. point source (SMDSs) vs.
potentially resolved extended object (galaxy). The last two columns summarize
the potential to use the $m_{158}-m_{184}$ vs. $m_{184}-m_{213}$ color diagram
to separate SMDSs of a given mass vs. galaxies.

Differentiating SMDS with masses up to $10^{6}M_{\odot}$ against early
galaxies without spectroscopy proves to be difficult. As mentioned above, both
types of SMDS as well as early galaxies have SEDs that match RST data $\sim$
equally well. For SMDS formed via Extended AC, for SMDS masses with $M\sim
10^{5},10^{6}M_{\odot}$, the loci occupied by the SMDSs in the color-color
plots deviate from the evolutionary lines of Pop III/II galaxies at the
$2\sigma$ level for the case of $\mu\gtrsim 100$ (see Fig. 24). For smaller
SMDS or for higher statistical significance of the difference between the
objects, even larger magnifications would be required. For SMDS formed via
capture, the locations in color-color plots cannot be differentiated from
early galaxies; the only differentiating characteristic would then be that
these are point objects whereas galaxies can be resolved at sufficient
magnifications. For instance, for the $10^{6}M_{\odot}$ SMDS via DM Capture,
by $\mu\gtrsim 100$ all the galactic counterparts are resolved (top left
panels of Figs .19 and 20).

There is a “smoking gun” for detection of SMDS once the spectroscopy is
available: a telltale spectroscopic signature, the HeII $\lambda$1640
absorption line. While RST does not cover the wavelength band required to find
this line (for $z_{\rm emi}\gtrsim 10$), JWST does. Hence the two detectors
can be used together in identifying SMDS. SMDS formed via capture would
produce this line; for the cooler SMDS formed via extended AC, this feature is
present only for extremely massive ($M\gtrsim 10^{6}M_{\odot}$) SMDSs (See
Fig. 2). However, there is a caveat: as yet we have not modeled the nebula
surrounding the star, which in the case of the hotter SMDS formed via capture
could wash out the absorption line and/or produce emission lines. The cooler
SMDS formed via extended AC are not likely to be affected. In followup work,
we plan to use the CLOUDY code to add the effects of the nebula to the stellar
spectra produced by TLUSTY. In any case, should a HeII $\lambda$1640
absorption line be found, it would be a strong indicator that an object found
in RST is a supermassive star rather than an early galaxy.

While the HeII $\lambda$1640 line is a very useful spectroscopic tool, since
it is isolated from other neighbouring lines (see Fig. 2), we note here that
SMDSs differ from Pop III/II galaxies with respect to their spectral
signatures in other important ways. First of all, the Balmer break, i.e. the
sudden jump in the flux at around $\mathrm{0.35}{\mu m}$ (restframe), which
can be seen in the lower two panels of Fig. 2 as a “hump-like” feature. This
feature will be more pronounced for Pop III/II galaxies with nebular emission,
but most importantly, the sequence of lines that follows the Balmer break,
i.e. the Balmer series, are emission lines for galaxies with nebular emission
vs. absorption lines for SMDS with purely stellar spectra. Thus, in addition
to the He II $\lambda$1640 line, as a spectroscopic disambiguation tool, one
can also use lines in the Balmer series as well.

On heavier $10^{7}M_{\odot}$ SMDS: In this paper we have focused on SMDS with
masses up to $10^{6}M_{\odot}$. However, in principle SMDS could grow to
become even heavier, e.g. if they formed in $10^{8}M_{\odot}$ minihalos or if
smaller minihaloes merged together and the DS remains in a dark matter rich
region. We therefore consider below the detectability of $10^{7}M_{\odot}$
SMDS. Since total luminosity scales linearly with mass, these objects would be
ten times brighter than $10^{6}M_{\odot}$ SMDS and thus easier to detect. We
note, however, that differentiation in color-color plots against early
galaxies would actually be more difficult (see Figure 21). On the plus side,
galaxies this bright should be easier to resolve. Thus the differentiation of
these very heavy SMDS vs. early galaxies should be possible. Further, the He
II 1640 line would be more pronounced (deeper) for these hotter objects; such
a line would be detectable in RST only for $z_{emi}<10$ while JWST could find
it even for higher redshift objects. In summary, $10^{7}M_{\odot}$ SMDS are
much brighter, therefore easier to detect as well as differentiate from early
galaxies.

Using RST and JWST together: The primary advantage of RST is that it will have
a much larger field of view than that of JWST. Thus, at the redshifts RST is
able to probe, it will have a larger probability of successfully finding
SMDSs. Two of us ( Ilie:2012) have previously studied SMDS in JWST data
(including estimating the numbers of SMDS one could find with JWST). As shown
in Fig.3, RST and JWST have comparable detector sensitivity for wavelengths up
to $\sim\mathrm{1.8}{\mu m}$, including the J and H bands relevant for
identifying objects as J- and H-band dropouts, corresponding to $z\sim 11$ and
$z\sim 13$ respectively. JWST is far more sensitive at higher wavelengths and
thus can find higher redshift objects than RST can, e.g. K-band dropouts at
$z\gtrsim 15$. JWST can probe, via photometry wavelengths up to
$\mathrm{28}{\mu m}$ (NIRCam up to $\mathrm{5}{\mu m}$ and MIRI from
$\mathrm{5}{\mu m}$ to $\mathrm{28}{\mu m}$), whereas the Wide Field
Instrument (WFI) onboard RST will be sensitive only up to $\mathrm{2.3}{\mu
m}$. In terms of spectroscopy the Grism on RST will be probing up to
$\mathrm{1.93}{\mu m}$, whereas NIRSpec onboard JWST is sensitive up to
$\mathrm{5}{\mu m}$. As such RST will be essentially blind with respect to any
objects at $z_{emi}\gtrsim 18$. At those high redshifts the Gunn-Peterson
trough will cutoff the entirety of the redshifted flux in the region RST is
potentially sensitive to. Moreover, even at the redshift of interest to us in
this paper ($z_{emi}\sim 12$) there is quite important information one can
gain from possible redshifted spectral features that fall outside of the
sensitivity range of RST, such as, for example, the Balmer Break, or other H
or He absorption lines present in the SMDS SEDs. Moreover, with a much larger
aperture, JWST has a better angular resolution. Therefore, once a candidate DS
object is identified by RST, followup observations with JWST could be used to
further verify and validate the Dark Star hypothesis. As mentioned above, a
smoking gun for SMDS is the existence of a He II $\lambda$1640 line, which
would not be expected for the case of early galaxies. While RST wavelengths
are insensitive to this line, spectroscopy with JWST may be able to detect it.

We note that the ability of NIRSpec on JWST to obtain clean spectra is
remarkable, see e.g. GNz11 in GNz11NIRSpec:2023. This $z=10.6$ galaxy has a
spectrum seen to $m_{AB}\sim 26$ in the H-band, which would be comparable to
the brightness of a $M_{\star}\simeq 4\times 10^{6}M_{\odot}$ SMDS formed via
AC, see Fig. 5 in (Ilie:2012). While GNz11 is clearly not a Dark Star, as it
is resolved, and moreover shows numerous metal emission lines (see Fig. 1 of
GNz11NIRSpec:2023), based on the relatively short total exposure time ($\sim
17$ hours) needed to generate its exquisite spectrum with NIRSpec, we would
expect spectroscopy with JWST is a viable tool for a SMDSs. In summary, RST
will be an excellent instrument for finding SMDS candidates, with followup
observations from JWST potentially providing definitive determination of Dark
Star discovery.

In Conclusion: Dark Stars are very bright sources. In fact, a million solar
mass dark star can emit as much light as a billion solar mass galaxy so that
the two look very similar in RST and JWST observations. Hence the conundrum
posed by the many observed bright high redshift objects in JWST, in the
context of the standard $\Lambda$CDM cosmological model, could be alleviated
by the existence of Dark Stars containing much less baryonic mass than would
be required of a comparably bright galaxy.

In this paper we showed that SMDSs candidates formed via either the capture or
extended AC formation mechanism and emitting at redshifts up to $z_{emi}=14$
could be found by RST using photometry alone. We examined how those candidates
could be differentiated from high redshift Pop III or Pop II galaxies, and
summarized our results in this section. There are a number of potential
signatures, including their location in color-color plots and image
morphology. SDMSs with purely stellar spectra would appear as point objects,
very bright ($L\gtrsim 10^{9}L_{\odot}$), yet relatively cool ($T_{eff}\sim
10^{4}$ K) sources. The detection of a He II absorption line at
$\mathrm{0.1640}{\mu m}$ restframe wavelength (the He II $\lambda$1640 line)
with followup spectroscopic observations would be a clear signature of
supermassive dark stars, as this feature is absent in any galactic sources.
The identification of supermassive dark stars would be truly remarkable, as it
would imply the existence of a novel heat source powering stars, such as the
DM annihilation we have studied. Further, such a discovery could open up the
possibility of DM parameter estimations based on observed properties of dark
stars.

##  9 Acknowledgments

K.F. and S.Z. are grateful for support from the Jeff and Gail Kodosky Endowed
Chair in Physics held by K.F. at the Univ. of Texas, Austin. K.F. and S.Z.
acknowledge funding from the U.S. Department of Energy, Office of Science,
Office of High Energy Physics program under Award Number DE-SC0022021. K.F.
acknowledges support by the Vetenskapsradet (Swedish Research Council) through
contract No. 638- 2013-8993 and the Oskar Klein Centre for Cosmoparticle
Physics at Stockholm University. We would acknowledge the useful discussions
with James Rhoads, and help from Steve Finkelstein, Volker Bromm through
personal communication. We are especially grateful for Jonathan Levine’s help
with the error ellipses and for him sharing with us the code he uses to
generate such ellipses for his research. S.Z. would like to give special
thanks to his roommate Changhan Ge who offered help with the Pandeia
simulation installation.

##  Appendix A Pandeia Parameters

In this appendix, we present the key parameters we have used for image
simulation, as described in Tables 4 to 6. The complete input dictionary can
be found on the Pandeia reference paper (pontoppidan2016pandeia), as well as
at the following link:
https://outerspace.stsci.edu/display/PEN/Pandeia+Engine+Input+API. Below we
explain some of the parameters particularly relevant to our work and possible
input choices for those.

  1. 1.

Sersic Index: The morphology of Pop III galaxies remains largely unknown due
to lack of observations. Since the masses of target galaxies are relatively
small, we would expect them to have a shape similar to stellar clusters or
irregular galaxies. The choice of this index $n=1$ (exponential) reflects that
the flux is not overly concentrated at the center. For those galaxies with
stellar mass on the order of $M_{\star}\sim 10^{9}M_{\odot}$, we use the
recent argument on the shape of the first galaxies from 2022arXiv220211925P,
where they have simulated that galaxies of this mass will have Sersic index
$n\lesssim 1.5$. Also, in the recent results from JWST, GLASSz13 fitted the
Sersic index of the observed two galaxies and the results are both $n\lesssim
1$, which is consistent with the simulation. Therefore, we still choose $n=1$
throughout our paper when we scale up the mass. Although, for smaller
galaxies, this might not be accurate description, but it would not
significantly change our conclusion since its angular size is relatively small
to be resolved.

  2. 2.

Group/Integration/Exposure Number: For simplicity, the readout pattern is
chosen as the default for Roman (Deep2). To avoid saturation, the maximal
allowed group number($N_{group}$) for this readout pattern is 20, and the
integration time ($t_{int}$) is a linear function of the group number. For
that case of Deep2, it is given by $t_{int}=t_{frame}\times(20N_{groups}-18)$,
where $\mathrm{t}_{\text{frame}}=10.73677\mathrm{~{}s}$ as the sample exposure
time. Since our desired exposure time would be $\sim 10^{6}s$, we choose the
maximum value for the group number as $N_{group}=20$.262626Differences in the
integration pattern are explained in the fig. 2 of the documentation page:
https://jwst-docs.stsci.edu/jwst-near-infrared-camera/nircam-
instrumentation/nircam-detector-overview/nircam-detector-readout-patterns. We
also have the integration number per exposure ($N_{int}$) and exposure number
($N_{exp}$), that multiply the integration time to give the total exposure
time: $t_{exp}=N_{exp}\times N_{int}\times t_{int}$. Since there’s no special
preference on the choice of these two numbers,272727For a more detailed
understanding of the integration process and observation strategies, one can
refer to https://jwst-docs.stsci.edu/understanding-exposure-times. we choose
$N_{int}=29$ and $N_{exp}=30$ such that the total exposure time is closest to
$10^{6}s$.

  3. 3.

Background Level: the relevant background properties and spectrum are
described at https://jwst-docs.stsci.edu/jwst-general-support/jwst-background-
model. For the range of wavelengts of interest ($\sim[1-2]~{}\mu m$), the
background noise contribution from zodiacal lights and galactic dust
dominates. To acquire optimal observation results and for simplicity, we
choose the minimum zodiacal background as ’minzodi’ and set the background
level to be its benchmark level.

In the three tables below we list input parameters specific to SMDSs (Table
4), Pop III/II galaxies (Table 5), and lastly common to both of those objects
(Table 6) In.

Table 4: Input dictionary unique to the point objects–SMDSs Aperture Size | Sky Annulus
---|---
0.2” | [0.4”,0.6”]
Table 5: Input dictionary unique to extended objects –Pop III/II galaxies. Major | Minor | Geometry | Sersic Index | Norm Method | Aperture Size | Sky Annulus
---|---|---|---|---|---|---
$\mu^{1/2}\times\theta_{eff}$ | $\mu^{1/2}\times\theta_{eff}$ | Sersic | 1 | integ infinity |  $\mu^{1/2}\times$ 0.1” |  $\mu^{1/2}\times$[0.15”,0.2”]
Table 6: Other input parameters used in the Pandeia simulation shared by both SMDSs and Pop III galaxies. Background | Background | Background | Aperture | Group | Integration | Exposure | Readout
---|---|---|---|---|---|---|---
| Level | Subtraction |  | Number | Number | Number | Pattern
minzodi | benchmark | True | imaging | 20 | 29 | 30 | deep2