On testing single connectedness in directed graphs and some related problems

Martin Dietzfelbinger, Raed Jaberi

Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The graph $G$ is called singly-connected if for each pair of vertices $v,w\in V$ there is at most one simple pat…