On the complexity of strongly connected components in directed hypergraphs

Abstract. We study the problem of determining strongly connected compo-nents (Sccs) of directed hypergraphs. The main contribution is an algorithm computing the terminal strongly connected components (i.e. Sccs which do not reach any other components than themselves). The time complexity of the algorithm is almost linear, which is a significant improvement over the known methods which are quadratic time. This also proves that the prob-lems of (i) testing strong connectivity, (ii) and determining the existence of a sink, can be both solved in almost linear time in directed hypergraphs. We also highlight an important discrepancy between the reachability relations in directed hypergraphs and graphs. We establish a superlinear lower bound on the size of the transitive reduction of the reachability relation in directed hy-pergraphs, showing that it is combinatorially more complex than in directed graphs. We also prove linear time reductions from combinatorial problems on the subset partial order, in particular from the well-studied problem of finding all minimal sets among a given family, to the problem of computing the Sccs in directed hypergraphs. 1