  The fifth generation of communication technology (5G) revolutionizes mobile
networks and the associated ecosystems through the integration of cross-domain
networks. Network slicing is an enabling technology for 5G as it provides
dynamic, on-demand, and reliable logical network slices (i.e., network
services) over a common physical network/infrastructure. Since a network slice
is subject to failures originated from disruptions, namely node or link
failures, in the physical infrastructure, our utmost interest is to evaluate
the reliability of a network slice before assigning it to customers. In this
paper, we propose an evaluation metric, \textit{survivable probability}, to
quantify the reliability of a network slice under random physical link
failure(s). We prove the existence of a \textit{base protecting spanning tree
set} which has the same survivable probability as that of a network slice. We
propose the necessary and sufficient conditions to identify a base protecting
spanning tree set and develop corresponding mathematical formulations, which
can be used to generate reliable network slices in the 5G environment. In
addition to proving the viability of our approaches with simulation results, we
also discuss how our problems and approaches are related to the Steiner tree
problems and present their computational complexity and approximability.
