  Critical Infrastructures like power and communication networks are highly
interdependent on each other for their full functionality. Many significant
research have been pursued to model the interdependency and failure analysis of
these interdependent networks. However, most of these models fail to capture
the complex interdependencies that might actually exist between the
infrastructures. The \emph{Implicative Interdependency Model} that utilizes
Boolean Logic to capture complex interdependencies was recently proposed which
overcome the limitations of the existing models. A number of problems were
studies based on this model. In this paper we study the \textit{Robustness}
problem in Interdependent Power and Communication Network. The robustness is
defined with respect to two parameters $K \in I^{+} \cup \{0\}$ and $\rho \in
(0,1]$. We utilized the \emph{Implicative Interdependency Model} model to
capture the complex interdependency between the two networks. The model
classifies the interdependency relations into four cases. Computational
complexity of the problem is analyzed for each of these cases. A polynomial
time algorithm is designed for the first case that outputs the optimal
solution. All the other cases are proved to be NP-complete. An
in-approximability bound is provided for the third case. For the general case
we formulate an Integer Linear Program to get the optimal solution and a
polynomial time heuristic. The applicability of the heuristic is evaluated
using power and communication network data of Maricopa County, Arizona. The
experimental results showed that the heuristic almost always produced near
optimal value of parameter $K$ for $\rho < 0.42$.
