On testing single connectedness in directed graphs and some related problems

• We give improved algorithms to test single-connectedness of a graph.
• An example shows our runtime bound is tight.

Let G=(V,E)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∈Vv,w∈V there is at most one simple path from v to w in G. Buchsbaum and Carlisle (1993) [1] gave an algorithm for testing whether G   is singly-connected in O(n2)O(n2) time. In this paper we describe a refined version of this algorithm with running time O(s⋅t+m)O(s⋅t+m), where s and t   are the number of sources and sinks, respectively, in the reduced graph GrGr obtained by first contracting each strongly connected component of G   into one vertex and then eliminating vertices of indegree or outdegree 1 by a contraction operation. Moreover, we show that the problem of finding a minimum cardinality edge subset C⊆EC⊆E (respectively, vertex subset F⊆VF⊆V) whose removal from G leaves a singly-connected graph is NP-hard.