Make a graph singly connected by edge orientations

Tim A. Hartmann, Komal Muluk

A directed graph $D$ is singly connected if for every ordered pair of vertices $(s,t)$, there is at most one path from $s$ to $t$ in $D$. Graph orientation problems ask, given an u…