  The knowledge of the network topology is imperative to precisely describing
the viral dynamics of an SIS epidemic process. In scenarios for which the
network topology is unknown, one resorts to reconstructing the network from
observing the viral state trace. This work focusses on the impact of the viral
state observations on the computational complexity of the resulting network
reconstruction problem. We propose a novel method of constructing a specific
class of viral state traces from which the inference of the presence or absence
of links is either easy or difficult. In particular, we use this construction
to prove that the maximum-likelihood SIS network reconstruction is NP-hard. The
NP-hardness holds for any adjacency matrix of a graph which is connected.
