  Cascading failures in complex systems have been studied extensively using two
different models: $k$-core percolation and interdependent networks. We combine
the two models into a general model, solve it analytically and validate our
theoretical results through extensive simulations. We also study the complete
phase diagram of the percolation transition as we tune the average local
$k$-core threshold and the coupling between networks. We find that the phase
diagram of the combined processes is very rich and includes novel features that
do not appear in the models studying each of the processes separately. For
example, the phase diagram consists of first and second-order transition
regions separated by two tricritical lines that merge together and enclose a
novel two-stage transition region. In the two-stage transition, the size of the
giant component undergoes a first-order jump at a certain occupation
probability followed by a continuous second-order transition at a lower
occupation probability. Furthermore, at certain fixed interdependencies, the
percolation transition changes from first-order $\rightarrow$ second-order
$\rightarrow$ two-stage $\rightarrow$ first-order as the $k$-core threshold is
increased. The analytic equations describing the phase boundaries of the
two-stage transition region are set up and the critical exponents for each type
of transition are derived analytically.
