  The connectivity of a graph is an important parameter to measure its
reliability. Structure and substructure connectivity, component connectivity
and $k$-restricted connectivity are well-known generalizations of the concept
of connectivity, which have been extensively studied from the combinatorial
point of view. Very little result is known about their complexity other than
the recently obtained computational complexity of $k$-restricted
edge-connectivity. In this paper, we zero in on characterizing the complexity
of structure and substructure connectivity, component connectivity and
$k$-restricted connectivity of graphs, showing that they are all NP-complete.
