On k-component Algorithms for Graphs and Digraphs

Consider a digraph (or graph) G without any self-loops on parallel-edges. We denote the vertex-set and edge-set of G by V(G) and E(G), respectively. We denote the candinality of V(G) and E(G), namely, |V(G)| or |E(G)| by n and e, respectively. G is k-connected, if there exist at least k vertex-disjoint paths from v to w, for every ordered pair of v and w (v, w ∈ V(G)). A k-component of G is a maximal k-connected subgraph of G (see Figure 1). Hopcroft and Tarjan discovered algorithms for finding 1-components, 2-conponents and 3-components of a graph, as well as 1-components of a digraph, within O(n+e) time [Ta72], [HoTa73]. The existence of such linear algorithms for finding k-components of a graph for any fixed k(>3) was conjectured in [AhHoU174] ; however, no such linear algorithm has been found. Recently, Kanevsky and Ramachandran discovered an algorithm that finds all separating triplets of a 3-connected graph in O(n^2) time [KaRa87], which suggests the existence of an efficient algorithm for finding 4-components of a graph ; however, finding all separating triplets does not directly yield a decomposition into 4-components, and the problem still remains. Matula discovered a polynomial algorithm that finds all the k-components of a graph, using cluster analysis techniques [Ma77]. Note that the problems for graphs are easily reducible to those for symmetrical digraphs, although the converse is not true. Our purpose is to construct an algorithm to find all the k-components of a digraph. Our algorithm can be regarded as an extension and refinement (a practical, and probably more efficient version) of Matula's. Proceeding to our main results, we need to introduce some notations. For v, w∈V, let [v, w] denote a directed edge which leaves v and enters w. For v∈V, let Γ+(v)= {w|[v, w]∈E(G)}, and Γ-(v)={w|[w, v]∈E(G)}. We denote deg(v)=min{Γ+(v), Γ-(v)}. G is complete if Γ+(v)=Γ-(v)=n-1, for ∀v∈V(G). For U(⊂V(G)), ≪U≫_G denotes the induced subgraph of G by U, that is, a subgraph of G whose vertex-set is U, and whose edge-set is {[v, w]∈E(G)|v, w∈U}. S(⊂V(G)) is a separator of G if ≪V(G)＼S≫_G is not 1-connected. For l≥1, a l-separator, denoted by ζ^l(G), is a minimum separator, S, of G, such that |S|≤l, Note that ζ^l(G) is nothing but a minimum separator of G, if it exists, and that otherwise ζ^l(G) is empty (see Figure 1). We assume all digraphs in our algorithm are represented by adjacency structures [AhHoU174], [Ta72], and manipulated in an efficient way. Our results are summarized as follows.