# First-principles modelling for time-resolved ARPES under different pump-
probe conditions

Umberto De Giovannini<EMAIL_ADDRESS>Max Planck Institute for
the Structure and Dynamics of Matter and Center for Free Electron Laser
Science, 22761 Hamburg, Germany  IKERBASQUE, Basque Foundation for Science,
E-48011, Bilbao, Spain, and Nano-Bio Spectroscopy Group, Departamento de
Fisica de Materiales, Universidad del País Vasco UPV/EHU, 20018 San Sebastián,
Spain  Shunsuke A. Sato<EMAIL_ADDRESS>Center for Computational
Sciences, University of Tsukuba, Tsukuba 305-8577, Japan  Max Planck Institute
for the Structure and Dynamics of Matter and Center for Free Electron Laser
Science, 22761 Hamburg, Germany  Hannes Hübener<EMAIL_ADDRESS>Max
Planck Institute for the Structure and Dynamics of Matter and Center for Free
Electron Laser Science, 22761 Hamburg, Germany  Angel Rubio
<EMAIL_ADDRESS>Max Planck Institute for the Structure and Dynamics of
Matter and Center for Free Electron Laser Science, 22761 Hamburg, Germany
Center for Computational Quantum Physics (CCQ), The Flatiron Institute, 162
Fifth avenue, New York NY 10010.

###### Abstract

First-principles methods for time-resolved angular resolved photoelectron
spectroscopy play a pivotal role in providing interpretation and microscopic
understanding of the complex experimental data and in exploring novel
observables or observation conditions that may be achieved in future
experiments. Here we describe an efficient, reliable and scalable first-
principles method for tr-ARPES based on time-dependent density functional
theory including propagation and surface effects usually discarded in the
widely used many-body techniques based on computing the non-equilibrium
spectral function and discuss its application to a variety of pump-probe
conditions. We identify four conditions, depending on the length of the probe
relative to the excitation in the materials on the one hand and on the overlap
between pump and probe on the other hand. Within this paradigm different
examples of observables of time-resolved ARPES are discussed in view of the
newly developed and highly accurate time-resolved experimental spectroscopies.

##  I Introduction

Angular resolved photoelectron spectroscopy (ARPES) is a long standing well
established technique to observe the electronic energy dispersion in solids
and surfaces. Indeed, it is the standard technique for the electronic
structure of solids and the observed spectral functions are well understood
from a theoretical point of view in terms of quasiparticles and their
lifetimes, including manifestations of complex quasiparticle interactions
Damascelli  _et al._ (2003); Wang  _et al._ (2018). Like many other
spectroscopies, the possibility to perform time-resolved measurements has
opened new avenues to observe dynamical processes and today, time-resolved
(tr)-ARPES is a widely employed technique with a vast breadth of applications.
This raises new challenges for the theoretical description of the observed
dynamical effects as well as the simulation of the observation process itself.

Equilibrium ARPES is usually described within response theory, that captures
the processes around the excitation and emission of the photoelectron. On the
most basic level Fermi’s Golden Rule, often referred to as the one step model
Hüfner (2003); Damascelli (2004), describes the probability of producing a
photo-electron by the dipole matrix element of the material state and the
continuum. This can be refined by more sophisticated final states, modelling
the detector etc. Such a description, however, neglects dynamical effects that
occur in the photoemission process, such as the scattering of excited
electrons before they leave the material. This is attempted to be captured by
the so called three step model, which accounts for the excitation, transport
through the material, eventual emission and detection of the photoelectron,
which allows to phenomenologically include the effects of excitation of or
scattering with other material modes during the photo-hole creation process,
such as plasmons, phonons as well as electron-electron scattering. The more
rigorous description of many-body perturbation theory based on quantum field
theory, avoids the separation in steps as well as phenomenological assumptions
and has been very successful in describing the many-body interactions through
self-energies and their signatures in the recorded spectral functions.
However, for time-domain measurements, the equilibrium quasi-particle
approximation is not sufficient, because it does not account for the two-time
nature of electronic correlations and the fundamental changes a system can
undergo when it is excitedPerfetto and Stefanucci (2015).

The formulation of the time-resolved ARPES process with non-equilibrium
Green’s functionsStefanucci and van Leeuwen (2013) is considered as the most
comprehensive theoretical description. Recently, it has been approached even
as a first principles computational technique and demonstrated to be feasible
for a real materialSangalli (2021), while lattice model based approaches have
been implemented as well Schüler  _et al._ (2020). The non-equilibrium Greens
functions approach allows to compute the time-dependent spectral function of
materials, taking into account the complex many-body excitationPerfetto  _et
al._ (2020), de-excitation and decoherenceStefanucci and Perfetto (2021),
dynamical correlationDendzik  _et al._ (2020); Pavlyukh  _et al._ (2020),
excitations in strongly correlated systemsAoki  _et al._ (2014); Freericks
_et al._ (2009) and lifetime effects.

Figure 1:  Different pump-probe conditions considered in this review. We
distinguish the cases where pump (red line) and probe (blue lines) are either
overlapping or not. The pump creates an excitation (green line) in the
material. Depending on the relative time-scale between the probe envelope and
the period of the excitation, we further distinguish the cases of long and
short probes. The blue shaded areas indicate the time scales at which the
excitation is probed. Each of these four conditions allow the observation of
different phenomena.

In this article we will present another realistic and accurate approach for
the first-principles computation of time-resolved ARPES that is based on time-
dependent density functional theory (TDDFT) De Giovannini  _et al._ (2012,
2013); Crawford-Uranga  _et al._ (2014); De Giovannini  _et al._ (2017);
Wopperer  _et al._ (2017); Krečinić  _et al._ (2018); Sato  _et al._ (2018);
Hübener  _et al._ (2018); De Giovannini and Castro (2018); De Giovannini
(2018); De Giovannini  _et al._ (2020); Trabattoni  _et al._ (2020); Gatti
_et al._ (2020); Aeschlimann  _et al._ (2021). While in principle equivalent
in scope and accuracy for coherent excitations to the quasiparticle method,
TDDFT is limited by the available approximations to the complex exchange-
correlation functional, but has the advantage of computational efficiencyOnida
_et al._ (2002). Most applications of the Green’s function methods give the
quasiparticle spectral functions, whereas the method we discuss here
explicitly computes the photo-ionization current and constructs the ARPES
spectrum from its energy and momentum distribution, in a conceptual analogue
to the photoelectron detector. TDDFT, being a theory for the electronic
density, does not natively include electron-phonon coupling, however, it can
be coupled to the classical ionic motion of the lattice through Ehrenfest
molecular dynamics. This allows to describe the effects of coherent phonon
excitations on the tr-ARPES spectrum Hübener  _et al._ (2018). In such a
quantum-classical coupled system it is not possible to accurately describe the
exchange of energy between the lattice and electrons Parandekar and Tully
(2005, 2006); Alonso  _et al._ (2020), hence processes like thermalization and
decoherence can not be described in this approach. Nevertheless, decoherence
effects can be accounted for in TDDFT by phenomenological scattering times and
coupling to an density matrix Floss  _et al._ (2019), while the coupling of
quantum nuclear dynamics to a first-principles approach is under development
Albareda  _et al._ (2014, 2019); Abedi  _et al._ (0 09, 2013).

Here, we will discuss examples of observables of excited states in solids
accessed via time-resolved ARPES and their theoretical description and first-
principles simulation with TDDFT. To organise the examples we consider the
paradigmatic regimes of short and long probes applied during and after the
pump pulse, as sketched in Fig. 1. The length of the probe pulse is here to be
understood relative to the excited mode of the solid that is being created or
the frequency of the pump that is applied. Probing a system with a long probe
while the pump is applied allows the observation of Floquet states that have
received considerable recent attention, because they offer the possibility to
transiently alter the topology of a material Oka and Aoki (2009). We will
discuss how they are imprinted in the ARPES spectrum and issues and
limitations that arise for they experimental detection. While Floquet states
are usually associated with periodic driving fields, it is also possible to
apply Floquet theory to states of a solid after the pump, when a coherent
eigenmode of the material is dressing the electronic structure. This
possibility to create a field-free Floquet material, will be discussed
alongside its signatures in ARPES spectra which can be observed under a long
probe regime. By contrast, short probes allow to observe the electronic
structure as it follows the oscillation of the excitation mode or pump field.
In the latter case one can obtain streaking traces from solids, which gives
access to the intrinsic times with which electrons are ejected into the
continuum. In the time domain following the pump, the short probe regime
allows to observe the coupling to the electronic structure to elemental modes,
which we will show here for the example of electron-phonon coupling.

It is worth mentioning that here we do not discuss the most widely considered
observable of tr-ARPES, that is rise and decay times of excited state
populations, because it is well covered elsewhere and in the other
contributions to this special issue.

##  II Tr-ARPES with TDDFT

TDDFTRunge and Gross (1984); Marques  _et al._ (2011); Ullrich (2012) provides
a practical framework to treat quantum dynamics of many-electron systems out
of equilibrium. The theory is based on the Runge-Gross theorem that
establishes the one-to-one correspondence between the time dependent many-body
wavefunction and the corresponding time-dependent density, $n(t)$. From this
tenet, by employing the Kohn-Sham (KS) scheme, one can reformulate the time-
dependent problem of interacting electrons in terms of a fictitious non-
interacting system – the KS system – having the same density as the
interacting one at all times. In formulas this translates into a set of single
particle equations for each, doubly occupied, KS orbital, $\varphi_{i,{\bf
k}}({\bf r},t)$, representing $N$ electrons in the simulation cell, of the
form

$i\frac{\partial}{\partial t}\varphi_{i,{\bf k}}({\bf
r},t)=\Bigg{[}\frac{1}{2}\left(\hat{\bf
p}+\frac{1}{c}\bf{A}(t)\right)^{2}+V_{ion}({\bf r})\\\ +V_{H}[n]({\bf
r})+V_{xc}[n]({\bf r})\Bigg{]}\varphi_{i,{\bf k}}({\bf r},t)$ (1)

with

$n({\bf r},t)=\sum_{\bf k}^{\rm BZ}\sum_{i=1}^{N/2}|\varphi_{i,{\bf k}}({\bf
r},t)|^{2},$ (2)

where, $V_{ion}({\bf r})$ indicates the external potential generated by ions,
$V_{H}[n]({\bf r})$ is the Hartree potential, the electrostatic potential
generated by the charge density of the electrons, $V_{xc}[n]({\bf r})$ is the
exchange and correlation potential accounting for the many-body interaction,
and the square bracket is a customary notation indicating the functional
dependence on the density. For convenience we consider the integrals in
reciprocal space discretized over a grid of k-points covering the Brillouin
zone. The right hand side of Eq. (1) defines the KS Hamiltonian which we
denote with $\hat{H}_{\rm KS}$. The coupling with external electric fields is
expressed in the velocity gauge and in the dipole approximation, i.e. with a
spatially uniform vector potential ${\bf
A}(t)=-c\int_{-\infty}^{t}d\tau\,{E}(\tau)$. Here, we are concerned only with
a purely electric vector potential. To include magnetic fields, one would have
to employ the generalization of TDDFT to current-density functional theory.
Although, here we use the dipole approximation, the scheme we discuss is
generally valid and can be applied beyond the dipole approximation and deal
with arbitrary fields. Atomic units, $\hbar=m_{e}=e=1$, are used trough the
paper unless specified otherwise.

The time-dependent vector potential in Eq. (1) can represent any linear
combination of fields and naturally includes the case of two fields, pump and
probe, needed to perform tr-ARPES measurements. It must be noted that a
perturbative treatment of the problem becomes unfeasible to describe the
state-of-the-art experimental condition, where highly-nonlinear dynamics is
induced by strong fields. Direct integration approaches to Eq. (1), like the
propagation in real-time of the equations, remain the only practical option.

There are few options to extract the directly recorded tr-ARPES observable
from a real-time TDDFT calculation which contains more than the electronic
spectral function that is usually the result of other many-body approaches.
The first option is to extract the photoelectron angular distribution from the
flux of the ionization current through a surface with the t-SURFF method Tao
and Scrinzi (2012); Wopperer  _et al._ (2017); De Giovannini  _et al._ (2017).
This approach requires to account explicitly for the surface termination of
the material and to partition the spatial dimension perpendicular to the
surface, $z$, into an inner, $\Omega$, and an outer, $\bar{\Omega}$ region
like depicted in Fig. 2.

Figure 2:  Schematic representation of the continuum states used to represent
the photoelectrons away from the material. The assumption is made that beyond
a certain distance from the materials surface the states are well represented
by Volkov states.

This partitioning sets the stage for the approximation of the physical
division between the material surface and the photoelectron detector that
constitutes the basic ansatz of the approach. In this division electrons in
the inner region are fully interacting among each other, with the ions of the
crystal and with the external field while in the outer region they interact
only with the external field. Formally it means that the Hamiltonian of the
system is decomposed into the KS Hamiltonian in $\Omega$ and the Volkov
Hamiltonian in $\bar{\Omega}$ as following

$\hat{H}({\bf r},t)=\left\\{\begin{aligned} \hat{H}_{\rm KS}({\bf r},t)&\text{
if }{\bf r}\in\Omega\\\ \hat{H}_{\rm V}({\bf r},t)&\text{ if }{\bf
r}\in\bar{\Omega}\end{aligned}\right.\,,$ (3)

where the Volkov Hamiltonian, $\hat{H}_{\rm V}$, is the Hamiltonian governing
the dynamics of free electrons driven by an external homogeneous vector
potential ${\bf A(t)}$, and is defined as

$\hat{H}_{\rm V}({\bf r},t)=\frac{1}{2}\left(\hat{\bf p}+\frac{{\bf
A}(t)}{c}\right)^{2}\,.$ (4)

The time-dependent Schrödinger equation (TDSE) associated with the Volkov
Hamiltonian is solved by wavefunctions of the form

$\chi_{\bf p}({\bf r},t)=\frac{1}{(2\pi)^{\frac{3}{2}}}e^{i{\bf p}\cdot{\bf
r}}e^{-i\Phi({\bf p},t)}\,,$ (5)

with

$\Phi({\bf p},t)=\int_{0}^{t}{\rm d}\tau\frac{1}{2}\left({\bf p}+\frac{{{\bf
A}}(\tau)}{c}\right)^{2}\,,$ (6)

that are eigenstates of the momentum operator and form a complete set. This
property allows one to use them as detector states and extract the momentum
dependence of the KS orbitals in the continuum by projection

$\varphi_{i,{\bf k}}({\bf r},t)=\int{\rm d}{\bf p}\,b_{i,{\bf k}}({\bf
p},t)\chi_{\bf p}({\bf r},t)\,.$ (7)

The total momentum probability, measured in the experiments, is simply
obtained by summing up the squared modulus of the amplitude, $b_{i,{\bf
k}}({\bf p},t)$, over states and k-points,

$\mathcal{P}({\bf p},t)=\frac{2}{N}\sum_{\bf k}^{\rm
BZ}\sum_{i=1}^{N/2}|b_{i,{\bf k}}({\bf p},t)|^{2}\,.$ (8)

Using the continuity equation for the ionization current is then possible to
formulate an equation for the amplitude Wopperer  _et al._ (2017); De
Giovannini  _et al._ (2017) as a flux integral over the surface, $S$,
separating $\Omega$ and $\hat{\Omega}$ as,

$b_{i,{\bf k}}({\bf p},t)=-\int_{0}^{t}{\rm d}\tau\oint_{S}{\rm d}{\bf
s}\cdot\chi^{*}_{\bf p}({\bf r},\tau)\left\\{\hat{\bf p}+\frac{{\bf
A}(\tau)}{c}\right\\}\varphi_{i,{\bf k}}({\bf r},\tau)\,.$ (9)

This method provides a good estimate of ARPES matrix elements De Giovannini
_et al._ (2017). This is due to the fact that the approximation involved in
the Hamiltonian ansatz of Eq. (3) requires that the continuum states of the KS
Hamiltonian are well approximated by Volkov waves in the detector region
$\bar{\Omega}$. From Fig. 2 one can see that this approximation is mostly
affected by the tail of the surface potential extending into the vacuum and
that the error can be reduced simply by moving the surface $S$ further into
the vacuum. In practical calculations the dimension of the simulation box in
$z$ is determined by the position of $S$ and by the absorbing boundary
employed to prevent spurious reflections from the boundaries and therefore
correctly model the vacuum region. The spectrum of possible boundaries
conditions cover a wide range of alternatives going from simple complex
absorbing potentials De Giovannini  _et al._ (2015) up to exterior complex
scaling Scrinzi (2010) and sophisticated open boundary conditions Kaye  _et
al._ (2020).

A characteristic aspect of the semi-periodic boundary conditions employed in
this method is that the surface of the material must be modeled by a slab
geometry. This offers the possibility to study the electrons transport
dynamics explicitly naturally beyond the sudden approximation. Even though
photoemission essentially probe surface properties because of the small mean
free path of the photoelectrons in practical calculations one has to converge
with respect to the number of layers needed to reach the bulk limit with clear
implications in terms of computational costs. Still, many realistic
applications can be treated by this method De Giovannini  _et al._ (2016,
2017); Schüler  _et al._ (2020); Gatti  _et al._ (2020); Aeschlimann  _et al._
(2021).

In cases where the demand for accuracy is less stringent one can employ a
simpler approach that requires only to model the dynamics in the bulk without
the surface. This is the case for a method that can be derived by invoking the
strong field approximation Brabec and Krausz (2000) where only the time
evolution under the pump field is required explicitly and the effect of the
probe is considered at the level of the one-step model. We can call this
approach the time-dependent one-step model. In this approximation the
ionization amplitude for the $i$-th band can be written Sato  _et al._ (2020);
De Giovannini and Hübener (2020) as the time integral of the transition
amplitude between an initial time-dependent state (pump driven), and a
scattering state approximated by a Volkov wave resulting from the action of
the probe field, ${\bf A}_{pr}(t)=\bm{\epsilon}F(t)$. In a formula

$b_{i,{\bf k}}({\bf p})=-i\int_{\infty}dt\,\langle\chi_{\bf p}(t)|\hat{\bf
p}\cdot{\bf A}_{pr}(t)|\varphi_{i,{\bf k}}(t)\rangle\,,$ (10)

where the bra-ket notation indicates spatial integration over the unit cell.
This formula can be further simplified by using the fact that Volkov waves are
eigenstates of the momentum operator and therefore $\langle\chi_{\bf
p}(t)|\hat{\bf p}\cdot{\bf A}_{pr}(t)|\varphi_{i,{\bf k}}(t)\rangle={\bf
p}\cdot{\bf A}_{pr}(t)\langle\chi_{\bf p}(t)|\varphi_{i,{\bf k}}(t)\rangle$.
The ionization amplitude then becomes,

$b_{i,{\bf k}}({\bf p})=-i{\bf p}\cdot\bm{\epsilon}\sum_{j}\langle{\bf
p}|\varphi_{j,{\bf k}}\rangle\int_{\infty}dt\,e^{i\Phi({\bf
p},t)}F(t)c_{j,i,{\bf k}}(t)$ (11)

where the time-dependent KS orbital is expanded in the basis of the KS orbital
at equilibrium ($t=0$), $|\varphi_{i,{\bf k}}(t)\rangle=\sum_{j}c_{j,i,{\bf
k}}(t)|\varphi_{i,{\bf k}}(t=0)\rangle$ with coefficients $c_{j,i,{\bf
k}}(t)=\langle\varphi_{j,{\bf k}}|\varphi_{i,{\bf k}}(t)\rangle$. Note that
Eq. (11) reduce to Fermi’s golden rule in the limit where there is no pump and
the probe is monochromatic, according to the one-step theory of photoemission.

The advantage of this approach is immediately apparent from Eq. (11) since it
only requires the information of the time dependent projections from a
dynamical evolution of the KS orbitals. This is an easily accessible quantity
that can be available to any code capable to simulate the real-time dynamics
of a solid.

A limitation of this approach is that the photoemission matrix elements,
$M=\langle{\bf p}|\varphi_{j,{\bf k}}\rangle$, are calculated as an expansion
over plane waves, i.e. as a spatial Fourier transforms of the KS orbitals.
While this approach is certainly convenient from the numerical stand point it
delivers only qualitative results. This is because plane waves are low-level
approximations for the continuum states of the solid because of the presence
of crystal fields, as one can appreciate by looking at Fig 2. In order to
improve the quality one should use more accurate continuum states of the
material such as time-reversed low-energy electron diffraction (LEED) Hüfner
(2003) states that can be obtained with separate, static, calculations Pendry
and Hopkinson (1978).

It must be noted that basis expansion and final state approximations, like
done by taking Eq. (11) in first-order perturbation theory, can cause an
artificial gauge dependence that has to be carefully assessed in order to
attain predictive results from theory Foreman (2002); Schüler  _et al._
(2021). Even though Eq. (11) and Eq. (9) are defined using gauge-invariant
physical states, the Volkov states, theoretical predictions based on Eq. (9)
are more robust because they are defined in terms of the gauge-invariant
current operator instead of the dipole operator. Moreover the spectra obtained
with t-SURFF can be systematically converged by moving the the flux surface
$S$ further into the vacuum to improve the match between plane waves and
continuum states whereas the overlap integral in Eq. (11) can only be
improved, as discussed above, by changing the final state. Indeed t-SURFF has
been widely used in the strong field community Tao and Scrinzi (2012); Tulsky
and Bauer (2020) where gauge independence is crucial and applied, for
instance, to laser-induced electron diffraction Krečinić  _et al._ (2018);
Trabattoni  _et al._ (2020).

##  III Overlapping pump and probe

Here, we discuss the overlapping pump-prove regime, where pump and probe
pulses are (partially) overlapped. In this regime, it is on the one hand
possible to observe ultrafast excitation processes directly at their creation
with short (sub-cycle) probe pulses and on the other hand create dressed
states in the solids that emerge when the probe is longer than the pump
carriers.

###  III.1 Condition 1: Short-probe in the overlapping regime

Experiments where the probe pulse extension in time is of the order or smaller
than a single cycle of the pump carrier, c.f. Fig. 1, provide access to the
sub-cycle excitation dynamics in a material. Of particular interest for
excitations in solids is the attosecond time scale (1 as = $10^{-18}$ s) which
is the natural scale of electron-hole dynamics. Crucial for accessing this
time scale is the ability to generate isolated attosecond pulses Sansone  _et
al._ (2006) which also opens the door on the vast field of the research on
attosecond physics Krausz and Ivanov (2009).

In this regime tr-ARPES has been employed mainly for attosecond streaking
Itatani  _et al._ (2002). Attosecond streaking is a pump-probe technique in
which an XUV pulse creates a photoelecton wavepacket that is subsequently
streaked by a moderately strong and carrier-envelope phase (CEP) stabilized IR
field (typically of the order $I_{IR}\approx 10^{11}$ W/cm2) and by this means
encode a time information in the velocity spectrum of the photoelectrons. By
carefully analysing the spectrogram obtained from the expansion of the
photoelectron momentum distribution as a function of the time-delay it is
possible to recover various contributions. Most notably the Eisenbud-Wigner-
Smith (EWS) time delay of photoemission which defines the time that is takes
for electrons to be released into the continuum during an ionization process.

The working principle Kienberger  _et al._ (2004) is based on the fact that
the electron momentum at the detector, ${\bf p}_{f}$, is constituted by the
momentum with which the electron reaches the continuum, ${\bf p}_{0}$, shifted
by the value of the pump field at the precise moment in time in which it get
released, $t_{0}$, as

${\bf p}_{f}={\bf p}_{0}-{\bf A}_{IR}(t_{0})/c\,.$ (12)

The release time, $t_{0}$, is the observable that is directly measured albeit,
in many cases, only as a quantity relative to other ionization channels. It
can be thought as composed of the pump-probe delay, $\tau$, plus a generic
time shift, $t_{S}$: $t_{0}=\tau+t_{S}$. The time shift is composed of a
number of contributions originating from different sources such as atto-chirp,
Coulomb tail or lattice scattering, etc. depending on the details of the
experiment including the EWS delay.

Attosecond streaking is considered one of the cornerstone of attosecond
chronoscopy Pazourek  _et al._ (2015); Seiffert  _et al._ (2017) with ample
breadth of application that ranges from the first experiment on neon atoms
Schultze  _et al._ (2010) to molecules Vos  _et al._ (2018); Biswas  _et al._
(2020) and clusters Seiffert  _et al._ (2017). In solids it was first employed
on Tungsten where $t_{S}$ $\approx 100$ as delay in the emission between
localized core states and conduction band states was observed Cavalieri  _et
al._ (2007); Ossiander  _et al._ (2018). In Magnesium it was employed to
investigate the screening in real-time Neppl  _et al._ (2012, 2015) and to
uncover the dependence on the initial state angular momentum in WSe2 van der
Waals crystals Siek  _et al._ (2017).

###  III.2 Condition 2: Long-probe in the overlapping regime

When the probe is overlapping in time with a considerable portion of the pump
it is possible to create a situation where resulting ARPES spectrum shows a
quasiparticle spectrum that is not only determined by the intrinsic properties
of the solid, but shows the spectrum of the pump-dressed solid. This has
gained some recent attention, because such dressed states can have different
properties, especially in terms of topology. In the limit of a constant pump
envelope, such states, as well as their ARPES spectrum, can be described by
Floquet theorySambe (1973); Sentef  _et al._ (2015).

The Floquet theorem states that a time-dependent Schrödinger equation
$i\frac{d}{dt}\phi^{F}_{\alpha}(t)=H(t)\phi^{F}_{\alpha}(t)$ with a time-
periodic Hamiltonian ($H(t)=H(t+T)$), can be satisfied with the following form
of the wavefunction, the Floquet states,

$\phi_{\alpha}^{F}(t)=e^{-iE_{\alpha}t}u_{\alpha}(t),$ (13)

where $u_{\alpha}(t)$ are the time-periodic function as
$u_{\alpha}\left(t+T\right)=u_{\alpha}(t)$. Hence, one can expand the periodic
part of the Floquet states as

$u_{\alpha}(t)=\sum_{m=-\infty}^{\infty}e^{im\Omega t}u^{\alpha}_{m},$ (14)

where $\Omega$ is the fundamental frequency $\Omega=2\pi/T$ of the applied
laser. Furthermore, inserting Eqs. (13) and (14) into the original Schrödinger
euation, one can obtain the following eigenvalue equation

$E_{\alpha}u^{\alpha}_{n}=\sum_{m}\mathcal{H}_{nm}u^{\alpha}_{m},$ (15)

where the Floquet Hamiltonian $\mathcal{H}_{nm}$ is given by

$\mathcal{H}_{nm}=\frac{1}{T}\int_{T}dtH(t)e^{i(m-n)\Omega
t}+m\Omega\delta_{mn}.$ (16)

Thus Floquet theory maps the problem of solving a differential equation in the
time into a static eigenvalue equation in the energy domain, by means of the
discrete Fourier expansion of Eq. (16). Any solution of the time-dependent
Schrödinger equation can then be constructed as a linear combination of the
Floquet states as $\phi(t)=\sum_{\alpha}f_{\alpha}\phi^{F}_{\alpha}(t)$, where
the coefficients $f_{\alpha}$ depend on the boundary conditions.

This expansion of the a driven quantum mechanical system is relevant for tr-
ARPES in two ways: (i) because under these driving conditions ARPES records
the spectrum of the Floquet Hamiltonian, $E_{\alpha}$ instead of the bare band
energiesSentef  _et al._ (2015); Kalthoff  _et al._ (2018) and (ii) the
intensity of the ARPES spectrum depends on the expansion coefficients
$f_{\alpha}$. By analysing the photoemission matrix element, c.f. Eq. (18), in
terms of the Floquet expansion the photoemission probability amplitude readsDe
Giovannini and Hübener (2020)

$\displaystyle P({\bf p})=$
$\displaystyle\sum_{\alpha}\sum_{n}|f_{\alpha}|^{2}|u_{\alpha}^{n}({\bf
p})|^{2}({\bf p}\cdot{\bf A}^{0}_{pr})^{2}$ $\displaystyle\delta({\bf
p}^{2}/2-E_{\alpha}+n\Omega-\omega).$ (17)

This expression shows that the kinetic energy of the photoelectrons depends on
the new, Floquet-eigenvalue $E_{\alpha}$ and moreover, that the spectrum shows
this energy repeated at integer intervals of $n\Omega$. These are the Floquet
sidebands, whose intensity depends on the norm of the harmonic component
$u^{\alpha}_{n}$. The overall intensity of such a series of $E_{\alpha}$
sidebands is governed by the Floquet expansion coefficient $f_{\alpha}$, that
depends on how much the dynamics of the system is described by the Floquet
state $\psi^{\alpha}$. As such Eq. (III.2) not only shows how an ARPES
spectrum of a continuously driven system can be analysed, it also illustrates
that ARPES is a natural observable of a Floquet electronic structure De
Giovannini  _et al._ (2016). This last point implies that many theoretical
proposals relying on the formation of Floquet states, especially for
topological systems, can, or rather should, be verified with ARPES experiments
Schüler  _et al._ (2020a).

The observation of Floquet electronic structure, is however, not as
straightforward as Eq. (III.2) suggests. In the above derivation, Floquet
states are derived with an effective single-particle Hamiltonian without a
significant contribution from other degrees of freedom. On the contrary, in
real systems, an electron is not an independent particle but interacts with
other degree of freedom such as phonons, defects and other electrons. As a
result, the formation of single-particle Floquet states is disturbed by the
surrounding environment, and signals from the Floquet bands are suppressed
Schüler  _et al._ (2020b); Sato  _et al._ (2020); Aeschlimann  _et al._
(2021). From the viewpoint of many-body systems, in principle, one needs to
consider not only electrons but also their surrounding environment in the
framework of the Floquet theory in order to accurately describe dressed
matter. If a single-particle degree of freedom is sufficiently isolated from
the other degrees of freedom, a single-particle Floquet feature can be
observed in real experiments. Indeed, this mechanism has been observed in
experiments on BiSe2 Wang  _et al._ (2013); Mahmood  _et al._ (2016) as an
avoided crossing in ARPES sidebands.

So far, we discussed how electronic states in matter are dressed by light and
how their properties are recorded in the tr-ARPES with the Floquet theory.
These Floquet states are the initial states of the photoemission process
induced via the probe pulse, and the corresponding final states (detector
states) of the tr-ARPES simulation are the Volkov states as described in Sec.
II. Importantly, under a continuous-wave driving, these Volkov states can be
also seen as the corresponding Floquet states. As a result, the observed tr-
ARPES signals may contain additional side-band contributions from the dressed
free-electron states; Volkov states. This effect is known as laser-assisted
photoemission effect (LAPE) Park (2014); Mahmood  _et al._ (2016). This side-
band formation due to the photo-dressed free-electron states play an essential
role in the reconstruction of attosecond beating by interference of two-photon
transitions (RABBIT) technique Paul  _et al._ (2001); Klünder  _et al._ (1
04). RABBIT is a technique that allows to recover the phase of the ionized
electron wavepacket and the delay in photoemission. It can be view as
technique complementary to streaking. In solid is was applied to Nickel Tao
_et al._ (2016) and Tungsten Heinrich  _et al._ (2021) crystals.

##  IV Non-Overlapping pump and probe

Here, we discuss a regime, where pump and probe pulses are sufficiently
separated in the time-domain. In this regime one probes only the excitation
created by the pump, rather than its build up or driven states. Depending on
the relative time-scales of time-resolution and decay time one can either
observe how the excitation is dissipated through the solid or one can measure
dynamics of the excitation itself.

###  IV.1 Condition 3: Short-probe in the non-overlapping regime

In this regime tr-ARPES can be used to probe excitations and eigenmodes of
solids on their characteristic time scales, provided the delay resolution is
fast enough to resolve the internal dynamics. In the following we will focus
on the case where the pump has excited a coherent phonon and will analyse how
in this condition tr-ARPES can give access to electron phonon coupling.

Figure 3:  (a) Illustration of the FD-ARPES method. Under non-equilibrium
conditions each point in an ARPES map acquires a time dependence that can be
analyzed by Fourier transform. Selecting a particular Fourier component for
all points allows the construction of the FD-ARPES map, that gives and energy
and momentum resolved view of the couplign of the electronic structure to a
mode with that particular frequency. (b) Computed equilibirum (upper panel)
and FD-ARPES (lower panel) for Graphene the frequency of the E${}_{2}g$ phonon
mode, which has been coherently excited (adapted from De Giovannini  _et al._
(2020)).

The lattice displacement associated with a coherent phonon induces, to first
order, a shift in the electronic band energies depending on the the strength
of the electron-phonon coupling. This can be observed in tr-ARPES as an
oscillation of the spectral function at a given $k$-point and by fitting this
movement in energy on can extract the electron phonon couplingRettig  _et al._
(2015); Gerber  _et al._ (2017). Alternatively one can perform a Fourier
transform of the time-series obtained by tr-ARPES for each point in the
energy-momentum map and reconstruct the ARPES map at a given frequencyHein
_et al._ (2020); Suzuki  _et al._ (2021); De Giovannini  _et al._ (2020), c.f.
Fig. 3(a). This latter option, Frequency-domain (FD)-ARPES, does not only
provide a novel way of presenting the large amount of data collected in tr-
ARPES measurements with novel high-resolution detectors, but it also presents
the opportunity of processing the data differently, as we will discuss now.

To analyze the FD-ARPES signal based on the microscopic theory, we start from
the Fermi’s Golden Rule expression for the photoemission intensity at a given
$k$-point and originating from a given band orbital $\psi$ with energy
$\epsilon$

$I_{i{\bf k}}(E_{\rm kin})=|\langle f_{\bf p}|{\bf A}\cdot\hat{\bf
p}|\psi_{i{\bf k}}\rangle|^{2}F(\Omega+\epsilon_{i\mathbf{k}}-E_{\rm kin})$
(18)

where $E_{\rm kin}=p^{2}/2$ is the kinetic energy of the photoelectron,
$f_{\bf p}$ is a final state with momentum $\mathbf{p}$, $F$ is the spectral
lineshape and $\Omega$ is the energy of the probe. We now make the assumption
that the lattice excitation is a coherent phonon or contains a substantial
coherent component, so that the ionic motion can be described by a single
classical trajectory. Assuming a sinusoidal for the displacement of the
lattice due to the coherent phonon generation,
$u(\tau)=u_{0}\sin{\omega_{0}\tau}$ with the maximum lattice displacement
$u_{0}$ and the phonon frequency $\omega_{0}$, we can account for the effect
of the adiabatic coupling to coherent lattice motion by introducing a
parametric dependence of the band energy and orbital on the lattice
displacement $u$ through ordinary perturbation theory:

$\displaystyle\epsilon_{i\mathbf{k}}[u(\tau)]$
$\displaystyle=\epsilon_{i\mathbf{k}}+\Delta_{i{\bf k}}\sin{(\omega_{0}\tau)}$
(19) $\displaystyle|\psi_{i\mathbf{k}}[u(\tau)]\rangle$
$\displaystyle=|\psi_{i\mathbf{k}}\rangle+|\delta\psi_{i\mathbf{k}}\rangle\sin{(\omega_{0}\tau)}$
(20)

where $\Delta_{i{\bf k}}=u_{0}\langle\psi_{i\mathbf{k}}|\delta
V|\psi_{i\mathbf{k}}\rangle$ is the change in orbital energy at the maximum
displacement $u_{0}$ of the lattice, and
$g_{ii}(\mathbf{k})=\langle\psi_{i\mathbf{k}}|\delta
V|\psi_{i\mathbf{k}}\rangle$ is the diagonal element of the standard electron-
phonon coupling matrix Giustino (2017), while the term
$|\delta\psi_{i\mathbf{k}}\rangle=u_{0}\sum_{i\neq j}\frac{g_{ij}({\bf
k})}{\epsilon_{i\mathbf{k}}-\epsilon_{j\mathbf{k}}}|\psi_{j\mathbf{k}}\rangle$
depends on the interband electron-phonon coupling. Inserting these expansions
into the Fermi’s Golden Rule expression, Eq. (18), gives a model for the tr-
ARPES intensity of an adiabatically coupled coherent phonon:

$I_{i{\bf k}}(E_{\rm kin},\tau)=|\langle f_{\bf p}|{\bf A}\cdot\hat{\bf
p}|\psi_{i{\bf
k}}[u(\tau)]\rangle|^{2}F(\Omega+\epsilon_{i\mathbf{k}}[u(\tau)]-E_{\rm kin})$
(21)

and the FD-ARPES map is obtained by Fourier transforming with respect to
$\tau$. It is important to note, that despite the linear expansion of the band
properties, this expression is clearly non-linear in the lattice displacement.
Since the coupling is adiabatic, the Fourier transform can only have
components at the frequency of the phonon and its harmonics. For the
fundamental frequency this gives

$\displaystyle\tilde{I}_{i{\bf k}}(E_{\rm kin},\omega_{0})=$
$\displaystyle\frac{1}{2\Delta}M\tilde{J}_{1}\bigg{(}\frac{E}{\Delta}\bigg{)}*F(E)+$
$\displaystyle\frac{i}{2\Delta}\delta
M\left[\tilde{J}_{0}\bigg{(}\frac{E}{\Delta}\bigg{)}+\frac{3}{2}\tilde{J}_{2}\bigg{(}\frac{E}{\Delta}\bigg{)}\right]*F(E)$
(22)

where $\tilde{J}_{n}$ are Fourier transforms of Bessel functions, $*$ denotes
the convolution product, $\delta M=Re[\langle\psi_{i{\bf k}}|{\bf
A}\cdot\hat{\bf p}|f_{\bf p}\rangle\langle f_{\bf p}|{\bf A}\cdot\hat{\bf
p}|\delta\psi_{i{\bf k}}\rangle]$ and we have used the shorthand
$E=\Omega+\epsilon_{i\mathbf{k}}+E_{\rm kin}$.

The expression in Eq. (22) gives the FD-ARPES map at the phonon-frequency for
adiabatic electron-phonon coupling and an example for such a spectrum is given
in Fig. 3(b), showing the FD-APRES spectrum for Graphene at the frequency of
the coherently excited E${}_{2}g$ phonon mode. Generally, FD-ARPES spectra can
be used to disentangle a large number of processes linked to the electron-
phonon coupling that affect the ARPES spectrum. First of all, we note that the
expression in Eq. (22) is purely imaginary, reflecting the assumption of the
adiabatic electron dynamics and the form of the lattice displacement,
$u(\tau)=u_{0}\sin{\omega_{0}\tau}$. The complex phase is determined by the
phase of the time dependence in Eqs. (19-20) and is therefore somewhat
arbitrary. However, if the measurements detects another phonon mode at a
different $\omega_{0}$ the relative phase of the FD-ARPEES maps can reveal
different excitation mechanism for the two coherent modes, i.e. a displasive
vs. an impulsive Raman process. However, maybe more telling can be the absence
of a unique complex phase across an FD-ARPES map. In this case localised
deviations of the complex phase directly signal regions in the Brillouin zone
where the electron-phonon coupling is not adiabatic, pointing to underlying
resonances and points where the electrons and phonons participate in other
excitations. Secondly, the FD-ARPES expression of Eq. (22) provides a way to
distinguish the type of electron phonon coupling. We note that the first term
has odd symmetry as a function of energy and depends only on $\Delta$ while
the second term even symmetry and contains $\delta M$. This means that if an
FD-ARPES map is recorded that features lineshapes of purely odd symmetry, all
the underlying electron-phonon coupling is provided by the diagonal coupling
matrix elements $g_{ii}(\mathbf{k})$. Conversely, a deviation from the odd
symmetry means that $|\delta\psi_{i\mathbf{k}}\rangle$ contribute to the FD-
ARPES signal, meaning that band-orbitals are affected by the electron-phonon
coupling and that off-diagonal coupling matrix elements $g_{ij}(\mathbf{k})$
are involved. Finally, we have shown in Ref. De Giovannini  _et al._ (2020)
that using a perturbative expansion in terms of small lattice distortions of
small coupling, one can extract the diagonal matrix elements
$g_{ii}(\mathbf{k})$ from FD-ARPES data, thus making the matrix element and
observable of this spectroscopy.

We note that a necessary condition for FD-ARPES is that the underlying tr-
ARPES measurement is able to resolve dynamics on the the time-scale of the
phonon frequency. Hence, it falls in the short probe category, where short is
relative to a previously excited mode. Next, we will turn to the opposite
case, where the probe is longer than the period of the excited mode.

###  IV.2 Condition 4: Long-probe in the non-overlapping regime

In this regime the probe itself does not resolve any dynamics on the time
scale of the of the excitation. However, it neither results in a mere average
of the signal. Instead, the correct picture to describe this regime is the
Floquet expansion, despite the fact that there is no pump anymore. We will
illustrate this paradigm again with the example of a coherent phonon
excitation.

We noted section III.2 that when the probe is longer than the pump duration it
may record the Floquet spectrum of a material, because the electronic levels
appear as dressed by the photons to the probe. The same picture applies in the
absence of a pump, when a coherent phonon has been excited in the system. In
this case the Hamiltonian is periodic in time, $H(t)=H(t+T)$ where the
periodicity now results from the oscillating lattice potential instead of an
external field.

To see how the resulting Floquet features depend on the material properties it
is instructive to write the time-dependent electronic Hamiltonian coupled to a
coherent phonon mode $\omega_{\nu}$ at a given $k$-point as

$H_{\mathbf{k}\nu}(t)=\epsilon_{n\mathbf{k}}c^{\dagger}_{n\mathbf{k}}c^{\dagger}_{n\mathbf{k}}+\sum_{mn}g_{mn\nu}(\mathbf{k})c^{\dagger}_{m\mathbf{k}}c^{\dagger}_{n\mathbf{k}}\mathbf{u}_{\nu}\sin(\omega_{\nu}t).$
(23)

where $u_{\nu}$ is the amplitude of the coherent lattice motion along the
phonon eigenvector and $g$ is again the electron-phonon matrix element.
Optically excited coherent phonons are typically zone center modes, hence here
we have additionally assumed that the phonon carry no moment, i.e. $q=0$. This
formulation now shows that on the one hand the amplitude $u$ of the lattice
motion takes the role of the laser intensity for the Floquet states and on the
other hand the electron-phonon matrix elements $g$ that of the optical dipole
matrix elements. This means that Floquet-phonon features in ARPES depend
directly on the single band electron-phonon matrix element, which is somewhat
analogous to the above example of the FD-ARPES case. Indeed, one can view an
ARPES measurement of the Floquet-phonon case as the limit of the FD-ARPES
case, where the probe time is very long, giving a static, rather than a time-
resolved result. Fig. 4 shows an example of a computed ARPES spectrum in the
Floquet-phonon regime, where the momentum and energy dependence of the the
sideband features are clearly follows that of the electron-phonon matrix
elements.

Figure 4:  (a) Computed ARPES spectrum of Graphene with the E${}_{2}g$ mode
under Floquet-phonon conditions (adapted from Hübener  _et al._ (2018)). (b)
Electron-phonon matrix elements of the E${}_{2}g$ mode of Graphene (adapted
from De Giovannini  _et al._ (2020)). Comparison between the panels shows that
the number of visible sideband broadly tracks the strength of the electron-
phonon coupling. Note, that the ARPES result also contains photoelectron
matrix elements that suppress some bands more than others, leading to some
deviations from this interpretation.

Finally, we comment on the similarity between Floquet satellites and other
satellite or sideband features that are ubiquitous in many experimental ARPES
spectraDamascelli  _et al._ (2003); Sobota  _et al._ (2021). Strong coupling
between the electronic structure and quasiparticle eigenmodes, such as plasmon
or indeed phonons, can lead to sidebands in the ARPES of the equilibrium
material, when the creation of the hole in the photoemission process also
results in the excitation of a quasiparticle eigenmode of the solid and hence
to a reduced energy of the photoelectron. While this phenomenology is very
similar to that of the Floquet, it results from a very different physical
situation: Floquet-ARPES probes an excited solid while the sidebands observed
in equilibrium result from excitations due to the probing process itself. The
two processes can be distinguished however, because in the equilibrium solid
sidebands mostly occur below the main band, because the photoelectron has lost
energy. In Floquet-ARPES by contrast, the already active eigenmode can supply
the photoelectron with additional energy and hence sidebands occur
symmetrically above and below the main peak.

##  V Outlook

Here we have sketched an overview of the developments we have carried out over
the last years to develop a reliable, efficient and widely applicable
theoretical framework to address all kind of pump-probe conditions and their
respective observables. This is by no means attempting at being comprehensive
as many particular conditions and regimes have been omitted. A major point of
interest in tr-ARPES measurements is the observation of dynamical
correlationGatti  _et al._ (2020), quasiparticle dynamics, coupling
(decoherence and dissipation effects) and dressing of quasiparticles.
Furthermore, the discussion here has been largely concerned with single photon
processes (with the exception of the condition 1, the standard Floquet case).
However, in tr-ARPES the possibility to create two (pump+probe) or multiple
photon pathways that can interfere and thus give a different kind of
characteristic spectrum is also possible and widely employed. The theoretical
tool described here, includes such processes out-of-the-box and remains to be
explored. Another yet to be explored field is the systematic employment of the
FD-ARPES method to eigenmode excitations other than phonons. For instance
plasmon or magnon coupling should lend itself to be systematically
characterised by this approach, as well as other collective modes such as the
charge-density wave transitions or excitons in the exciton insulator phase.
Furthermore, FD-ARPES might be employed to monitor the electron-phonon
coupling under non-equilibrium conditions, thus possibly giving insight into
phenomena such as light-induced superconductivity. One further prospect
(related to streaking and RABBIT) could be to study how exciton are formed
during and get further observations on the ”birth of and exciton” Voorhis
(2015) or light induced topological phases of matter, for instance by
monitoring Weyl formationHübener  _et al._ (2017) and dynamics, among others.
Recent success in tr-ARPES experiment investigating the decay dynamics of
excitons in TMD Madéo  _et al._ (2020); Dong  _et al._ (2021) suggests that
pursuing this route could be feasible.

##  VI Acknowledgment

This work was supported by the European Research Council (ERC-2015-AdG694097),
the Cluster of Excellence ’CUI: Advanced Imaging of Matter’ of the Deutsche
Forschungsgemeinschaft (DFG) - EXC 2056 - project ID 390715994, Grupos
Consolidados (IT1249-19), partially by the Federal Ministry of Education and
Research Grant RouTe-13N14839, the DFG – SFB-925 – project 170620586, and JSPS
KAKENHI Grants No. JP20K14382. The Flatiron Institute is a division of the
Simons Foundation.

## References

  * Damascelli  _et al._ (2003) A. Damascelli, Z. Hussain, and Z.-X. Shen, Reviews of Modern Physics 75, 473 (2003).
  * Wang  _et al._ (2018) Y. Wang, M. Claassen, C. D. Pemmaraju, C. Jia, B. Moritz, and T. P. Devereaux, Nature Reviews Materials 3, 312 (2018).
  * Hüfner (2003) S. Hüfner, Advanced Texts in Physics , 575 (2003).
  * Damascelli (2004) A. Damascelli, Physica Scripta T109, 61 (2004), cond-mat/0307085 .
  * Perfetto and Stefanucci (2015) E. Perfetto and G. Stefanucci, Phys. Rev. A 91, 033416 (2015).
  * Stefanucci and van Leeuwen (2013) G. Stefanucci and R. van Leeuwen,  _Nonequilibrium Many-Body Theory of Quantum Systems_ (Cambridge University Press, 2013).
  * Sangalli (2021) D. Sangalli, Physical Review Materials 5, 083803 EP (2021).
  * Schüler  _et al._ (2020) M. Schüler, D. Golež, Y. Murakami, N. Bittner, A. Herrmann, H. U. Strand, P. Werner, and M. Eckstein, Computer Physics Communications 257, 107484 (2020).
  * Perfetto  _et al._ (2020) E. Perfetto, S. Bianchi, and G. Stefanucci, Physical Review B 101, 041201 (2020).
  * Stefanucci and Perfetto (2021) G. Stefanucci and E. Perfetto, Physical Review B 103, 245103 (2021).
  * Dendzik  _et al._ (2020) M. Dendzik, R. P. Xian, E. Perfetto, D. Sangalli, D. Kutnyakhov, S. Dong, S. Beaulieu, T. Pincelli, F. Pressacco, D. Curcio, S. Y. Agustsson, M. Heber, J. Hauer, W. Wurth, G. Brenner, Y. Acremann, P. Hofmann, M. Wolf, A. Marini, G. Stefanucci, L. Rettig, and R. Ernstorfer, Physical Review Letters 125, 096401 (2020).
  * Pavlyukh  _et al._ (2020) Y. Pavlyukh, G. Stefanucci, and R. van Leeuwen, Physical Review B 102, 045121 EP (2020).
  * Aoki  _et al._ (2014) H. Aoki, N. Tsuji, M. Eckstein, M. Kollar, T. Oka, and P. Werner, Reviews Of Modern Physics 86, 779 (2014).
  * Freericks  _et al._ (2009) J. K. Freericks, H. R. Krishnamurthy, and T. Pruschke, Physical Review Letters 102, 136401 (2009).
  * De Giovannini  _et al._ (2012) U. De Giovannini, D. Varsano, M. A. L. Marques, H. Appel, E. K. U. Gross, and A. Rubio, Phys. Rev. A 85, 062515 (2012).
  * De Giovannini  _et al._ (2013) U. De Giovannini, G. Brunetto, G. Brunetto, A. Castro, J. Walkenhorst, J. Walkenhorst, and A. Rubio, Chemphyschem 14, 1363 (2013).
  * Crawford-Uranga  _et al._ (2014) A. Crawford-Uranga, U. De Giovannini, D. J. Mowbray, S. Kurth, and A. Rubio, Journal of Physics B: Atomic, Molecular and Optical Physics 47, 124018 (2014).
  * De Giovannini  _et al._ (2017) U. De Giovannini, H. Hübener, and A. Rubio, J. Chem. Theory Comput. 13, 265 (2017).
  * Wopperer  _et al._ (2017) P. Wopperer, U. De Giovannini, and A. Rubio, The European Physical Journal B 90, 1307 (2017).
  * Krečinić  _et al._ (2018) F. Krečinić, P. Wopperer, B. Frusteri, F. Brauße, J.-G. Brisset, U. De Giovannini, A. Rubio, A. Rouzée, and M. J. J. Vrakking, Physical Review A 98, 041401 (2018).
  * Sato  _et al._ (2018) S. A. Sato, H. Hübener, A. Rubio, and U. De Giovannini, Eur. Phys. J. B 91, 126 (2018).
  * Hübener  _et al._ (2018) H. Hübener, U. De Giovannini, and A. Rubio, Nano Lett. 18, 1535 (2018).
  * De Giovannini and Castro (2018) U. De Giovannini and A. Castro, in  _Attosecond Molecular Dynamics_ (The Royal Society of Chemistry, 2018) pp. 424–461.
  * De Giovannini (2018) U. De Giovannini, “Pump-probe photoelectron spectra,” in  _Handbook of Materials Modeling : Methods: Theory and Modeling_, edited by W. Andreoni and S. Yip (Springer International Publishing, Cham, 2018) pp. 1–19.
  * De Giovannini  _et al._ (2020) U. De Giovannini, H. Hübener, S. A. Sato, and A. Rubio, Physical Review Letters 125, 136401 (2020).
  * Trabattoni  _et al._ (2020) A. Trabattoni, J. Wiese, U. De Giovannini, J.-F. Olivieri, T. Mullins, J. Onvlee, S.-K. Son, B. Frusteri, A. Rubio, S. Trippel, and J. Küpper, Nature Communications 11, 2546 (2020).
  * Gatti  _et al._ (2020) G. Gatti, A. Crepaldi, M. Puppin, N. Tancogne-Dejean, L. Xian, U. De Giovannini, S. Roth, S. Polishchuk, P. Bugnon, A. Magrez, H. Berger, F. Frassetto, L. Poletto, L. Moreschini, S. Moser, A. Bostwick, E. Rotenberg, A. Rubio, M. Chergui, and M. Grioni, Physical Review Letters 125, 076401 (2020).
  * Aeschlimann  _et al._ (2021) S. Aeschlimann, S. A. Sato, R. Krause, M. Chávez-Cervantes, U. De Giovannini, H. Hübener, S. Forti, C. Coletti, K. Hanff, K. Rossnagel, A. Rubio, and I. Gierz, Nano Letters (2021), 10.1021/acs.nanolett.1c00801.
  * Onida  _et al._ (2002) G. Onida, L. Reining, and A. Rubio, Reviews Of Modern Physics 74, 601 (2002).
  * Parandekar and Tully (2005) P. V. Parandekar and J. C. Tully, The Journal of Chemical Physics 122, 094102 (2005).
  * Parandekar and Tully (2006) P. V. Parandekar and J. C. Tully, Journal of Chemical Theory and Computation 2, 229 (2006).
  * Alonso  _et al._ (2020) J. L. Alonso, C. Bouthelier, A. Castro, J. Clemente-Gallardo, and J. A. Jover-Galtier, Physical Review E 102, 042118 (2020), 2004.01986 .
  * Floss  _et al._ (2019) I. Floss, C. Lemell, K. Yabana, and J. Burgdörfer, Phys. Rev. B 99, 224301 (2019).
  * Albareda  _et al._ (2014) G. Albareda, H. Appel, I. Franco, A. Abedi, and A. Rubio, Phys. Rev. Lett. 113, 083003 (2014).
  * Albareda  _et al._ (2019) G. Albareda, A. Kelly, and A. Rubio, Phys. Rev. Materials 3, 023803 (2019).
  * Abedi  _et al._ (0 09) A. Abedi, N. T. Maitra, and E. K. U. Gross, Physical Review Letters 105, 123002 (2010-09).
  * Abedi  _et al._ (2013) A. Abedi, F. Agostini, Y. Suzuki, and E. K. U. Gross, Physical Review Letters 110, 263001 (2013).
  * Oka and Aoki (2009) T. Oka and H. Aoki, Phys. Rev. B 79, 081406 (2009).
  * Runge and Gross (1984) E. Runge and E. K. U. Gross, Phys. Rev. Lett. 52, 997 (1984).
  * Marques  _et al._ (2011) M. A. L. Marques, N. T. Maitra, F. Nogueira, E. K. U. Gross, and A. Rubio,  _Fundamentals of Time-Dependent Density Functional Theory_ (Springer-Verlag, 2011).
  * Ullrich (2012) C. A. Ullrich,  _Time-Dependent Density-Functional Theory_ , Oxford University Press (Oxford University Press, 2012).
  * Tao and Scrinzi (2012) L. Tao and A. Scrinzi, New Journal of Physics 14, 013021 (2012).
  * De Giovannini  _et al._ (2015) U. De Giovannini, A. H. Larsen, A. Rubio, and A. Rubio, The European Physical Journal B 88, 1 (2015).
  * Scrinzi (2010) A. Scrinzi, Physical Review A 81, 053845 (2010).
  * Kaye  _et al._ (2020) J. Kaye, A. Barnett, and L. Greengard, arXiv:2001.06113v1 (2020).
  * De Giovannini  _et al._ (2016) U. De Giovannini, H. Hübener, and A. Rubio, Nano Lett. 16, 7993 (2016).
  * Schüler  _et al._ (2020) M. Schüler, U. De Giovannini, H. Hübener, A. Rubio, M. A. Sentef, and P. Werner, Science Advances 6, eaay2730 (2020).
  * Brabec and Krausz (2000) T. Brabec and F. Krausz, Reviews Of Modern Physics 72, 545 (2000).
  * Sato  _et al._ (2020) S. A. Sato, U. De Giovannini, S. Aeschlimann, I. Gierz, H. Hübener, and A. Rubio, Journal of Physics B: Atomic, Molecular and Optical Physics 53, 225601 (2020).
  * De Giovannini and Hübener (2020) U. De Giovannini and H. Hübener, Journal of Physics: Materials 3, 012001 (2020).
  * Pendry and Hopkinson (1978) J. B. Pendry and J. F. L. Hopkinson, Le Journal de Physique Colloques 39, C4 (1978).
  * Foreman (2002) B. A. Foreman, Physical Review B 66, 165212 (2002), cond-mat/0204456 .
  * Schüler  _et al._ (2021) M. Schüler, J. A. Marks, Y. Murakami, C. Jia, and T. P. Devereaux, arXiv (2021), 2101.01143 .
  * Tulsky and Bauer (2020) V. Tulsky and D. Bauer, Computer Physics Communications 251, 107098 (2020), 1907.08595 .
  * Sansone  _et al._ (2006) G. Sansone, E. Benedetti, F. Calegari, C. Vozzi, L. Avaldi, R. Flammini, L. Poletto, P. Villoresi, C. Altucci, R. Velotta, S. Stagira, S. D. Silvestri, and M. Nisoli, Science 314, 443 (2006).
  * Krausz and Ivanov (2009) F. Krausz and M. Ivanov, Reviews Of Modern Physics 81, 163 (2009).
  * Itatani  _et al._ (2002) J. Itatani, F. Quéré, G. L. Yudin, M. Y. Ivanov, F. Krausz, and P. B. Corkum, Physical Review Letters 88, 173903 (2002).
  * Kienberger  _et al._ (2004) R. Kienberger, E. Goulielmakis, M. Uiberacker, A. Baltuska, V. Yakovlev, F. Bammer, A. Scrinzi, T. Westerwalbesloh, U. Kleineberg, U. Heinzmann, M. Drescher, and F. Krausz, Nature 427, 817 (2004).
  * Pazourek  _et al._ (2015) R. Pazourek, S. Nagele, and J. Burgdörfer, Reviews Of Modern Physics 87, 765 (2015).
  * Seiffert  _et al._ (2017) L. Seiffert, Q. Liu, S. Zherebtsov, A. Trabattoni, P. Rupp, M. C. Castrovilli, M. Galli, F. Süßmann, K. Wintersperger, J. Stierle, G. Sansone, L. Poletto, F. Frassetto, I. Halfpap, V. Mondes, C. Graf, E. Rühl, F. Krausz, M. Nisoli, T. Fennel, F. Calegari, and M. F. Kling, Nature Physics 13, 766 (2017).
  * Schultze  _et al._ (2010) M. Schultze, M. Fieß, N. Karpowicz, J. Gagnon, M. Korbman, M. Hofstetter, S. Neppl, A. L. Cavalieri, Y. Komninos, T. Mercouris, C. A. Nicolaides, R. Pazourek, S. Nagele, J. Feist, J. Burgdörfer, A. M. Azzeer, R. Ernstorfer, R. Kienberger, U. Kleineberg, E. Goulielmakis, F. Krausz, and V. S. Yakovlev, Science 328, 1658 (2010).
  * Vos  _et al._ (2018) J. Vos, L. Cattaneo, S. Patchkovskii, T. Zimmermann, C. Cirelli, M. Lucchini, A. Kheifets, A. S. Landsman, and U. Keller, Science 360, 1326 (2018).
  * Biswas  _et al._ (2020) S. Biswas, B. Förg, L. Ortmann, J. Schötz, W. Schweinberger, T. Zimmermann, L. Pi, D. Baykusheva, H. A. Masood, I. Liontos, A. M. Kamal, N. G. Kling, A. F. Alharbi, M. Alharbi, A. M. Azzeer, G. Hartmann, H. J. Wörner, A. S. Landsman, and M. F. Kling, Nature Physics 16, 778 (2020).
  * Cavalieri  _et al._ (2007) A. L. Cavalieri, A. L. Cavalieri, N. Müller, N. M. u. ller, T. Uphues, T. Uphues, V. S. Yakovlev, V. S. Yakovlev, A. B. s. ka, A. Baltuska, B. Horvath, B. Horvath, B. Schmidt, B. Schmidt, L. B. u. mel, L. Blümel, R. Holzwarth, R. Holzwarth, S. Hendel, S. Hendel, M. Drescher, M. Drescher, U. Kleineberg, U. Kleineberg, P. M. Echenique, P. M. Echenique, R. Kienberger, R. Kienberger, F. Krausz, U. Heinzmann, and U. Heinzmann, Nature 449, 1029 (2007).
  * Ossiander  _et al._ (2018) M. Ossiander, J. Riemensberger, S. Neppl, M. Mittermair, M. Schäffer, A. Duensing, M. S. Wagner, R. Heider, M. Wurzer, M. Gerl, M. Schnitzenbaumer, J. V. Barth, F. Libisch, C. Lemell, J. Burgdörfer, P. Feulner, and R. Kienberger, Nature 561, 374 (2018).
  * Neppl  _et al._ (2012) S. Neppl, E. M. Bothschafter, A. L. Cavalieri, D. Menzel, J. V. Barth, F. Krausz, R. Kienberger, and P. Feulner, Physical Review Letters 109, 087401 (2012).
  * Neppl  _et al._ (2015) S. Neppl, R. Ernstorfer, A. L. Cavalieri, C. Lemell, G. Wachter, E. Magerl, E. M. Bothschafter, M. Jobst, M. Hofstetter, U. Kleineberg, J. V. Barth, D. Menzel, J. Burgdörfer, P. Feulner, F. Krausz, and R. Kienberger, Nature 517, 342 (2015).
  * Siek  _et al._ (2017) F. Siek, S. Neb, P. Bartz, M. Hensen, C. Strüber, S. Fiechter, M. Torrent-Sucarrat, V. M. Silkin, E. E. Krasovskii, N. M. Kabachnik, S. Fritzsche, R. D. Muiño, P. M. Echenique, A. K. Kazansky, N. Müller, W. Pfeiffer, and U. Heinzmann, Science 357, 1274 (2017).
  * Sambe (1973) H. Sambe, Phys. Rev. A 7, 2203 (1973).
  * Sentef  _et al._ (2015) M. A. Sentef, M. Claassen, A. F. Kemper, B. Moritz, T. Oka, J. K. Freericks, and T. P. Devereaux, Nat. Commun. 6, 7047 (2015).
  * Kalthoff  _et al._ (2018) M. H. Kalthoff, G. S. Uhrig, and J. K. Freericks, Phys. Rev. B 98, 035138 (2018).
  * Schüler  _et al._ (2020a) M. Schüler, U. De Giovannini, H. Hübener, A. Rubio, M. A. Sentef, and P. Werner, Science Advances 6, eaay2730 (2020a).
  * Schüler  _et al._ (2020b) M. Schüler, U. D. Giovannini, H. Hübener, A. Rubio, M. A. Sentef, T. P. Devereaux, and P. Werner, Physical Review X 10, 041013 (2020b).
  * Wang  _et al._ (2013) Y. H. Wang, H. Steinberg, P. Jarillo-Herrero, and N. Gedik, Science 342, 453 (2013).
  * Mahmood  _et al._ (2016) F. Mahmood, C.-K. Chan, Z. Alpichshev, D. Gardner, Y. Lee, P. A. Lee, and N. Gedik, Nat. Phys. 12, 306 (2016).
  * Park (2014) S. T. Park, Physical Review A 90, 013420 (2014).
  * Paul  _et al._ (2001) P. M. Paul, E. S. Toma, P. Breger, G. Mullot, F. Augé, P. Balcou, H. G. Muller, and P. Agostini, Science 292, 1689 (2001).
  * Klünder  _et al._ (1 04) K. Klünder, J. M. Dahlström, M. Gisselbrecht, T. Fordell, M. Swoboda, D. Guénot, P. Johnsson, J. Caillat, J. Mauritsson, A. Maquet, R. Taïeb, and A. L’Huillier, Physical Review Letters 106, 143002 (2011-04), 1012.3863 .
  * Tao  _et al._ (2016) Z. Tao, C. Chen, T. Szilvási, M. Keller, M. Mavrikakis, H. Kapteyn, and M. Murnane, Science 353, 62 (2016).
  * Heinrich  _et al._ (2021) S. Heinrich, T. Saule, M. Högner, Y. Cui, V. S. Yakovlev, I. Pupeza, and U. Kleineberg, Nature Communications 12, 3404 (2021).
  * Rettig  _et al._ (2015) L. Rettig, S. O. Mariager, A. Ferrer, S. Grübel, J. A. Johnson, J. Rittmann, T. Wolf, S. L. Johnson, G. Ingold, P. Beaud, and U. Staub, Physical Review Letters 114, 067402 (2015).
  * Gerber  _et al._ (2017) S. Gerber, S. L. Yang, D. Zhu, H. Soifer, J. A. Sobota, S. Rebec, J. J. Lee, T. Jia, B. Moritz, C. Jia, A. Gauthier, Y. Li, D. Leuenberger, Y. Zhang, L. Chaix, W. Li, H. Jang, J. S. Lee, M. Yi, G. L. Dakovski, S. Song, J. M. Glownia, S. Nelson, K. W. Kim, Y. D. Chuang, Z. Hussain, R. G. Moore, T. P. Devereaux, W. S. Lee, P. S. Kirchmann, and Z. X. Shen, Science 357, 71 (2017).
  * Hein  _et al._ (2020) P. Hein, S. Jauernik, H. Erk, L. Yang, Y. Qi, Y. Sun, C. Felser, and M. Bauer, Nature Communications 11, 2613 (2020).
  * Suzuki  _et al._ (2021) T. Suzuki, Y. Shinohara, Y. Lu, M. Watanabe, J. Xu, K. L. Ishikawa, H. Takagi, M. Nohara, N. Katayama, H. Sawa, M. Fujisawa, T. Kanai, J. Itatani, T. Mizokawa, S. Shin, and K. Okazaki, Phys. Rev. B 103, L121105 (2021).
  * Giustino (2017) F. Giustino, Rev. Mod. Phys. 89, 015003 (2017).
  * Sobota  _et al._ (2021) J. A. Sobota, Y. He, and Z.-X. Shen, Rev. Mod. Phys. 93, 025006 (2021).
  * Voorhis (2015) T. V. Voorhis, Nature Physics 11, 300 (2015).
  * Hübener  _et al._ (2017) H. Hübener, M. A. Sentef, U. De Giovannini, A. F. Kemper, and A. Rubio, Nat. Commun. 8, 13940 (2017).
  * Madéo  _et al._ (2020) J. Madéo, M. K. L. Man, C. Sahoo, M. Campbell, V. Pareek, E. L. Wong, A. Al-Mahboob, N. S. Chan, A. Karmakar, B. M. K. Mariserla, X. Li, T. F. Heinz, T. Cao, and K. M. Dani, Science 370, 1199 (2020), 2005.00241 .
  * Dong  _et al._ (2021) S. Dong, M. Puppin, T. Pincelli, S. Beaulieu, D. Christiansen, H. Hübener, C. W. Nicholson, R. P. Xian, M. Dendzik, Y. Deng, Y. W. Windsor, M. Selig, E. Malic, A. Rubio, A. Knorr, M. Wolf, L. Rettig, and R. Ernstorfer, Natural Sciences n/a, e10010 (2021).


my hack/.style= late after line=
, late after last line= ,

An experimental study of algorithms for obtaining a singly connected subgraph

Ahmed Zahloote, Al-hasan Saleh, Ayman Ghanem, Hiba Hasan, Asem Dreibaty, Ali
Abodaraa, Nermeen Suleiman,Nour Naameh,Ali Ibrahim, Zeinab mahfoud

###### Abstract

A directed graph $G=(V,E)$ is singly connected if for any two vertices $v,u\in
V$, the directed graph $G$ contains at most one simple path from $v$ to $u$.
In this paper, we study different algorithms to find a feasible but
necessarily optimal solution to the following problem. Given a directed
acyclic graph $G=(V,E)$, find a subset $H\subseteq E$ of minimum size such
that the subgraph $(V,E\setminus H)$ is singly connected. Moreover, we prove
that this problem can be solved in polynomial time for a special kind of
directed graphs.

keywords
Depth First Search, Singly Connected Graph, cross edges, forward edges,
backward edges, Sources, Sinks

##  1 Introduction

A directed graph $G=(V,E)$ is singly connected if for any two vertices $v,u\in
V$, the directed graph $G$ contains at most one simple path from $v$ to $u$
[2, 3]. Buchsbaum and Carlisle [1], Khuller [5, 6], and Karlin [7] provided
algorithms to check whether an input directed graph is singly connected or not
in $O(n^{2})$ time. In $2015$, Dietzfelbinger and Jaberi [4] presented a
better algorithm for testing whether a directed graph is singly connected or
not. Moreover, they proved that the following problem is NP-hard. Given a
directed graph $G=(V,E)$, find a subset $H\subseteq E$ of minimum size such
that the subgraph $(V,E\setminus H)$ is singly connected. In this paper, we
prove that this problem can be solved in polynomial time for a special kind of
graphs. Furthermore, we study different algorithms to find a feasible but
necessarily optimal solution to this problem when the input graph has no
cycles.

##  2 An optimal solution for special kind of graphs

In this section we study a special case when the input graph $G=(V,E)$ has the
following properties:

  * •

$G$ has no cycles

  * •

the number of sources in G is one

  * •

the number of verices is equal to the number of edges in $G$

The following Theorem shows that removing only one edge leaves a singly
connected subgraph. This means we can find an optimal solution which contains
only one edge.

Theorem $1$: Let $G=(V,E)$ be a directed acyclic graph such that $|E|=|V|$ and
the number of sources in $G$ is one. Then an optimal solution can be found in
polynomial time.

proof. Let $h$ be the source in $G$. Then all the veritices in $V$ are
reachable from the vertex $h$ [12]. Therefore, performing depth first search
algorithm starting from vertex $h$ produces exactly $|V|-1$ tree edges and one
non-tree edge which is a cross or forward edge. Moreover, these tree edges
form a tree called dfs tree. This tree is a subgraph of $G$ and for any two
vertices $v,u\in V$, there is at most one simple path from $v$ to $u$ in this
tree. Notice that the non-tree edge produced by depth first search is an
optimal solution.

The following pseudocode (DFS_once) shows an algorithm that is able to compute
an optimal solution when the input graph is a directed acyclic graph with one
source and the number of edges is equal to the number of vertices.

DFS_once(DirectedGraph):
1\. Let $h$ be the source source in $G$
2\. tree $\longleftarrow$ DFS(DirectedGraph)
3\. for each edge in tree:
{
3.1 if(edge.class.is_equal_to(”cross”) or edge.class.is_equal_to(”forward”))
{ 3.1.1 cross_edge $\longleftarrow$ edge } }
4\. DirectedGraph.remove_edges_from(cross_edge)
5\. return DirectedGraph

The correctness of this algorithm follows from Theorem $1$ and the following
theorem shows that DFS_once algorithm runs in linear time.
Theorem $2$. DFS_once algorithm runs in $O(n)$ time.
proof. DFS runs in linear time and the number of edges is $n$.

##  3 Algorithms for directed graphs that has no cycles

In this section we describe different algorithms for obtaining a singly
connected subgraph when the input graph contains no cycles.

###  3.1 Algorithm 1

The first algorithm is about doing DFS (Depth First Search) on each node with
indegree zero (called a source node) and classify each edge during the search
then we combine the edges classified as cross or forward edges and delete them
from graph, here is the pseudo code:

DFS_From_Sources(DirectedGraph):
{
1\. non_tree_edges[ ] $\longleftarrow$ [ ]
2\. sources[ ] $\longleftarrow$ [ ]
3\. for each node in Directedgraph do
{ 3.1 deg $\longleftarrow$ node.caldegree(node)
3.2 if(deg.is_equal_to(0)
{ 3.2.1 sources.add(node) } }
4\. for each source in sources do
{ 4.1 tree$\longleftarrow$ DFS(Source) /*this classifies edges of tree to
cross,forward and tree edges*/
4.2 for each edge in tree do { 4.2.1 if(edge.class.is_equal_to(”cross”) or
edge.class.is_equal_to(”forward”))
{ 4.2.1.1 non_tree_edges.add(edge) } }
5\. DirectedGraph.remove_edges_from(non_tree_edges[])
6\. return DirectedFraph
}

Theorem $3$. The running time of DFS_From_Sources algorithm is $O(n(n+m)$
Proof. Calculating the indegree for all vertices requires $O(n+m)$ time.
Furthermore, DFS runs in linear time and edges can be classified using dfs in
linear time.

Theorem 4: The first algorithm (DFS_from_sources) returns a singly connected
subgraph.
proof. Let $H$ be the set of non-tree edges computed in DFS_from_sources
algorithm. Suppose that the subgraph $(v,E\setminus H)$ is not singly
connected. Then there are two vertices $u,v\in V$ such that the subgraph
$(V,E\setminus H)$ contains two edge-disjoint paths P,$\acute{P}$ from $u$ to
$v$ in $G$ Consequently, since the subgraph $(V,E\setminus H)$ is a directed
acyclic graph there is a source $s\in V$ such that all the vertices and edges
of the paths P,$\acute{P}$ are reachable from the source $s$. Notice that the
DFS tree rooted at $s$ can’t have two tree edges entering $u$.

###  3.2 Algorithm 2

The second algorithm is similar to the first one but the difference is that
the execution of DFS will depend on the number of sources and sinks so if
there are more sinks than sources about reversing the direction of all the
edges and then executing DFS (Depth First Search) on each node with outdegree
of the node equal to zero (a sink node) and classify each edge during the
search then we combine the edges classified as cross or forward edges and
delete corresponding original edges from the graph, here is the pseudo code:

DFS_From_Sources$|$Sinks(DirectedGraph):
{
1\. non_tree_edges[ ] $\longleftarrow$ [ ]
2\. sinks[ ] $\longleftarrow$ [ ]
3\. sources[ ] $\longleftarrow$ [ ]
4\. for each node in Directedgraph do
{ 4.1 indeg $\longleftarrow$ node.caldegree()
4.2 outdeg $\longleftarrow$ node.cal_outdegree()
4.3 if(indeg.is_equal_to(0)
{ 4.3.1 sources.add(node) } 4.4 if(outdeg.is_equal_to(0)
{ 4.4.1 sinks.add(node) } }
5\. max $\longleftarrow$ max(sources,sinks)
6\. for each node in max do
{ 6.1 tree$\longleftarrow$ DFS(node) /*this classifies edges of tree to
cross,forward and tree edges*/
6.2 for each edge in tree do { 6.2.1 if(edge.class.is_equal_to(”cross”) or
edge.class.is_equal_to(”forward”))
{ 6.2.1.1 non_tree_edges.add(edge) } }
7\. DirectedGraph.remove_edges_from(non_tree_edges[])
8\. DirectedGraph.reverse_edges
9\. return DirectedGraph
}

Theorem $5$. Algorithm DFS_From_Sources$|$Sinks runs in O(max$\emph{
\\{i1,i2}\\}$.(n+m)) time where _i1_ is the number of sources and _i2_ is the
number of sinks, the second algorithm pretty similar to the first one but the
only difference is that edges may be reversed based on the biggest number
between sources and sinks(if the sinks are more than the sources)

The correctness of the second algorithm (DFS from max(sinks,sources))follows
from theorem $4$ and the following observation, G is singly connected if and
only if $G^{R}$ is singly connected.

###  3.3 Algorithm 3

The third algorithm calculates dfs tree rooted at each source. The edges of
these dfs trees form a subgraph which is not necessarily singly connected.
Then the algorithm performs the first algorithm on the obtained subgraph, here
is the pseudo code:

DFS_on_tree_edges(DirectedGraph):
{
1\. non_tree_edges[ ] $\longleftarrow$ [ ]
2\. sinks[ ] $\longleftarrow$ [ ]
3\. sources[ ] $\longleftarrow$ [ ]
4\. for each node in Directedgraph do
{ 4.1 indeg $\longleftarrow$ node.caldegree()
4.2 outdeg $\longleftarrow$ node.cal_outdegree()
4.3 if(indeg.is_equal_to(0)
{ 4.3.1 sources.add(node) } }
5\. tree_edges_set$\longleftarrow$ {}
6\. for each source in sources do
{ 6.1 tree$\longleftarrow$ DFS(Source)
6.2 for each edge in tree do:
{
6.2.1 tree_edges_set $\longleftarrow$ tree_edges_set + edge } }
7\. DirectedGraph.remove_edges_from(tree_edges_set)
8\. for each source in sources do
{ 8.1 tree $\longleftarrow$ DFS(Source)
8.2 for each edge in tree do:
{ 8.2.1 if(edge.class.is_equal_to(”cross”) or
edge.class.is_equal_to(”forward”))
{ 8.2.1.1 non_tree_edges.add(edge) } }

}
9\. DirectedGraph.remove_edges_from(non_tree_edges)
10\. return DirectedGraph

Theorem $6$ The running time of the algorithm (DFS_on_tree_edges) is
O(i(n+m)).

Notice that the tree edges calculated by performing dfs on each source form a
subgraph but necessarily singly connected. But when we perform the first
algorithm on this subgraph we can obtain a singly connected subgraph by
removing cross and forward edges. Therefore, the correctness of algorithm
DFS_on_tree_edges follows from Theorem $4$.

###  3.4 Algorithm 4:

Algorithm 4 executes DFS search on every medial node (medial means that it’s
not a source or a sink), after that we perform algorithm1 on the resulting
subgraph, the pseudo code:

DFS_from_medials(DirectedGraph):
1\. non_tree_edges[ ] $\longleftarrow$ [ ]
2\. medials[ ] $\longleftarrow$ [ ]
3\. for each node in Directedgraph do
{ 3.1 indeg $\longleftarrow$ node.caldegree()
3.2 outdeg $\longleftarrow$ node.cal_outdegree()
3.3 if(indeg.is_not_equal_to(0) & outdeg.is_not_equal_to(0) )
{ 3.3.1 medials.add(node) } }
4\. for each medial in medials do
{ 4.1 tree$\longleftarrow$ DFS(medial) 4.2 for each edge in tree do { 4.2.1
if(edge.class.is_equal_to(”cross”) or edge.class.is_equal_to(”forward”))
{ 4.2.1.1 non_tree_edges.add(edge) } }
5\. TempGraph $\longleftarrow$ Graph(DirectedGraph.nodes(), non_tree_edges)
6\. execute Algorithm 1 on TempGraph
7\. return TempGraph
}

Theorem $7$. algorithm DFS_from_medials runs in $O(n(n++m))$ time.

##  4 Study Results:

the following table contains the results for the execution of the algorithms
on three graphs two of them were taken from SNAP, the first one is
p2p-Gnutella04 [8, 9, 10] and the second one is soc-Epinions1[8, 11] (we
removed all cycles from p2p-Gnutella04 and soc-Epinions1), the third one it’s
a simple random acyclic graph that we built to try the algorithms on small
inputs, the cpu used to execute code on the data is Intel core i7 11370h and
16GBs of memory, here are the results:

[my hack]results.csv

## Acknowledgements.

We gratefully give all appreciation and thanks to Dr. Raed Jaberi for teaching
and lecturing us approximation algorithms and advanced algorithms.

## References

  * [1] A.L. Buchsbaum, M.C. Carlisle, Determining uni-connectivity in directed graphs, Information Processing Letters 48(1)(1993) 9–12.
  * [2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Electrical Engineering and Computer Science Series, MIT Press, Cambridge, MA, 1991.
  * [3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, third edition, 2009.
  * [4] Martin Dietzfelbinger, Raed Jaberi: On testing single connectedness in directed graphs and some related problems. Inf. Process. Lett. 115(9): 684–688 (2015)
  * [5] S. Khuller, An O($|V|^{2}$) algorithm for single connectedness, Information Processing Letters, 72(3–4)(1999) 105–107.
  * [6] S. Khuller, Addendum to ”An O($|V|^{2}$) algorithm for single connectedness”, Information Processing Letters, 74(5–6) (2000) 263.
  * [7] A. Karlin, Solution to homework 7, CS 421, Winter 1995, Department of Computer Science, University of Washington, 1995.
  * [8] Jure Leskovec and Andrej Krevl,https://snap.stanford.edu/data/,2014
  * [9] J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007.
  * [10] M. Ripeanu and I. Foster and A. Iamnitchi. Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design. IEEE Internet Computing Journal, 2002.
  * [11] M. Richardson and R. Agrawal and P. Domingos. Trust Management for the Semantic Web. ISWC, 2003.
  * [12] Robert Sedgewick, Kevin Wayne: Algorithms, 4th Edition. Addison-Wesley 2011, ISBN 978-0-321-57351-3, pp. I-XII, 1-955