  Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$
is called a {\it rainbow edge-cut} if no two edges of $R$ are colored with the
same color. For two distinct vertices $u$ and $v$ of $G$, if an edge-cut
separates them, then the edge-cut is called a {\it $u$-$v$-edge-cut}. An
edge-colored graph $G$ is called \emph{strong rainbow disconnected} if for
every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and
minimum $u$-$v$-edge-cut ({\it rainbow minimum $u$-$v$-edge-cut} for short) in
$G$, separating them, and this edge-coloring is called a {\it strong rainbow
disconnection coloring} (srd-{\it coloring} for short) of $G$. For a connected
graph $G$, the \emph{strong rainbow disconnection number} (srd-{\it number} for
short) of $G$, denoted by $\textnormal{srd}(G)$, is the smallest number of
colors that are needed in order to make $G$ strong rainbow disconnected.
  In this paper, we first characterize the graphs with $m$ edges such that
$\textnormal{srd}(G)=k$ for each $k \in \{1,2,m\}$, respectively, and we also
show that the srd-number of a nontrivial connected graph $G$ equals the maximum
srd-number among the blocks of $G$. Secondly, we study the srd-numbers for the
complete $k$-partite graphs, $k$-edge-connected $k$-regular graphs and grid
graphs. Finally, we show that for a connected graph $G$, to compute
$\textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already
NP-complete to decide if $\textnormal{srd}(G)=3$ for a connected cubic graph.
Moreover, we show that for a given edge-colored (with an unbounded number of
colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong
rainbow disconnected.
