Complexity of (arc)-connectivity problems involving arc-reversals or deorientations

Jørgen Bang-Jensen, Florian Hörsch, Matthias Kriesell

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 edg…