A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set system

In this paper, we first study what we call Superset-Subset-Disjoint (SSD) set system. Based on properties of SSD set system, we derive the following (I) to (IV): (I) For a nonnegative integer k and a graph $G=(V,E)$ with |V|≥2, let X₁,X₂,,Xq V denote all maximal proper subsets of V that induce k-edge-connected subgraphs. Then at least one of (a) and (b) holds: (a) ₁,X₂,,Xq\ is a partition of V; and (b) V X₁, V X₂,,V Xq are pairwise disjoint. (II) For $k=1$ and a strongly-connected digraph G, whether V is in (a) and/or (b) can be decided in $O(n+m)$ time and we can generate all such X₁,X₂,,Xq in O(n+m+|X₁|+|X₂|++|Xq|) time, where $n=|V|$ and $m=|E|$. (III) For a digraph G, we can enumerate in linear delay all vertex subsets of V that induce strongly-connected subgraphs. (IV) A digraph is Hamiltonian if there is a spanning subgraph that is strongly-connected and in the case (a).