# Microresonator-referenced soliton microcombs with zeptosecond-level timing
noise

Xing Jin1∗, Zhenyu Xie1∗, Xiangpeng Zhang2∗, Hanfei Hou1∗, Fangxing Zhang3,
Xuanyi Zhang1, Lin Chang2, Qihuang Gong1,3,4, and Qi-Fan Yang1,3,4†
1State Key Laboratory for Artificial Microstructure and Mesoscopic Physics and
Frontiers Science Center for Nano-optoelectronics, School of Physics, Peking
University, Beijing 100871, China
2State Key Laboratory of Advanced Optical Communications System and Networks,
School of Electronics, Peking University, 100871 Beijing, China
3Peking University Yangtze Delta Institute of Optoelectronics, Nantong,
Jiangsu 226010, China
4Collaborative Innovation Center of Extreme Optics, Shanxi University, 030006,
Taiyuan, China
∗These authors contributed equally to this work.
†Corresponding author<EMAIL_ADDRESS>
Optical frequency division relies on optical frequency combs to coherently
translate ultra-stable optical frequency references to the microwave domain 1,
2, 3, 4, 5. This technology has enabled microwave synthesis with ultralow
timing noise, but the required instruments are too bulky for real-world
applications. Here, we develop a compact optical frequency division system
using microresonator-based frequency references 6, 7, 8 and comb generators 9.
The soliton microcomb formed in an integrated Si3N4 microresonator is
stabilized to two lasers referenced to an ultrahigh-$Q$ MgF2 microresonator.
Photodetection of the soliton pulse train produces 25 GHz microwaves with
absolute phase noise of -141 dBc/Hz (547 zs Hz-1/2) at 10 kHz offset
frequency. The synthesized microwaves are tested as local oscillators in
jammed communication channels, resulting in improved fidelity compared with
those derived from electronic oscillators. Our work demonstrates unprecedented
coherence in miniature microwave oscillators, providing key building blocks
for next-generation timekeeping, navigation, and satellite communication
systems 10, 11.

Introduction

Consumer microwave technologies are transitioning towards X-band and beyond to
accommodate the booming data traffic. However, these expanded radiofrequency
channels will soon be overwhelmed by the exponential growth of satellite
communications 12. Furthermore, other microwave applications, including
geodesy 13, meteorological observations 14, and marine monitoring 15 are
utilizing these same frequency ranges. It is envisioned that the improvement
of channel capacity and transmission fidelity would be the most significant
task for the widespread implementation of next-generation communication
technologies.

To this end, low-noise microwave oscillators have become the cornerstone for
advanced communication systems, which can enable high modulation formats and
minimize inter-channel cross-talks. They also play a critical role in
enhancing the accuracy, sensitivity, and dynamic range of radars 16. While
electronic oscillators are facing bandwidth limitations and degraded
performance at higher-frequency bands, photonic technologies can overcome this
challenge by synthesizing microwaves through laser beatnotes, as in the form
of optoelectronic oscillators 17, 18, Brillouin oscillators 19, 20, dual-
frequency lasers 21, and optical frequency combs 22. Notably, optical
frequency combs offer the unique ability to coherently connect optical and
microwave signals through optical frequency division (OFD) 4. This is usually
achieved by stabilizing a set of equidistant comb lines – the comb structure –
to optical frequency references, and the microwave-rate beatnote of comb lines
sustains the relative stability of frequency references with remarkable
fidelity 1, 2, 3, 5, 23, 24. OFD of ultra-stable frequency references derived
from atoms, ions, or high-finesse optical resonators has led to many
performance milestones in microwave technology, including record low absolute
timing noise of 41 zs Hz-1/2 3 and fractional stability of 10-18 5.

Fig. 1: Conceptual illustration of microresonator-based optical frequency
division (OFD). a, Photograph of the MgF2 reference microresonator. b,
Photograph of the Si3N4 nonlinear microresonator. The insets show the cross-
sectional profile of the fundamental mode of each microresonator. c, Concept
of two-point OFD. d, OFD error signal generation and feedback control of the
soliton microcomb. PLL: phase-locked loop. PD: photodetector.

The key components of an OFD system are frequency references and optical
frequency combs, which are typically bulky and expensive. For example,
conventional ultra-stable resonators, such as Fabry-Pérot resonators made of
ultra-low-expansion glass or single-crystal silicon 25, 1, 3, 26, often
require vacuum enclosures or cryogenic temperatures to minimize acoustic noise
and thermal drifts. Moreover, table-top optical frequency combs that are
constructed from free-space or fiber-optic elements are usually too delicate
for operation outside laboratories. Recently, integrated OFD systems have been
proposed 27, 28, which are motivated by the demonstration of soliton
microcombs in microresonators 9. Ultra-stable resonators have also been
redesigned to operate under ambient conditions. Miniaturized OFD systems using
centimeter-scale mini Fabry-Pérot resonators have achieved remarkable timing
noise performance approaching 1 as Hz-1/2 at 10 kHz offset frequencies 27.

Whispering-gallery-mode (WGM) microresonators have been proposed as potential
candidates for ultra-stable frequency references. Firstly, these
microresonators are solid-state devices with exceptional mechanical stability.
The optical modes are confined along the periphery through total internal
reflections, resulting in a highly compact geometry that can be realized using
thin disks or photonic chips. This mechanism also supports ultra-high-$Q$
factors exceeding 100 million 29, 30, 31, 32, 33, 34. Moreover, they can be
fabricated using temperature-insensitive materials (with low thermo-optic and
thermal expansion coefficients). These features provide appealing noise
performance and compactness for OFD systems.

In this work, we advance miniature OFD technology by referencing a soliton
microcomb to a WGM microresonator, and the synthesized microwave features
record-low timing noise among all miniature photonic microwave oscillators. As
depicted in Fig. 1a, the reference microresonator is fabricated from a MgF2
disk through meticulous mechanical grinding and polishing processes 35,
yielding a diameter of 9.6 mm and a free-spectral-range ($FSR$) of 7 GHz. The
trapezoid cross section supports WGMs with mode areas over 1000 µm2. Such a
large mode volume, combined with a low thermo-optic coefficient of $1\times
10^{-6}$ K-1, provides a low thermorefractive noise that is at least 30 dB
lower than silica and Si3N4 microresonators with the same $FSR$. On the other
hand, Si3N4 microresonators are very suitable for soliton microcomb generation
due to their strong Kerr nonlinearity and tight optical confinement. The Si3N4
microresonator used here is fabricated via standard photolithography and
plasma-etching processes 36, resulting in an $FSR$ closely approximating 25
GHz. Two-point OFD operations based on these two devices are described in Fig.
1c. Two lasers ($f_{A}$ and $f_{B}$) are simultaneously stabilized to two
modes of the MgF2 microresonator. The spatial overlap between these two modes
provides common-mode noise rejection once the residual locking noise is below
the thermal noise. It results in a mutual phase noise for $f_{B}-f_{A}$ that
is lower than that of each laser, and we use $f_{B}-f_{A}$ as the frequency
reference for further division. As described in Fig. 1d, the microresonator is
excited by a continuous-wave pump laser to generate a soliton microcomb with
repetition frequency $f_{r}$. The reference lasers are combined with two
adjacent comb lines that are indexed by $m$ and $n$ relative to the pump. The
photodetected beatnotes are then down-mixed to $f_{B}-f_{A}-(m-n)f_{r}$ and
locked to a local oscillator (LO) with the frequency of $f_{\mathrm{LO}}$.
This locking is commonly achieved by adjusting the frequency of the pump
laser, which regulates the repetition frequency through the Raman-induced
soliton-self-frequency-shift mechanism 37. Photodetection of the soliton pulse
train provides the stabilized repetition frequency as:

$f_{r}=\frac{f_{B}-f_{A}-f_{\mathrm{LO}}}{m-n}.$ (1)

If the phase noise of the LO is not dominant, we can anticipate that the phase
noise of $f_{r}$ is reduced by a factor of $(m-n)^{2}$ compared with that of
$f_{B}-f_{A}$.

Results

Fig. 2: Characterization of optical frequency references. a,  Photograph of
the packaged MgF2 reference microresonator. b, Typical transmission spectrum
of a resonance. The intrinsic quality factor is derived from Lorentzian
fitting as 3.4 billion. c, Setup of multi-frequency delayed self-heterodyne
interferometer. AOFS: acousto-optic frequency shifters; PC: polarization
controller; LO: local oscillator; BPF: optical bandpass filter; OSC:
oscilloscope. d, Measured relative frequency noise of the free-running and
locked reference lasers. The simulated individual and relative
thermorefractive noise of the references are also plotted, between which is
the regime accessible via common-mode noise rejection.

Optical frequency references

We first characterize the performance of the frequency reference. To ensure
stable operation, we enclose the MgF2 microresonator in a metallic package
with a tapered fiber coupler and a thermoelectric cooler (Fig. 2a). The
packaging process does not degrade the resonator’s $Q$ factors, which can
exceed 3 billion under near-critical coupling conditions. Two fiber lasers at
wavelengths of 1540 nm and 1560 nm are stabilized to the MgF2 microresonator
using the Pound-Drever-Hall (PDH) technique. Servo control is applied to the
laser piezos and acousto-optic frequency shifters (AOFS), providing a locking
bandwidth of up to 300 kHz. The relative frequency noises of these lasers are
characterized using a multi-frequency delayed self-heterodyne interferometer
38, 39 (Fig. 2c). The two reference lasers are combined and sent to an AOFS
driven by a 55 MHz LO. The 0th and 1st-order diffraction lights travel in two
arms of an unbalanced Mach-Zender interferometer respectively before again
being combined and separated by a bandpass filter according to their
wavelength. The two reference lasers, along with their frequency-shifted
counterparts, are detected by two photodetectors, yielding two 55 MHz
beatnotes containing the phase fluctuation of the respective reference lasers.
Simultaneous extraction of the phases of the beatnotes is realized through two
methods. Hilbert transform of the oscilloscope traces provides fast sampling
rates but limited recording length; acquisition of the IQ demodulated
beatnotes using a datalogger provides a very long recording length at limited
sampling rates ($\textless$800 kHz). Such a combination allows for noise
measurement bandwidth from 10 Hz to 1 MHz. The relative frequency noise of the
reference lasers is shown in Fig. 2d, where locking to the microresonator
results in a noise reduction of more than 50 dB. Notably, the relative noise
at offset frequencies from 10 Hz to 10 kHz is 10 dB below the thermorefractive
noise of the microresonator. This is attributed to common-mode noise
rejection, which can lead to an additional 30 dB reduction factor if residual
locking noises are further minimized.

Fig. 3: Optical frequency division characterization. a, Experimental setup for
OFD. VCO: voltage-controlled oscillator; PM: phase modulator; EDFA: erbium-
doped fiber amplifier; NF: notch filter; Amp: electrical amplifier; LPF:
electrical lowpass filter; ESA: electrical spectrum analyzer; PNA: phase noise
analyzer. b, Optical spectra of the soliton microcomb and the reference
lasers. c, Beatnote of the free-running soliton microcomb. d, Beatnote of the
locked soliton microcomb. RBW: resolution bandwidth. e, Single sideband phase
noise of the free-running and locked beatnotes of the soliton microcomb. The
projected contribution (scaled by 40 dB) from the optical frequency references
is also shown for comparison. The dashed black line indicates the timing
jitter level of 1 as Hz-1/2. The gray shaded area represents the noise floor
of the PNA during the measurement.

Optical frequency division

The detailed experimental setup is illustrated in Fig. 3a. Soliton microcombs
are generated by pumping a packaged Si3N4 microresonator at 1550 nm using an
amplified fiber laser. By manually tuning the frequency of the pump laser from
a multi-soliton state 40, a single soliton state is achieved, exhibiting a
characteristic spectral envelope of sech2 and a 3-dB bandwidth spanning over
30 nm (Fig. 3b). This bandwidth is sufficient to bridge the frequency gap
between reference lasers (20 nm, or equivalently 2.5 THz), and dividing it to
the 25 GHz repetition frequency should provide a noise reduction factor of 40
dB. We use bandpass filters to select the frequency components near 1540 nm
and 1560 nm of the amplified soliton microcomb to beat with the reference
lasers separately. The beatnotes are amplified and then down-mixed to generate
the OFD error signal. To increase the locking range, the OFD error signal is
electrically divided by a factor of 8 before sending it into the PLL. By
adding an AOFS to the pump laser, the locking bandwidth can be extended to 200
kHz. Finally, the amplified soliton microcomb is sent into a fast
photodetector with proper dispersion compensation to suppress the Gordon-Haus
jitter introduced by the amplification process 41.

The radiofrequency beatnotes of the free-running and stabilized soliton
microcombs acquired with an electrical spectral analyzer are compared in Fig.
3c and d. The former is susceptible to various technical noise sources,
including noise transduced from the pump laser and temperature fluctuations
within the microresonator, leading to a broader linewidth and frequency drift.
In contrast, the repetition frequency of the stabilized soliton microcomb
primarily follows the frequency references and exhibits a significantly
narrowed linewidth. Figure 3e presents a more quantitative comparison
conducted using a phase noise analyzer (Rohde & Schwarz FSWP50). Within an
offset frequency range of 10 Hz to 10 kHz, OFD leads to a noise reduction
exceeding 40 dB compared to the free-running case. Within this frequency
range, the phase noise of the stabilized repetition frequency aligns closely
with that of the divided frequency references, achieving a level of -123(-141)
dBc/Hz at 1(10) kHz offset frequency. Above the corner frequencies of
approximately 200 kHz, its phase noise converges to the shot-noise-limited
level of -152 dBc/Hz.

Fig. 4: Anti-interference experiments. a, Conceptual diagram of an interfered
communication channel. b, Electrical spectra of the signals after up-
conversion using Keysight PSG E8257D (PSG) and OFD-based LOs. The black dashed
line in the up panel indicates the inferred information signal. c, The
differences in signal-to-noise ratio (SNR) of the information signal for PSG
and OFD-based LOs. The x-axis is the frequency gap between the information and
interference signals. d, Constellation diagram of interfered 64QAM data
transmission experiments using PSG and OFD-based LOs. The normalized symbol
density is indicated by color.

Anti-interference experiments

We compare the performance of our OFD system with a high-end electronic
oscillator (Keysight PSG E8257D, referred to as PSG in the following text) as
the LOs in two anti-interference experiments. The objective is to test the
anti-interference performance of the LOs under conditions of intense
communication jamming 42, such as satellite communications disturbed by
millimeter waves for 5G communications and autonomous vehicles (Fig. 4a). We
start the experiments by up mixing a pair of frequency-close single-tone
signals – one serving as the strong interference (-20 dBm) and the other as
the weak information (-97 dBm) – with the local oscillation signal generated
by PSG and OFD respectively (Extended Data Fig. 1 a). As shown in Fig. 4b,
when PSG is used as the LO, the noise floor of the converted interference is
so high that the information signal is drowned out. When shifting from PSG to
OFD-based LO, a previously obscured information signal can be observed, which
can be attributed to the ultra-low phase noise characteristics of the OFD-
based LO. We then compare the signal-to-noise ratio of the information signals
for the two cases at different frequency separations. Notably, our OFD system
provides a 20 dB advantage over the PSG when the two signals are 10 kHz apart
(Fig. 4c).

We then replace the single-tone information signal with communication data in
64QAM format with a symbol rate of 50 kBd to imitate a real communication
scenario (Extended Data Fig. 1 b). The frequency gap between the information
and interference signals is set to be 35 kHz. The up-mixed information signal
is analyzed using a vector signal analyzer for constellation diagram
construction and error vector magnitude (EVM) measurement. As can be seen in
Fig 4d, using the PSG-based LO yields an EVM of 12.06%, exceeding the 8%
threshold for standard 64QAM telecommunication. In contrast, using the OFD-
based LO yields an EVM of only 4.38%, maintaining an adequate signal fidelity
under heavy jamming due to its lower phase noise. These experimental results
suggest that our system can potentially outperform table-top electronic
microwave oscillators in the quest for robust communication systems.

Conclusion and outlook

Fig. 5: Comparison of microwaves synthesized by miniature photonic microwave
oscillators, scaled to 10 GHz. Performance of an integrated optoelectronic
oscillator 18, OEwaves HI-Q X-band optoelectronic oscillator (*), a Brillouin
laser oscillator in silica 19, a Brillouin laser oscillator in Si3N4 20, a
self-injection-locked laser based oscillator 21, a free-running microcomb in
Si3N4 43, a free-running microcomb in MgF2 32, a free-running microcomb in
silica 33, an optical parametric oscillation in Si3N4 referenced microcomb in
Si3N4 44, a Si3N4 coil cavity referenced microcomb in Si3N4 28, a mini
Fabry–Pérot cavity referenced microcomb in Si3N4 27, and a MgF2 microresonator
referenced microcomb in Si3N4 (this work) are in comparison. All of the noise
performance in this figure is scaled to a 10 GHz carrier frequency. The gray
shaded area indicates the noise performance of commercial electronics
(Keysight PSG E8257D). The dashed black indicates the timing jitter level of 1
as Hz-1/2.

The phase noise (scaled to 10 GHz carrier) and absolute timing noise of
miniature photonic microwave oscillators are summarized in Table 1 and Fig. 5.
The benefit of introducing frequency references is very obvious: it reduces
the absolute timing noise of free-running oscillators by more than 10 dB to a
level that is not attainable by commercial electronic oscillators. Notably,
our findings represent the lowest timing noise achieved from 100 Hz to 10 kHz
offset frequencies among all miniature photonic microwave oscillators. A
significant milestone is the realization of timing noise below 546 zs Hz-1/2
at a 10 kHz offset frequency. Such zeptosecond timing noise regime was
previously only accessible by referencing microcombs to a table-top ultra-
stable laser 45.

While the state-of-the-art table-top OFD systems provide more than an order of
magnitude lower timing noise 3, such performance difference can be mitigated
by increasing the division ratio, which would reduce the impact of the
residual locking noise. One-point OFD can be anticipated using self-referenced
microwave-rate microcombs, which could be achieved through a combination of
dispersion engineering 46 and efficient pumping schemes 47. Additionally,
optimizing the residual amplitude modulation in the phase modulator may
improve the level of common-mode noise rejection, potentially providing over
20 dB lower timing noise as inferred from Fig. 2d.

Further integration of the OFD system is viable. By leveraging thin-film
lithium niobate technology 48, key components such as phase modulators 49 and
acousto-optic modulators 50 can be implemented on chips. Integrated lasers 20,
29, 51 and soliton microcombs 52, 53, 54, 29, 55 with competitive noise
performance have also been recently demonstrated, and their low-noise
amplification for photodetection can be realized using erbium-doped waveguide
amplifiers 56. In addition, electro-optic comb generators can also be chosen
as the frequency divider such that the desired microwaves can be directly read
out from the driving VCO 2, 23, 49, 57. As for the optical references,
integrated waveguide couplers have been developed to interface with ultra-
high-$Q$ crystalline microresonators 58, 59. They should enable laser self-
injection locking to the microresonators, such that the PDH locking setup can
be eliminated to reduce the form factors and electrical power consumption 60.
These advances would extend the impact of OFD technologies to consumer markets
such as high-resolution radars for autonomous vehicles and transceivers for
high-speed wireless communications, providing a combination of exceptional
performance, compact size, robust operation, and mass production. They can
also facilitate a number of scientific tasks, including very long baseline
interferometry for space-based radio astronomy 61 and high-fidelity
manipulation of superconducting qubits 62, 63.

Table 1: Comparison of miniature photonic microwave oscillators.  * OEwaves
HI-Q X-band optoelectronic oscillator. The material to form the resonators
that serve as the oscillators and optical references are indicated in the
table.

Methods

Simulation of thermorefractive noise. The thermorefractive noise is
numerically simulated using a finite-element method based on fluctuation-
dissipation theorem 64, 65. The parameters of MgF2 used in the simulations are
the heat capacity $920$ $\text{\,}\mathrm{J}\ \mathrm{k}\mathrm{g}^{-1}\
\mathrm{K}^{-1}$, thermal conductivity $20.98$ $\text{\,}\mathrm{W}\
\mathrm{m}^{-1}\ \mathrm{K}^{-1}$, material density $3.18\times 10^{3}$
$\text{\,}\mathrm{k}\mathrm{g}\ \mathrm{m}^{-3}$, refractive index 1.37, and
thermal-optic coefficient $1\times 10^{-6}$ $\text{\,}\mathrm{K}^{-1}$. In the
simulations, the ambient temperature is assumed to be $300$
$\text{\,}\mathrm{K}$.

Acknowledgments

The Si3N4 chips used in this work were fabricated by Qaleido Photonics. The
MgF2 microresonators used in this work were fabricated and packaged by Peking
University Yangtze Delta Institute of Optoelectronics. The project is
supported by National Key R&D Plan of China (Grant No. 2021YFB2800601),
Beijing Natural Science Foundation (Z210004), National Natural Science
Foundation of China (92150108,62305006), Nantong Science and Technology Bureau
(MS12022003), and the High-performance Computing Platform of Peking
University.

Author contributions

Experiments were conceived and designed by X.J., Z.X., X.Z., H.H. and Q-F.Y.
Measurements and data analysis were performed by X.J., Z.X., X.Z., H.H., and
Q-F.Y. Numerical simulations of thermorefractive noise were performed by X.J.,
H.H, and X.Z. The MgF2 microresonator was designed and fabricated by X.Z. and
F.Z. All authors participated in preparing the manuscript.

Competing interests

The authors declare no competing interests.

Additional information

Correspondence and requests for materials should be addressed to Q-F.Y.

Extended Data Fig. 1: Experiments setup for anti-interference experiments. a,
The two signal generators produce a strong interference signal and a weak
information signal respectively. The two signals are coupled together, mixed
with a LO, and then sent to an electrical signal analyzer (ESA). b, A signal
generator and an arbitrary waveform generator (AWG) produce a strong
interference signal and a baud information signal for data transmission
respectively. The two signals are coupled together, mixed with a LO, and then
sent to a vector signal analyzer (VSA) to obtain the constellation diagrams.

## References

  * [1] Fortier, T. M. _et al._ Generation of ultrastable microwaves via optical frequency division.  _Nat. Photon._ 5, 425–429 (2011).
  * [2] Li, J., Yi, X., Lee, H., Diddams, S. A. & Vahala, K. J.  Electro-optical frequency division and stable microwave synthesis.  _Science_ 345, 309–313 (2014).
  * [3] Xie, X. _et al._ Photonic microwave signals with zeptosecond-level absolute timing noise.  _Nat. Photon._ 11, 44–47 (2017).
  * [4] Yao, Y., Jiang, Y. & Ma, L.  Optical frequency division.  _Natl. Sci. Rev._ 7, 1801–1802 (2020).
  * [5] Nakamura, T. _et al._ Coherent optical clock down-conversion for microwave frequencies with $\mathrm{10^{-18}}$ instability.  _Science_ 368, 889–892 (2020).
  * [6] Matsko, A. B., Savchenkov, A. A., Yu, N. & Maleki, L.  Whispering-gallery-mode resonators as frequency references. i. fundamental limitations.  _J Opt Soc Am B_ 24, 1324–1335 (2007).
  * [7] Alnis, J. _et al._ Thermal-noise-limited crystalline whispering-gallery-mode resonator for laser stabilization.  _Phys. Rev. A_ 84, 011804 (2011).
  * [8] Liu, K. _et al._ 36 Hz integral linewidth laser based on a photonic integrated 4.0 m coil resonator.  _Optica_ 9, 770–775 (2022).
  * [9] Kippenberg, T. J., Gaeta, A. L., Lipson, M. & Gorodetsky, M. L.  Dissipative Kerr solitons in optical microresonators.  _Science_ 361 (2018).
  * [10] Betz, J. W.  _Engineering satellite-based navigation and timing: global navigation satellite systems, signals, and receivers_ (John Wiley & Sons, 2015).
  * [11] Kodheli, O. _et al._ Satellite communications in the new space era: A survey and future challenges.  _IEEE Communications Surveys & Tutorials_ 23, 70–109 (2020).
  * [12] Hecht, J. _et al._ The bandwidth bottleneck.  _Nature_ 536, 139–142 (2016).
  * [13] Schlüter, W. & Behrend, D.  The international VLBI service for geodesy and astrometry (IVS): current capabilities and future prospects.  _J Geod_ 81, 379–387 (2007).
  * [14] Doviak, R. J. _et al._ _Doppler radar and weather observations_ (Courier Corporation, 2006).
  * [15] Huang, W., Liu, X. & Gill, E. W.  Ocean wind and wave measurements using X-band marine radar: A comprehensive review.  _Remote Sens._ 9, 1261 (2017).
  * [16] Ayhan, S. _et al._ Impact of frequency ramp nonlinearity, phase noise, and SNR on FMCW radar accuracy.  _IEEE Trans Microw Theory Tech_ 64, 3290–3301 (2016).
  * [17] Maleki, L.  The optoelectronic oscillator.  _Nat. Photon._ 5, 728–730 (2011).
  * [18] Tang, J. _et al._ Integrated optoelectronic oscillator.  _Opt. Express_ 26, 12257–12265 (2018).
  * [19] Li, J., Lee, H. & Vahala, K. J.  Microwave synthesizer using an on-chip Brillouin oscillator.  _Nat. Commun._ 4, 1–7 (2013).
  * [20] Gundavarapu, S. _et al._ Sub-hertz fundamental linewidth photonic integrated Brillouin laser.  _Nat. Photon._ 13, 60–67 (2019).
  * [21] Kittlaus, E. A. _et al._ A low-noise photonic heterodyne synthesizer and its application to millimeter-wave radar.  _Nat. Commun._ 12, 4397 (2021).
  * [22] Diddams, S. A., Vahala, K. & Udem, T.  Optical frequency combs: Coherently uniting the electromagnetic spectrum.  _Science_ 369, eaay3676 (2020).
  * [23] Li, J. & Vahala, K.  Small-sized, ultra-low phase noise photonic microwave oscillators at X-Ka bands.  _Optica_ 10, 33–34 (2023).
  * [24] Tetsumoto, T. _et al._ Optically referenced 300 GHz millimetre-wave oscillator.  _Nat. Photon._ 15, 516–522 (2021).
  * [25] Diddams, S. _et al._ An optical clock based on a single trapped $\mathrm{{}^{199}Hg^{+}}$ ion.  _Science_ 293, 825–828 (2001).
  * [26] Kessler, T. _et al._ A sub-40-mHz-linewidth laser based on a silicon single-crystal optical cavity.  _Nat. Photon._ 6, 687–692 (2012).
  * [27] Kudelin, I. _et al._ Photonic chip-based low noise microwave oscillator.  _arXiv preprint arXiv:2307.08937_ (2023).
  * [28] Sun, S. _et al._ Integrated optical frequency division for stable microwave and mmwave generation.  _arXiv preprint arXiv:2305.13575_ (2023).
  * [29] Jin, W. _et al._ Hertz-linewidth semiconductor lasers using cmos-ready ultra-high-Q microresonators.  _Nat. Photon._ 15, 346–353 (2021).
  * [30] Lee, H. _et al._ Chemically etched ultrahigh-Q wedge-resonator on a silicon chip.  _Nat. Photon._ 6, 369–373 (2012).
  * [31] Wang, C. Y. _et al._ Mid-infrared optical frequency combs at 2.5 $\mu$m based on crystalline microresonators.  _Nat. Commun._ 4, 1345 (2013).
  * [32] Liang, W. _et al._ High spectral purity Kerr frequency comb radio frequency photonic oscillator.  _Nat. Commun._ 6, 7957 (2015).
  * [33] Yao, L. _et al._ Soliton microwave oscillators using oversized billion Q optical microresonators.  _Optica_ 9, 561–564 (2022).
  * [34] Puckett, M. W. _et al._ 422 Million intrinsic quality factor planar integrated all-waveguide resonator with sub-MHz linewidth.  _Nat. Commun._ 12, 934 (2021).
  * [35] Qu, Z. _et al._ Fabrication of an ultra-high quality MgF2 micro-resonator for a single soliton comb generation.  _Opt. Express_ 31, 3005–3016 (2023).
  * [36] Ye, Z. _et al._ Foundry manufacturing of tight-confinement, dispersion-engineered, ultralow-loss silicon nitride photonic integrated circuits.  _Photonics Res._ 11, 558–568 (2023).
  * [37] Yi, X., Yang, Q.-F., Yang, K. Y. & Vahala, K.  Theory and measurement of the soliton self-frequency shift and efficiency in optical microcavities.  _Opt. Lett._ 41, 3419–3422 (2016).
  * [38] Jeong, D. _et al._ Ultralow jitter silica microcomb.  _Optica_ 7, 1108–1111 (2020).
  * [39] Lao, C. _et al._ Quantum decoherence of dark pulses in optical microresonators.  _Nat. Commun._ 14, 1802 (2023).
  * [40] Guo, H. _et al._ Universal dynamics and deterministic switching of dissipative Kerr solitons in optical microresonators.  _Nat. Phys._ 13, 94–102 (2017).
  * [41] Gordon, J. P. & Haus, H. A.  Random walk of coherently amplified solitons in optical fiber transmission.  _Opt. Lett._ 11, 665–667 (1986).
  * [42] Carr, J. J.  In _The Technician’s EMI Handbook_ , 163–195 (Newnes, Woburn, 2000).
  * [43] Liu, J. _et al._ Photonic microwave generation in the X- and K-band using integrated soliton microcombs.  _Nat. Photon._ 14, 486–491 (2020).
  * [44] Zhao, Y. _et al._ All-optical frequency division on-chip using a single laser.  _arXiv preprint arXiv:2303.02805_ (2023).
  * [45] Lucas, E. _et al._ Ultralow-noise photonic microwave synthesis using a soliton microcomb-based transfer oscillator.  _Nat. Commun._ 11, 1–8 (2020).
  * [46] Anderson, M. H. _et al._ Zero dispersion kerr solitons in optical microresonators.  _Nat. Commun._ 13, 4764 (2022).
  * [47] Helgason, Ó. B. _et al._ Surpassing the nonlinear conversion efficiency of soliton microcombs.  _Nat. Photon._ 1–8 (2023).
  * [48] Boes, A. _et al._ Lithium niobate photonics: Unlocking the electromagnetic spectrum.  _Science_ 379, eabj4396 (2023).
  * [49] Wang, C. _et al._ Integrated lithium niobate electro-optic modulators operating at CMOS-compatible voltages.  _Nature_ 562, 101–104 (2018).
  * [50] Shao, L. _et al._ Integrated microwave acousto-optic frequency shifter on thin-film lithium niobate.  _Opt. Express_ 28, 23728–23738 (2020).
  * [51] Li, B. _et al._ Reaching fiber-laser coherence in integrated photonics.  _Opt. Lett._ 46, 5201–5204 (2021).
  * [52] Stern, B., Ji, X., Okawachi, Y., Gaeta, A. L. & Lipson, M.  Battery-operated integrated frequency comb generator.  _Nature_ 562, 401 (2018).
  * [53] Raja, A. S. _et al._ Electrically pumped photonic integrated soliton microcomb.  _Nat. Commun._ 10, 680 (2019).
  * [54] Shen, B. _et al._ Integrated turnkey soliton microcombs.  _Nature_ 582, 365–369 (2020).
  * [55] Xiang, C. _et al._ Laser soliton microcombs heterogeneously integrated on silicon.  _Science_ 373, 99–103 (2021).
  * [56] Liu, Y. _et al._ A photonic integrated circuit–based erbium-doped amplifier.  _Science_ 376, 1309–1313 (2022).
  * [57] Hu, Y. _et al._ High-efficiency and broadband on-chip electro-optic frequency comb generators.  _Nat. Photon._ 16, 679–685 (2022).
  * [58] Liu, G. _et al._ Low-loss prism-waveguide optical coupling for ultrahigh-Q low-index monolithic resonators.  _Optica_ 5, 219–226 (2018).
  * [59] Anderson, M. _et al._ Highly efficient coupling of crystalline microresonators to integrated photonic waveguides.  _Opt. Lett._ 43, 2106–2109 (2018).
  * [60] Liang, W. _et al._ Ultralow noise miniature external cavity semiconductor laser.  _Nat. Commun._ 6, 1–6 (2015).
  * [61] Akiyama, K. _et al._ First sagittarius a* event horizon telescope results. i. the shadow of the supermassive black hole in the center of the milky way.  _Astrophys. J. Lett._ 930, L12 (2022).
  * [62] Clarke, J. & Wilhelm, F. K.  Superconducting quantum bits.  _Nature_ 453, 1031–1042 (2008).
  * [63] Gong, M. _et al._ Quantum walks on a programmable two-dimensional 62-qubit superconducting processor.  _Science_ 372, 948–952 (2021).
  * [64] Kondratiev, N. & Gorodetsky, M.  Thermorefractive noise in whispering gallery mode microresonators: Analytical results and numerical simulation.  _Phys. Lett. A_ 382, 2265–2268 (2018).
  * [65] Yang, Q.-F. _et al._ Dispersive-wave induced noise limits in miniature soliton microwave sources.  _Nat. Commun._ 12, 1442 (2021).


# Computational Complexity of the Recoverable Robust Shortest Path Problem
with Discrete Recourse

Marcel Jackiewicz  Wrocław University of Science and Technology, Wrocław,
Poland
<EMAIL_ADDRESS>Adam
Kasperski111Corresponding author Wrocław University of Science and Technology,
Wrocław, Poland
<EMAIL_ADDRESS>Paweł Zieliński
Wrocław University of Science and Technology, Wrocław, Poland
<EMAIL_ADDRESS>
###### Abstract

In this paper the recoverable robust shortest path problem is investigated.
Discrete budgeted interval uncertainty representation is used to model
uncertain second-stage arc costs. The known complexity results for this
problem are strengthened. It is shown that it is $\Sigma_{3}^{p}$-hard for the
arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it
is also proven that the inner adversarial problem for these neighborhoods is
$\Pi_{2}^{p}$-hard.

Keywords: robust optimization, interval data, recovery, shortest path.

##  1 Preliminaries

Let $G=(V,A)$ be a directed graph with nonnegative arc costs $C_{e}\geq 0$,
$e\in A$. Two nodes $s,t\in V$ are distinguished as a source and a destination
node, respectively. We will use $\Phi$ to denote the set of all simple $s-t$
paths in $G$. In a shortest path problem we seek a simple $s-t$ path in $G$,
minimizing the total cost. This classic network optimization problem can be
solved in polynomial time by using one of several known algorithms (see, e.g.
[1]). In this paper, we consider a recoverable version of the problem, in
which an $s-t$ path $X\in\Phi$, called a first-stage path, can be modified to
some extent in the second stage by applying a limited recovery action. This
action consists in choosing a second-stage path $Y$ in some prescribed
neighborhood $\Phi(X,k)$ of $X$, where $k\geq 0$ is a fixed recovery
parameter. We will consider the following three types of neighborhoods, called
arc inclusion, arc exclusion, and arc symmetric difference neighborhoods,
respectively:

$\displaystyle\Phi^{\mathrm{incl}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|Y\setminus X|\leq k\\},$ (1)
$\displaystyle\Phi^{\mathrm{excl}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|X\setminus Y|\leq k\\},$ (2)
$\displaystyle\Phi^{\mathrm{sym}}(X,k)$
$\displaystyle=\\{Y\in\Phi\,:\,|(Y\setminus X)\cup(X\setminus Y)|\leq k\\}$
(3)

The cost of the first-stage path $X$ is $\sum_{e\in X}C_{e}$. The second-stage
arc costs are uncertain while the path $X$ is chosen. Let $\hat{c}_{e}$ be a
nominal second-stage cost of arc $e\in A$ and $\Delta_{e}$ be a maximum
deviation of the second-stage cost of $e$ from $\hat{c}_{e}$. Hence,
$c_{e}\in[\hat{c}_{e},\hat{c}_{e}+\Delta_{e}]$ for each $e\in A$. In the
following, we will assume that each realization of the second-stage arc costs
$(c_{e})_{e\in A}$, called scenario, belongs to the following uncertainty set
[3]:

$\displaystyle\mathcal{U}(\Gamma)$
$\displaystyle=\\{\boldsymbol{c}=(c_{e})_{e\in
A}\,:\,c_{e}\in[\hat{c}_{e},\hat{c}_{e}+\Delta_{e}],e\in
A\,:\,|c_{e}>\hat{c}_{e}|\leq\Gamma\\}.$ (4)

$\mathcal{U}(\Gamma)$ is called a discrete budgeted uncertainty set and the
parameter $\Gamma\in\\{0,\dots,|A|\\}$ is called a discrete budget. It denotes
the maximum number of the second-stage arc costs that can differ from their
nominal values. We consider the following recoverable robust shortest path
problem with discrete recourse [4, 9]:

$\textsc{Rec Rob SP}:\;\min_{X\in\Phi}\left(\sum_{e\in
X}C_{e}+\max_{\boldsymbol{c}\in\mathcal{U}(\Gamma)}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}\right).$ (5)

Given a first stage path $X\in\Phi$, we will consider the following
adversarial problem:

$\textsc{Adv
SP}:\;\max_{\boldsymbol{c}\in\mathcal{U}(\Gamma)}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}.$ (6)

Given additionally a second-stage cost scenario $(c_{e})_{e\in A}$ we will
consider the following incremental problem:

$\textsc{Inc SP}:\;\min_{Y\in\Phi(X,k)}\sum_{e\in Y}c_{e}.$ (7)

The Rob Rec SP problem was first investigated in [4], where it was shown to be
strongly NP-hard for the arc inclusion neighborhood. It was shown in [5] that
Inc SP for the arc exclusion neighborhood is strongly NP-hard and the same
hardness result was established in [9] for the arc symmetric difference
neighborhood. Interestingly, the Inc SP problem for the arc inclusion
neighborhood can be solved in polynomial time [5]. The Adv SP problem is
strongly NP-hard for all considered neighborhoods, which results from a
reduction from the most vital arcs problem [2] (see also [9]). Because Adv SP
is a special case of Rec Rob SP (we fix $C_{e}=0$ for $e\in X$ and $C_{e}$ to
some large number if $e\notin X$), the same hardness result holds for Rec Rob
SP.

#### New results

In this paper we strengthen the negative complexity results for Rec Rob SP.
Namely, we show that the problem is $\Sigma_{3}^{p}$-hard for the arc
exclusion and the arc symmetric difference neighborhoods. We also prove that
the adversarial problem for these neighborhoods is $\Pi_{2}^{p}$-hard.

##  2 Hardness of the adversarial problem

To show the hardness results for Adv SP we will use the following problem:

$\forall(\Gamma)\exists$CNF-SAT

Input: Two disjoint sets $\mathbb{Y}$ and $\mathbb{Z}$ of Boolean variables
that take the values 0 and 1, a Boolean formula
$\digamma(\mathbb{Y},\mathbb{Z})$ in conjunctive normal form, an integer
$\Gamma$.

Question: Is it true that for all subset
$\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$ such that
$|\mathbb{Y}^{\prime}|\leq\Gamma$, there exists 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$ of variables in $\mathbb{Y}$ and
$\mathbb{Z}$ in which all variables in $\mathbb{Y}^{\prime}$ are set to 0
($\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$, where
$\boldsymbol{y}|_{\mathbb{Y}^{\prime}}$ stands for the restriction of the
assignment $\boldsymbol{y}$ to the set $\mathbb{Y}^{\prime}$) and
$\digamma(\boldsymbol{y},\boldsymbol{z})$ is satisfied?

######  Theorem 1.

$\forall(\Gamma)\exists$CNF-SAT is $\Pi^{p}_{2}$-complete, even for
$|\mathbb{Y}|=|\mathbb{Z}|$.

The proof of Theorem 1 is shown in Appendix. It is adapted from [7, Theorem 1]
to our case. We will also use the following problem:

2-Vertex-Disjoint Paths

Input: A digraph $G=(V,A)$ and two terminal pairs $(s_{i},t_{i})$, where
$s_{i},t_{i}\in V$, $i\in\\{1,2\\}$ are pairwise distinct vertices.

Question: Are there vertex-disjoint paths $\pi_{1}$ and $\pi_{2}$ in $G$ such
that $\pi_{i}$ is a simple $s_{i}$-$t_{i}$ path, $i\in\\{1,2\\}$?

The 2-Vertex-Disjoint Paths is strongly NP-complete in general digraphs [6].

######  Observation 1.

Let $\widehat{\mathcal{U}}(\Gamma^{d})=\\{\boldsymbol{c}=(c_{e})_{e\in
A}\,:\,c_{e}\in\\{\hat{c}_{e},\overline{c}_{e}\\},\overline{c}_{e}=\hat{c}_{e}+\delta_{e}\Delta_{e},\delta_{e}\in\\{0,1\\},e\in
A\,:\,\sum_{e\in
A}\delta_{e}\leq\Gamma^{d}\\}\subseteq\mathcal{U}(\Gamma^{d})$. The following
equation holds:

$\max_{\boldsymbol{c}\in\mathcal{U}(\Gamma^{d})}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}=\max_{\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})}\min_{Y\in\Phi(X,k)}\sum_{e\in
Y}c_{e}.$

In what follows we can replace $\mathcal{U}(\Gamma^{d})$ with
$\widehat{\mathcal{U}}(\Gamma^{d})$ in the definition of Adv SP and Rec Rob
SP. Consider the following decision version of the adversarial problem:

Decision-Adv SP$(\Gamma^{d})$

Input: A digraph $G=(V,A)$, a path $X\in\Phi$, second stage arc costs under
the discrete budgeted uncertainty $\widehat{\mathcal{U}}(\Gamma^{d})$, i.e.
nominal costs $\hat{\boldsymbol{c}}=(\hat{c}_{e})_{e\in A}\geq\boldsymbol{0}$,
cost upper bounds $\overline{\boldsymbol{c}}=(\overline{c}_{e})_{e\in
A}\geq\hat{\boldsymbol{c}}$, an integer budget $\Gamma^{d}$, a recovery
parameter $k$, a bound $\gamma\geq 0$.

Question: Does for every $\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$
a path $Y\in\Phi(X,k)$ such that $\sum_{e\in Y}c_{e}\leq\gamma$ exist?

######  Lemma 1.

Decision-Adv SP$(\Gamma^{d})$ with
$\Phi(X,k)\in\\{\Phi^{\mathrm{excl}}(X,k),\Phi^{\mathrm{sym}}(X,k)\\}$ lies in
class $\Pi^{p}_{2}$.

###### Proof.

Indeed, Decision-Adv SP$(\Gamma^{d})$ can be expressed in the form:
$(\forall\,\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d}))(\exists\,Y\in\Phi(X,k))(\sum_{e\in
Y}c_{e}\leq\gamma)$. ∎

######  Theorem 2.

Decision-Adv SP$(\Gamma^{d})$ with the neighborhood
$\Phi(X,k):=\Phi^{\mathrm{excl}}(X,k)$ is $\Pi^{p}_{2}$-complete even if
$k=2$.

###### Proof.

Lemma 1 shows that our problem lies in $\Pi^{p}_{2}$. Now, we need to prove
that it is $\Pi^{p}_{2}$-hard. We will show a reduction from
$\forall(\Gamma)\exists$CNF-SAT to Decision-Adv SP$(\Gamma^{d})$ with
$\Phi^{\mathrm{excl}}(X,k)$.

We are given an instance $(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of
$\forall(\Gamma)\exists$CNF-SAT, i.e. two disjoint sets of variables,
$\mathbb{Y}=\\{y_{1},\ldots,y_{n}\\}$ and
$\mathbb{Z}=\\{z_{1},\ldots,z_{n}\\}$, a formula $\digamma$ in CNF,
$\digamma=\mathcal{C}_{1}\wedge\cdots\wedge\mathcal{C}_{m}$, a budget
$\Gamma$. The reduction is divided into two steps.

In the first step, we obtain a digraph $G=(A,V)$ from
$(\mathbb{Y},\mathbb{Z},\digamma)$ by a standard transformation used to reduce
CNF-SAT to 2-Vertex-Disjoint Paths (see, e.g., [8]). For each variable
$y_{i}\in\mathbb{Y}$, we associate a variable subgraph consisting of only two
internally node-disjoint paths (the internal nodes:
$\overline{y}_{i}^{\mathcal{C}_{1}},\ldots,\overline{y}_{i}^{\mathcal{C}_{m}}$
and $y_{i}^{\mathcal{C}_{1}},\ldots,{y}_{i}^{\mathcal{C}_{m}}$) of arc length
$m+1$, called the upper and lower paths. If we go through the upper (lower)
path, we simulate assigning $y_{i}:=0$ ($y_{i}:=1$). Similarly, we associate
$n$ variable subgraphs with the variables in $\mathbb{Z}$. We fix the terminal
pair $(s_{2},t_{2})$, where $s_{2}=y_{1}$ and $t_{2}=z_{n}$. For each clause
$\mathcal{C}_{j}$, $j\in[m]$, we create two nodes $\mathcal{C}^{(1)}_{j}$ and
$\mathcal{C}^{(2)}_{j}$ and for each literal $l_{r}\in\mathcal{C}_{j}$,
$l_{r}\in\\{y_{r},\overline{y}_{r},z_{r},\overline{z}_{r}\\}$, if
$l_{r}=y_{r}$ then we add two literal arcs
$(\mathcal{C}^{(1)}_{j},\overline{y}_{r}^{\mathcal{C}_{j}})$ and
$(\overline{y}_{r}^{\mathcal{C}_{j}},\mathcal{C}^{(2)}_{j})$; if
$l_{r}=\overline{y}_{r}$ then we add two literal arcs
$(\mathcal{C}^{(1)}_{j},y_{r}^{\mathcal{C}_{j}})$ and
$(y_{r}^{\mathcal{C}_{j}},\mathcal{C}^{(2)}_{j})$; we do the same if
$l_{r}=z_{r}$ or $l_{r}=\overline{z}_{r}$, $r\in[n]$. Finally, we add to $G$,
$s_{1}$ and $t_{1}$ which form the second terminal pair $(s_{1},t_{1})$. We
also add $m+1$ arcs
$(s_{1},\mathcal{C}^{(1)}_{1}),(\mathcal{C}^{(2)}_{m},t_{1})$, and
$(\mathcal{C}^{(2)}_{j},\mathcal{C}^{(1)}_{j+1})$ for each $j\in[m-1]$. The
graph $G$ is depicted in Figure 1.

It is easily seen that $\digamma$ is satisfiable if and only if $G$ contains
two node-disjoint simple paths, namely $\pi_{1}$ from $s_{1}$ to $t_{1}$ (the
clause path) and $\pi_{2}$ from $s_{2}$ to $t_{2}$ (the variable path). In
fact, every satisfying 0-1 assignment $(\boldsymbol{y},\boldsymbol{z})$ of
$\digamma$ corresponds to two node-disjoint simple paths $\pi_{1}$ and
$\pi_{2}$, such that the path $\pi_{2}$ contains, as a subpath, the lower path
corresponding to $y_{r}$ ($z_{r}$) if and only if $y_{r}=1$ ( $z_{r}=1$),
$r\in[n]$, in $(\boldsymbol{y},\boldsymbol{z})$, and the path $\pi_{1}$ uses
exactly two among all literal arcs and, in consequence, one node from the set
$\\{\overline{y}_{r}^{\mathcal{C}_{j}},\overline{z}_{r}^{\mathcal{C}_{j}},y_{r}^{\mathcal{C}_{j}},z_{r}^{\mathcal{C}_{j}}\\}_{r\in[n]}$
not used by $\pi_{2}$ for every clause $\mathcal{C}_{j}$, $j\in[m]$.

Figure 1: A graph $G$ in an instance of Decision-Adv SP$(\Gamma^{d})$ (the
solid and dashed arcs) and an embedded instance of 2-Vertex-Disjoint Paths
(the solid arcs) corresponding to the formula $\digamma=(\overline{y}_{1}\vee
y_{2}\vee\overline{z}_{1})\wedge(\overline{y}_{n}\vee\overline{z}_{1}\vee
z_{n})\wedge\cdots\wedge\mathcal{C}_{m}$.

In the second step we complete $G=(V,A)$ by adding three arcs $(s_{1},t_{1})$,
$(t_{1},s_{2})$ and $(s_{2},t_{2})$ representing the path $X\in\Phi$. We fix
$s:=s_{1}$ and $t:=t_{2}$ as the starting and the destination nodes,
respectively. In the arc set $A$, we distinguish $n$ arcs labeled $y_{i}$,
$i\in[n]$, (see the bold arcs in Figure 1) and denote them by
$A_{\boldsymbol{y}}$. The second stage arc costs under
$\widehat{\mathcal{U}}(\Gamma^{d})$ are defined as follows: $\hat{c}_{e}=0$ if
$e\in A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}$, $\hat{c}_{e}=1$ otherwise;
$\overline{c}_{e}=0$ if $e\in
A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}\setminus A_{\boldsymbol{y}}$,
$\overline{c}_{e}=1$ otherwise. Thus, the uncertainty is only allowed on the
arcs in $A_{\boldsymbol{y}}$. Finally, we set: the budget
$\Gamma^{d}:=\Gamma$, the recovery parameter $k:=2$ and the bound $\gamma:=0$.
This completes the reduction.

What is left to show is that an instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of $\forall(\Gamma)\exists$CNF-SAT
is a Yes-instance if and only if the built instance
$(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ of Decision-Adv
SP$(\Gamma^{d})$ with $\Phi^{\mathrm{excl}}(X,k)$ is a Yes-instance.

($\Rightarrow$) Assume that an instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance. Consider any
scenario $\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$. Let
$A^{\prime}_{\boldsymbol{y}}\subseteq A_{\boldsymbol{y}}$ be the subset of
arcs in $A_{\boldsymbol{y}}$ whose costs under $\boldsymbol{c}$ are at their
upper bounds equal to 1. Of course,
$|A^{\prime}_{\boldsymbol{y}}|\leq\Gamma^{d}$.  Let
$\mathbb{Y}^{\prime}=\\{y_{i}\,:\,e_{y_{i}}\in
A^{\prime}_{\boldsymbol{y}}\\}\subseteq\mathbb{Y}$. Thus,
$|\mathbb{Y}^{\prime}|=|A^{\prime}_{\boldsymbol{y}}|\leq\Gamma^{d}=\Gamma$.
Since $(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance, there
exists a 0-1 assignment $(\boldsymbol{y},\boldsymbol{z})$ in
$\mathbb{Y}\cup\mathbb{Z}$, in which
$\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$, satisfying
$\digamma(\boldsymbol{y},\boldsymbol{z})$. Hence
$(\boldsymbol{y},\boldsymbol{z})$ corresponds to two simple node-disjoint
paths $\pi_{1}$ (the clause path) and $\pi_{2}$ (the variable path) from
$s_{1}$ to $t_{1}$ and $s_{2}$ to $t_{2}$, respectively. The paths $\pi_{1}$
and $\pi_{2}$ together with the arc $(t_{1},s_{2})$ form a simple path
$Y\in\Phi^{\mathrm{excl}}(X,2)$. Observe that the path $\pi_{2}$ uses only
arcs that correspond to true literals, which are uniquely defined by
$(\boldsymbol{y},\boldsymbol{z})$. Thus, it does not traverse the arcs from
$A^{\prime}_{\boldsymbol{y}}$, which yields $\sum_{e\in Y}c_{e}=0$. This shows
that $(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ is a Yes-instance.

($\Leftarrow$) Assume that an instance
$(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ is a Yes-instance.
Consider any $\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$ such that
$|\mathbb{Y}^{\prime}|\leq\Gamma$. Let
$A^{\prime}_{\boldsymbol{y}}=\\{e_{y_{i}}\,:\,y_{i}\in\mathbb{Y}^{\prime}\\}\subseteq
A_{\boldsymbol{y}}$. Obviously, $|A_{\boldsymbol{y}}|\leq\Gamma=\Gamma^{d}$.
Consider scenario $\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$ defined
as follows: $c_{e}:=\overline{c}_{e}$ if $e\in A^{\prime}_{\boldsymbol{y}}$,
$c_{e}:=\hat{c}_{e}$ if $e\in A\setminus A^{\prime}_{\boldsymbol{y}}$. Since
$(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ is Yes-instance, there
exists a simple path $Y\in\Phi(X,2)$ such that $\sum_{e\in Y}c_{e}=0$. Hence,
no arc from $A^{\prime}_{\boldsymbol{y}}\cup\\{(s_{1},t_{1}),(s_{2},t_{2})\\}$
belongs to $Y$. It must traverse $(t_{1},s_{2})$ and contain as subpaths two
simple node-disjoint paths $\pi_{1}$ (the clause path) and $\pi_{2}$ (the
variable path) from $s_{1}$ to $t_{1}$ and $s_{2}$ to $t_{2}$, respectively.
The variable path $\pi_{2}$ defines the 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$, namely, $y_{i}:=1$ ($z_{i}:=1$) if
$e_{y_{i}}\in\pi_{2}$ ($e_{z_{i}}\in\pi_{2}$); $y_{i}:=0$ ($z_{i}:=0$) if
$e_{\overline{y}_{i}}\in\pi_{2}$ ($e_{\overline{z}_{i}}\in\pi_{2}$),
$i\in[n]$. Clearly, $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$.
The paths $\pi_{1}$ and $\pi_{2}$ are node-disjoint. Thus, the clause path
$\pi_{1}$ contains exactly one literal arc leaving node
$\mathcal{C}^{(1)}_{j}$ and one literal arc coming into node
$\mathcal{C}^{(2)}_{j}$ for every $j\in[m]$. Therefore, the 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$ satisfies
$\digamma(\boldsymbol{y},\boldsymbol{z})$ and
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance. ∎

By Observation 1 and Theorem 2, we get the following corollary:

######  Corollary 1.

Adv SP under $\mathcal{U}(\Gamma^{d})$ with the neighborhood
$\Phi^{\mathrm{excl}}(X,k)$ is $\Pi^{p}_{2}$-hard and $\Pi^{p}_{2}$-hard to
approximate even if $k=2$.

######  Theorem 3.

Decision-Adv SP$(\Gamma^{d})$ with the neighborhood
$\Phi(X,k):=\Phi^{\mathrm{sym}}(X,k)$ is $\Pi^{p}_{2}$-complete.

###### Proof.

Lemma 1 shows that the problem under consideration lies in $\Pi^{p}_{2}$. The
proof is completed by showing that it is $\Pi^{p}_{2}$-hard. In the following,
we provide a reduction from $\forall(\Gamma)\exists$CNF-SAT to Decision-Adv
SP$(\Gamma^{d})$ with $\Phi^{\mathrm{sym}}(X,k)$.

Given an instance $(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of
$\forall(\Gamma)\exists$CNF-SAT. We construct an instance of Decision-Adv
SP$(\Gamma^{d})$ in much the same way as in the proof of Theorem 2 \- the only
difference is in the second step of the construction. In the second step, we
add to $G=(V,A)$ two arcs $(s_{1},t_{1})$, $(s_{2},t_{2})$, and instead of
$(t_{1},s_{2})$ (see Figure 1, the dashed arc) we add the path connecting
$t_{1}$ with $s_{2}$ consisting of $(m+1)n+3m+1+2$ arcs (the length of a
simple path from $s_{2}$ to $t_{2}$ plus the length of a simple path from
$s_{1}$ to $t_{1}$ plus two arcs, see Figure 1). We fix $s:=s_{1}$ and
$t:=t_{2}$ as the starting and the destination nodes, respectively. The added
arcs represent the path $X\in\Phi$. The set $A_{\boldsymbol{y}}$ contains $n$
arcs labeled by $y_{i}$, $i\in[n]$ (see Figure 1, the bold arcs). The second
stage arc costs under $\widehat{\mathcal{U}}(\Gamma^{d})$ are defined as
follows: $\hat{c}_{e}=0$ if $e\in
A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}$, $\hat{c}_{e}=1$ otherwise;
$\overline{c}_{e}=0$ if $e\in
A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}\setminus A_{\boldsymbol{y}}$,
$\overline{c}_{e}=1$ otherwise. Finally, we set: the budget
$\Gamma^{d}:=\Gamma$, the recovery parameter $k:=(m+1)n+3m+1+2$, and the bound
$\gamma:=0$. This completes an instance
$(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$.

As in the proof of Theorem 2, we can prove the following: an instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of $\forall(\Gamma)\exists$CNF-SAT
is a Yes-instance if and only if the built instance
$(G,X,\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$ of Decision-Adv
SP$(\Gamma^{d})$ with $\Phi^{\mathrm{sym}}(X,k)$ is a Yes-instance. ∎

Again, we have the following corollary, by Observation 1 and Theorem 3.

######  Corollary 2.

Adv SP under $\mathcal{U}(\Gamma^{d})$ with the neighborhood
$\Phi^{\mathrm{sym}}(X,k)$ is $\Pi^{p}_{2}$-hard and and $\Pi^{p}_{2}$-hard to
approximate.

##  3 Hardness of the recoverable robust problem

To characterize the complexity of Rec Rob SP we will use the following
problem:

$\exists\forall(\Gamma)\exists$3CNF-SAT

Input: Three disjoint sets $\mathbb{X}$, $\mathbb{Y}$, and $\mathbb{Z}$ of
Boolean variables that take the values 0 and 1, a Boolean formula
$\digamma(\mathbb{X},\mathbb{Y},\mathbb{Z})$ in the conjunctive normal form,
where every clause consists of three literals, an integer $\Gamma$.

Question: Is it true that there is an 0-1 assignment $\boldsymbol{x}$ of the
variables in $\mathbb{X}$ such that for all subset
$\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$ such that
$|\mathbb{Y}^{\prime}|\leq\Gamma$, there exists 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$ of variables in $Y$ and $Z$ in which all
variables in $\mathbb{Y}^{\prime}$ are set to 0
($\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$) and
$\digamma(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ is satisfied?

The problem $\exists\forall(\Gamma)\exists$3CNF-SAT is
$\Sigma^{p}_{3}$-complete, even if $|\mathbb{X}|=|\mathbb{Y}|=|\mathbb{Z}|$
[7, Theorem 1]. Consider the following decision version of Rec Rob SP:

Decision-Rec Rob SP$(\Gamma^{d})$

Input: A digraph $G=(V,A)$, first stage arc costs
$\boldsymbol{C}=(C_{e})_{e\in A}\geq\boldsymbol{0}$, second stage arc costs
under the discrete budgeted uncertainty $\widehat{\mathcal{U}}(\Gamma^{d})$,
i.e. nominal costs $\hat{\boldsymbol{c}}=(\hat{c}_{e})_{e\in
A}\geq\boldsymbol{0}$, upper bounds on the arc costs
$\overline{\boldsymbol{c}}=(\overline{c}_{e})_{e\in
A}\geq\hat{\boldsymbol{c}}$, an integer budget $\Gamma^{d}$, recovery
parameter $k$, a bound $\gamma\geq 0$.

Question: Is there a path $X\in\Phi$ such that for every
$\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$ there exists a path
$Y\in\Phi(X,k)$ such that $\sum_{e\in X}C_{e}+\sum_{e\in Y}c_{e}\leq\gamma$?

######  Lemma 2.

Decision-Rec Rob SP$(\Gamma^{d})$ with
$\Phi(X,k)\in\\{\Phi^{\mathrm{excl}}(X,k),\Phi^{\mathrm{sym}}(X,k)\\}$ lies in
the class $\Sigma^{p}_{3}$.

###### Proof.

Indeed, Decision-Rec Rob SP$(\Gamma^{d})$ can be expressed in the form:
$(\exists\,X\in\Phi)(\forall\,\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d}))(\exists\,Y\in\Phi(X,k))(\sum_{e\in
X}C_{e}+\sum_{e\in Y}c_{e}\leq\gamma)$. ∎

######  Theorem 4.

Decision-Rec Rob SP$(\Gamma^{d})$ with the neighborhood
$\Phi(X,k):=\Phi^{\mathrm{excl}}(X,k)$ is $\Sigma^{p}_{3}$-complete even if
$k=2$.

###### Proof.

From Lemma 2 it follows that Decision-Rec Rob SP$(\Gamma^{d})$ with
$\Phi^{\mathrm{excl}}(X,k)$ is in $\Sigma^{p}_{3}$.

We now prove that it is $\Sigma^{p}_{3}$-hard. Let
$(\mathbb{X},\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ be an instance of
$\exists\forall(\Gamma)\exists$3CNF-SAT. In much the same way as in the proof
of Theorem 2, we construct an instance
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$ of Decision-
Rec Rob SP$(\Gamma^{d})$. Small changes are in the first and second steps.

In the first step, we additionally associate $n$ variable subgraphs (see
Figure 2) with the variables in $\mathbb{X}$, which results in adding them to
the graph $G$ depicted in Figure 1, $t_{2}$ is the only one connecting node.
Then, for each clause, we additionally add to $G$ the literal arcs
corresponding to $x_{i}$ or $\overline{x}_{i}$, $i\in[n]$ (in the same way as
for the variables in $\mathbb{Y}$ and $\mathbb{Z}$) Now, it is easy to check
that $\digamma$ is satisfiable if and only if $G$ contains two node-disjoint
simple paths $\pi_{1}$ (the clause path) and $\pi_{2}$ (the variable path)
from $s_{1}$ to $t_{1}$ and from $s_{2}$ to $t^{\prime}_{2}$, respectively
($t^{\prime}_{2}$ is now a new terminal node).

Figure 2: The $n$ $\boldsymbol{x}$-variable subgraphs.

In the second step, the dashed arcs connect the same nodes as in Figure 1.
This finishes building $G=(V,A)$. We now fix $s:=s_{1}$ and
$t:=t^{\prime}_{2}$ as the starting and the destination nodes, respectively.
The first stage costs are defined as follows: $C_{e}=0$ if
$e\in\\{(s_{1},t_{1}),(t_{1},s_{2}),(s_{2},t_{2})\\}$ or $e$ is an arc of the
$\boldsymbol{x}$-variable subgraphs (see Figure 2). The rest of the arcs have
the first stage costs equal to 1. The second stage arc costs under
$\widehat{\mathcal{U}}(\Gamma^{d})$ are defined as follows: $\hat{c}_{e}=0$ if
$e\in A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}$, $\hat{c}_{e}=1$ otherwise;
$\overline{c}_{e}=0$ if $e\in
A\setminus\\{(s_{1},t_{1}),(s_{2},t_{2})\\}\setminus A_{\boldsymbol{y}}$,
$\overline{c}_{e}=1$ otherwise. Again, the uncertainty affects only the arcs
from $A_{\boldsymbol{y}}$. Finally, we set: the budget $\Gamma^{d}:=\Gamma$,
the recovery parameter $k:=2$, and the bound $\gamma:=0$. This completes the
instance $(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$

We now need to prove the following assertion: an instance
$(\mathbb{X},\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of
$\exists\forall(\Gamma)\exists$3CNF-SAT is a Yes-instance if and only if the
corresponding instance
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$ of Decision-
Rec Rob SP$(\Gamma^{d})$ with $\Phi^{\mathrm{excl}}(X,k)$ is a Yes-instance.

($\Rightarrow$) Assume that
$(\mathbb{X},\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance. Fix a
0-1 assignment $\boldsymbol{x}$ of the variables in $\mathbb{X}$ such that for
every $\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$,
$|\mathbb{Y}^{\prime}|\leq\Gamma$, there exists a 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$ of the variables in $\mathbb{Y}$ and
$\mathbb{Z}$, in which $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$
and $\digamma(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ is satisfied. A
path $X\in\Phi$ consists of the arcs: $(s_{1},t_{1})$, $(t_{1},s_{2})$ and
$(s_{2},t_{2})$ and the subpath from $t_{2}$ to $t^{\prime}_{2}$ traversing
the arcs ($e_{x_{i}}$ or $e_{\overline{x}_{i}}$, $i\in[n]$) corresponding to
the true literals under the fixed $\boldsymbol{x}$ in the $n$
$\boldsymbol{x}$-variable subgraphs. Clearly, its first stage cost equals 0.
Consider any scenario $\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$.
Under this scenario a subset of arcs $A^{\prime}_{\boldsymbol{y}}\subseteq
A_{\boldsymbol{y}}$, $|A^{\prime}_{\boldsymbol{y}}|\leq\Gamma^{d}=\Gamma$,
have costs equal to 1 and the costs of the remaining arcs are 0. Define
$\mathbb{Y}^{\prime}=\\{y_{i}\,:\,e_{y_{i}}\in
A^{\prime}_{\boldsymbol{y}}\\}\subseteq\mathbb{Y}$,
$|\mathbb{Y}^{\prime}|\leq\Gamma^{d}=\Gamma$. Since
$(\mathbb{X},\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance, there
is a 0-1 assignment $(\boldsymbol{y},\boldsymbol{z})$ in
$\mathbb{Y}\cup\mathbb{Z}$, in which
$\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$ satisfying, together
with $\boldsymbol{x}$,
$\digamma(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$. The assignment
$(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ uniquely determines the part
of $Y\in\Phi^{\mathrm{excl}}(X,2)$, i.e. the simple path from $s_{2}$ to
$t^{\prime}_{2}$ (the variable path) denoted by $\pi_{2}$. Indeed, $\pi_{2}$
consists of the $3n$ subpaths (the lower or upper paths) traversing the arcs
corresponding to the true literals under
$(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ in the $3n$ variable
subgraphs. Thus $\pi_{2}$ does not contain any arc from
$A^{\prime}_{\boldsymbol{y}}$ and in consequence $\sum_{e\in\pi_{2}}c_{e}=0$.
Since $(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ is a satisfying
assignment, there exists a a simple path $\pi$ from $s_{1}$ to $t_{1}$ (the
clause path) that is node-disjoint with $\pi_{2}$ These paths $\pi_{1}$ and
$\pi_{2}$ together with $(t_{1},s_{2})$ form a simple path $Y$, which has the
arc $(t_{1},s_{2})$ common with $X$, and subpath from $t_{2}$ to
$t^{\prime}_{2}$. Thus, $Y\in\Phi^{\mathrm{excl}}(X,2)$ and $\sum_{e\in
X}C_{e}+\sum_{e\in Y}c_{e}=0$. Hence
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ is a Yes-
instance.

($\Leftarrow$) Assume that
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$ is a Yes-
instance. Thus, there exists a path $X\in\Phi$ such that $\sum_{e\in
X}C_{e}=0$. From the structure of the first stage costs, it follows that it
consists of the arcs: $(s_{1},t_{1})$, $(t_{1},s_{2})$ and $(s_{2},t_{2})$ and
the subpath from $t_{2}$ to $t^{\prime}_{2}$ traversing arcs of the $n$
$\boldsymbol{x}$-variable subgraphs. This subpath uniquely defines the 0-1
assignment $\boldsymbol{x}$ of the variables in $\mathbb{X}$, i.e. $x_{i}:=1$
if the subpath contains arc $e_{x_{i}}$; $x_{i}:=0$ if the subpath contains
arc $e_{\overline{x}_{i}}$, $i\in[n]$. Consider any
$\mathbb{Y}^{\prime}\subset\mathbb{Y}$ such that
$|\mathbb{Y}^{\prime}|\leq\Gamma$. Let
$A^{\prime}_{\boldsymbol{y}}=\\{e_{y_{i}}\,:\,y_{i}\in\mathbb{Y}^{\prime}\\}\subseteq
A_{\boldsymbol{y}}$, $|A_{\boldsymbol{y}}|\leq\Gamma=\Gamma^{d}$. Define
scenario $\boldsymbol{c}\in\widehat{\mathcal{U}}(\Gamma^{d})$ as follows:
$c_{e}:=\overline{c}_{e}$ if $e\in A^{\prime}_{\boldsymbol{y}}$,
$c_{e}:=\hat{c}_{e}$ if $e\in A\setminus A^{\prime}_{\boldsymbol{y}}$. Since
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k=2,\gamma=0)$, there
exists a simple path $Y\in\Phi^{\mathrm{excl}}(X,k)$ such that $\sum_{e\in
Y}c_{e}=0$. From the structure of $\boldsymbol{c}$ and the fact that
$Y\in\Phi^{\mathrm{excl}}(X,k)$, we have that neither of arcs $(s_{1},t_{1})$,
$(s_{2},t_{2})$ and arcs from $A^{\prime}_{\boldsymbol{y}}$ belong to $Y$. It
has to traverse $(t_{1},s_{2})$ and contain, as subpaths, two simple node-
disjoint paths $\pi_{1}$ (the clause path) and $\pi_{2}$ (the variable path)
from $s_{1}$ to $t_{1}$ and $s_{2}$ to $t^{\prime}_{2}$, respectively. The
variable path $\pi_{2}$ uniquely defines the 0-1 assignment
$(\boldsymbol{y},\boldsymbol{z})$, namely, $y_{i}:=1$ ($z_{i}:=1$) if
$e_{y_{i}}\in\pi_{2}$ ($e_{z_{i}}\in\pi_{2}$); $y_{i}:=0$ ($z_{i}:=0$) if
$e_{\overline{y}_{i}}\in\pi_{2}$ ($e_{\overline{z}_{i}}\in\pi_{2}$),
$i\in[n]$. Obviously, $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$.
The paths $\pi_{1}$ and $\pi_{2}$ are node-disjoint. Thus, the clause path
$\pi_{1}$ contains exactly one literal arc leaving node
$\mathcal{C}^{(1)}_{j}$ and one literal arc coming into node
$\mathcal{C}^{(2)}_{j}$ for every $j\in[m]$. Therefore, the 0-1 assignment
$(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ satisfies
$\digamma(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})$ and
$(\mathbb{X},\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ is a Yes-instance. ∎

By Observation 1 and Theorem 4, we get the following corollary:

######  Corollary 3.

Rec Rob SP under $\mathcal{U}(\Gamma^{d})$ with the neighborhood
$\Phi^{\mathrm{excl}}(X,k)$ is $\Sigma^{p}_{3}$-hard and $\Sigma^{p}_{3}$-hard
to approximate even if $k=2$.

######  Theorem 5.

Decision-Rec Rob SP$(\Gamma^{d})$ with the neighborhood
$\Phi(X,k):=\Phi^{\mathrm{sym}}(X,k)$ is $\Sigma^{p}_{3}$-complete.

###### Proof.

By Lemma 2, Decision-Rec Rob SP$(\Gamma^{d})$ with $\Phi^{\mathrm{sym}}(X,k)$
is in $\Sigma^{p}_{3}$. A reduction from an instance of
$\exists\forall(\Gamma)\exists$3CNF-SAT to an instance of Decision-Rec Rob
SP$(\Gamma^{d})$ is almost the same as in the proof of Theorem 4, the only
difference is in the second step.

In the second step, instead of adding arc $(t_{1},s_{2})$ to $G=(V,A)$, we add
the path connecting $t_{1}$ with $s_{2}$ consists of $(m+1)n+3m+1+2$ arcs.
Their costs in both the first and second stages are equal to 0. Here, we set
the recovery parameter $k:=(m+1)n+3m+1+2$. This completes the instance
$(G,\boldsymbol{C},\widehat{\mathcal{U}}(\Gamma^{d}),k,\gamma)$ of Decision-
Rec Rob SP$(\Gamma^{d})$. The proof goes the in the same way as the proof of
Theorem 4.

∎

Observation 1 and Theorem 4 lead to the following result:

######  Corollary 4.

Rec Rob SP under $\mathcal{U}(\Gamma^{d})$ with the neighborhood
$\Phi^{\mathrm{sym}}(X,k)$ is $\Sigma^{p}_{3}$-hard and $\Sigma^{p}_{3}$-hard
to approximate.

### Acknowledgements

The authors were supported by the National Science Centre, Poland, grant
2022/45/B/HS4/00355.

## References

  * [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.  Network Flows: theory, algorithms, and applications.  Prentice Hall, Englewood Cliffs, New Jersey, 1993.
  * [2] A. Bar-Noy, A. S. Khuller, and B. Schieber.  The complexity of finding most vital arcs and nodes.  Technical Report CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995.
  * [3] D. Bertsimas and M. Sim.  The price of robustness.  Operations research, 52:35–53, 2004.
  * [4] C. Büsing.  Recoverable robust shortest path problems.  Networks, 59:181–189, 2012.
  * [5] O. Şeref, R. K. Ahuja, and J. B. Orlin.  Incremental network optimization: theory and algorithms.  Operations Research, 57:586–594, 2009.
  * [6] S. Fortune, J. Hopcroft, and J. Wyllie.  The directed subgraph homeomorphism problem.  Theoretical Computer Science, 10:111–121, 1980.
  * [7] M. Goerigk, S. Lendl, and L. Wulf.  On the complexity of robust multi-stage problems with discrete recourse.  Discrete Applied Mathematics, 343:355–370, 2024.
  * [8] C.-L. Li, S. McCormick, and D. Simchi-Levi.  The complexity of finding two disjoint paths with min-max objective function.  Discrete Applied Mathematics, 26:105–115, 1990.
  * [9] E. Nasrabadi and J. B. Orlin.  Robust optimization with incremental recourse.  CoRR, abs/1312.4075, 2013.
  * [10] M. Schaefer and U. Christopher.  Completeness in the Polynomial-Time Hierarchy: A compendium.  SIGACT News, 33:32–49, 2002.

## Appendix

We will use the following problem:

$\forall\exists$3CNF-SAT

Input: Two disjoint sets $\mathbb{P}$ and $\mathbb{Q}$ of Boolean variables
that take the values 0 and 1, a Boolean formula $\Psi(\mathbb{P},\mathbb{Q})$
in conjunctive normal form (3CNF), where every clause consists of three
literals.

Question: Is it true that for all 0-1 assignments $\boldsymbol{p}$ of
variables in $\mathbb{P}$ there exists a 0-1 assignment $\boldsymbol{q}$ of
variables in $\mathbb{Q}$ such that $\Psi(\boldsymbol{p},\boldsymbol{q})$ is
satisfied?

$\forall\exists$3CNF-SAT is $\Pi^{p}_{2}$-complete, even for
$|\mathbb{P}|=|\mathbb{Q}|$, (see, e.g., [10]).

###### The proof of Theorem 1.

Obviously, $\forall(\Gamma)\exists$CNF-SAT is in $\Pi^{p}_{2}$, since it can
be expressed in the form
$\forall(\mathbb{Y}^{\prime}\subseteq\mathbb{Y}\,:\,|\mathbb{Y}^{\prime}|\leq\Gamma)(\exists(\boldsymbol{y},\boldsymbol{z})\in\\{0,1\\}^{|\mathbb{Y}|\times|\mathbb{Z}|}\,:\,\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0})\digamma(\boldsymbol{y},\boldsymbol{z})$.
We need to show that it is $\Pi^{p}_{2}$-hard by providing a reduction from
$\forall\exists$3CNF-SAT to $\forall(\Gamma)\exists$CNF-SAT, which is adapted
from [7, Theorem 1] to our case (some parts are nearly verbatim).

Given an instance $(\mathbb{P},\mathbb{Q},\Psi)$ of $\forall\exists$3CNF-SAT,
namely, two disjoint sets of Boolean variables,
$\mathbb{P}=\\{p_{1},\ldots,p_{n}\\}$ and
$\mathbb{Q}=\\{q_{1},\ldots,q_{n}\\}$, a Boolean formula $\Psi$ in CNF,
$\Psi=\mathcal{C}_{1}\wedge\cdots\wedge\mathcal{C}_{m}$, where each clause
$\mathcal{C}_{i}$, $i\in[m]$, we build an instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of $\forall(\Gamma)\exists$CNF-SAT
in two steps. First, we define two disjoint sets of Boolean variables:
$\mathbb{Y}=\\{y^{\mathrm{P}}_{1},\ldots,y^{\mathrm{P}}_{n},y^{\mathrm{N}}_{1},\ldots,y^{\mathrm{N}}_{n}\\}$
and
$\mathbb{Z}=\\{z_{1},\ldots,z_{n}\\}\cup\\{s_{1},\ldots,s_{n}\\}\cup\\{s\\}$
and replace in the formula $\Psi$ each positive literal $p_{j}$ by
$y^{\mathrm{P}}_{j}$, each negative literal $\overline{p}_{j}$ by
$y^{\mathrm{N}}_{j}$, each positive literal $q_{j}$ by $z_{j}$ and each
negative literal $\overline{q}_{j}$ by $\overline{z}_{j}$, $j\in[n]$. The
resulting formula
$\Psi^{\prime}=\mathcal{C}^{\prime}_{1}\wedge\cdots\wedge\mathcal{C}^{\prime}_{m}$
is in 3CNF and now depends on new variables $y^{\mathrm{P}}_{j}$,
$y^{\mathrm{N}}_{j}$ and $z_{j}$, $j\in[n]$. In the second step, we form the
formula $\digamma$, which is based on the modified $\Psi^{\prime}$ in which to
each clause $\mathcal{C}^{\prime}_{i}$ we add the additional positive literal
$s$, i.e.

$\mathcal{C}^{\prime\prime}_{i}:=(\mathcal{C}^{\prime}_{i}\vee s),\,i\in[m].$
(8)

Now each $\mathcal{C}^{\prime\prime}_{i}$, $i\in[m]$, consists of exactly four
literals. Then, we add to $\digamma$ $2n$ two literal clauses of the following
form:

$(y^{\mathrm{P}}_{j}\vee\overline{s}_{j})\text{ and
}(y^{\mathrm{N}}_{j}\vee\overline{s}_{j}),\,j\in[n].$ (9)

Finally, we add to $\digamma$ the following clause

$(\overline{s}\vee s_{1}\vee\cdots\vee s_{n})$ (10)

and set $\Gamma=n$. Thus, the constructed instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of $\forall(\Gamma)\exists$CNF-SAT
contains $4n+1$ variables and the formula $\digamma$ consists of $m+2n+1$
clauses. To meet the assumption $|\mathbb{Y}|=|\mathbb{Z}|$, it is enough to
add to $\mathbb{Y}$ a “dummy” variable that does not appear in any clause of
$\digamma$.

It remains to show that an instance $(\mathbb{P},\mathbb{Q},\Psi)$ of
$\forall\exists$3CNF-SAT is a Yes-instance if and only if the built instance
$(\mathbb{Y},\mathbb{Z},\digamma,\Gamma)$ of $\forall(\Gamma)\exists$CNF-SAT
is a Yes-instance.

($\Rightarrow$) Assume that instance $(\mathbb{P},\mathbb{Q},\Psi)$ is a Yes-
instance. Let $\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$ be an arbitrary but
fixed subset such that $|\mathbb{Y}^{\prime}|\leq\Gamma=n$. We need to
consider two cases.

Case 1: $|\mathbb{Y}^{\prime}|=n$ and for every $j\in[n]$ exactly one of the
variables $y^{\mathrm{P}}_{j}$ and $y^{\mathrm{N}}_{j}$ belongs to
$\mathbb{Y}^{\prime}$. Thus, in this case, $\mathbb{Y}^{\prime}$ uniquely
defines the 0-1 assignment $\boldsymbol{p}$ of variables in $\mathbb{P}$, i.e.
$p_{j}:=0$ if $y^{\mathrm{P}}_{j}\in\mathbb{Y}^{\prime}$ and $p_{j}:=1$ if
$y^{\mathrm{N}}_{j}\in\mathbb{Y}^{\prime}$, $j\in[n]$, and vice versa. Since
$(\mathbb{P},\mathbb{Q},\Psi)$ is a Yes-instance, there exists a 0-1
assignment $\boldsymbol{q}$ of variables in $\mathbb{Q}$ such that
$\Psi(\boldsymbol{p},\boldsymbol{q})$ is satisfied. Therefore, there exist the
0-1 assignment $\boldsymbol{y}$ of variables in $\mathbb{Y}$, where
$y^{\mathrm{P}}_{j}:=1$ and $y^{\mathrm{N}}_{j}:=0$ if $p_{j}=1$;
$y^{\mathrm{P}}_{j}:=0$ and $y^{\mathrm{N}}_{j}:=1$ if $p_{j}=0$, $j\in[n]$,
of course $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$, and the
assignment $\boldsymbol{z}\in\\{0,1\\}^{n}$, where $z_{j}=1\leftrightarrow
q_{j}=1$, $j\in[n]$ such that $\Psi^{\prime}(\boldsymbol{y},\boldsymbol{z})$
is satisfied and hence every $\mathcal{C}^{\prime}_{i}$, $i\in[m]$, is
satisfied. In consequence, all the clauses (8) are satisfied. In order to
satisfy all the clauses (9) and the clause (10), we set $s_{j}=0$ for every
$j\in[n]$ and $s=0$. Thus, $\digamma(\boldsymbol{y},\boldsymbol{z})$ is
satisfied.

Case 2: there exists $j^{*}\in[n]$ such that neither of the variables
$y^{\mathrm{P}}_{j^{*}}$ and $y^{\mathrm{N}}_{j^{*}}$ belongs to
$\mathbb{Y}^{\prime}$. In this case, $\mathbb{Y}^{\prime}$ does not define a
0-1 assignment $\boldsymbol{p}$ of variables in $\mathbb{P}$. We now define an
0-1 assignment $(\boldsymbol{y},\boldsymbol{z})$ satisfying $\digamma$,
namely, $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}:=\boldsymbol{0}$,
$y^{\mathrm{P}}_{j^{*}}:=1$, $y^{\mathrm{N}}_{j^{*}}:=1$, $s_{j^{*}}:=1$,
$s_{j}:=0$ for every $j^{*}\not=j$ and $s:=1$. The rest of the components in
$(\boldsymbol{y},\boldsymbol{z})$ are arbitrary. It is easily seen that the
clauses (8), (9) and (10) are satisfied for the assignment
$(\boldsymbol{y},\boldsymbol{z})$ and
$\digamma(\boldsymbol{y},\boldsymbol{z})$ is satisfied.

($\Leftarrow$) Assume that instance $(\mathbb{Y},\mathbb{Z},\digamma)$ is a
Yes-instance. Let $\boldsymbol{p}$ be an arbitrary 0-1 assignment of variables
in $\mathbb{P}$. This assignment uniquely defines the subset
$\mathbb{Y}^{\prime}\subseteq\mathbb{Y}$ such that $|\mathbb{Y}^{\prime}|=n$,
i.e.
$\mathbb{Y}^{\prime}=\\{y^{\mathrm{P}}_{j}\,:\,p_{j}=0,j\in[n]\\}\cup\\{y^{\mathrm{N}}_{j}\,:\,p_{j}=1,j\in[n]\\}$.
Since $(\mathbb{Y},\mathbb{Z},\digamma)$ is a Yes-instance, there exists a 0-1
assignment $(\boldsymbol{y},\boldsymbol{z})$ of variables in $\mathbb{Y}$ and
$\mathbb{Z}$ such that $\boldsymbol{y}|_{\mathbb{Y}^{\prime}}=\boldsymbol{0}$
satisfying $\digamma$. Since the clauses (9) and (10) are satisfied, it is
easy to check that $s_{j}=0$ for every $j\in[n]$ and $s=0$. From the
assignment $s=0$ and the fact that all the clauses (8) are satisfied, it
follows that for each $i\in[m]$ the clause $\mathcal{C}^{\prime}_{i}$ has to
be satisfied by $(\boldsymbol{y},\boldsymbol{z})$. Consider every clause
$\mathcal{C}^{\prime}_{i}$, $i\in[m]$. If $\mathcal{C}^{\prime}_{i}$ is
satisfied by the literal $y^{\mathrm{P}}_{j}$ ($y^{\mathrm{P}}_{j}=1$), then,
by the definition of $\mathbb{Y}^{\prime}$,
$y^{\mathrm{P}}_{j}\not\in\mathbb{Y}^{\prime}$ and the corresponding $p_{j}=1$
and the clause $\mathcal{C}_{i}$ is satisfied by $p_{j}$. Likewise, if
$\mathcal{C}^{\prime}_{i}$ is satisfied by a literal $y^{\mathrm{N}}_{j}$
($y^{\mathrm{N}}_{j}=1$), then again, by the definition of
$\mathbb{Y}^{\prime}$, $y^{\mathrm{N}}_{j}\not\in\mathbb{Y}^{\prime}$ and the
corresponding $p_{j}=0$, therefore, the clause $\mathcal{C}_{i}$ is satisfied
by $\overline{p}_{j}$. Clearly, a 0-1 assignment $\boldsymbol{q}$ can be
defined as follows $z_{j}=1\leftrightarrow q_{j}=1$, $j\in[n]$. Hence,
$\Psi(\boldsymbol{p},\boldsymbol{q})$ is satisfied. ∎