  By a well known theorem of Robbins, a graph $G$ has a strongly connected
orientation if and only if $G$ is 2-edge-connected and it is easy to find, in
linear time, either a cut edge of $G$ or a strong orientation of $G$.
  A result of Durand de Gevigny shows that for every $k\geq 3$ it is NP-hard to
decide if a given graph $G$ has a $k$-strong orientation. Thomassen showed that
one can check in polynomial time whether a given graph has a 2-strong
orientation. This implies that for a given digraph $D$ we can determine in
polynomial time whether we can reorient (=reverse) some arcs of $D=(V,A)$ to
obtain a 2-strong digraph $D'=(V,A')$. This naturally leads to the question of
determining the minimum number of such arcs to reverse before the resulting
graph is 2-strong. In this paper we show that finding this number is NP-hard.
  If a 2-connected graph $G$ has no 2-strong orientation, we may ask how many
of its edges we may orient so that the resulting mixed graph is still 2-strong.
Similarly, we may ask for a 2-edge-connected graph $G$ how many of its edges we
can orient such that the resulting mixed graph remains 2-arc-strong. We prove
that when restricted to graphs satisfying suitable connectivity conditions,
both of these problems are equivalent to finding the minimum number of edges we
must double in a 2-edge-connected graph in order to obtain a 4-edge-connected
graph. Using this, we show that all these three problems are NP-hard.
  Finally, we consider the operation of deorienting an arc $uv$ of a digraph
$D$ meaning replacing it by an undirected edge between the same vertices. In
terms of connectivity properties, this is equivalent to adding the opposite arc
$vu$ to $D$. We prove that for every $\ell\geq 3$ it is NP-hard to find the
minimum number of arcs to deorient in a digraph $D$ in order to obtain an
$\ell$-strong digraph $D'$.
